算法Day04-算法研习指导之回溯算法框架

爱被打了一巴掌 2023-02-23 07:58 7阅读 0赞

### 回溯算法框架 ###

*  回溯算法基本概念
 *  全排列问题
 *  N皇后问题
 *   *   *  八皇后问题
 *  回溯算法总结

# 回溯算法基本概念 #

*  回溯算法框架 : **解决一个回溯问题,实际上就是一个决策树的遍历过程**
    
     *  **路径:** 已经做出的选择
     *  **选择列表:** 当前可以做的选择
     *  **结束条件:** 到达决策树底层,无法再做选择的条件
 *  **回溯算法框架代码:**

result[];
    def backTrack(路径, 选择列表):
    	if 满足条件:
    		result.add[路径]
    		return
    	
    	for 选择 in 选择列表:
    		做选择
    		backTrack(路径, 选择列表)
    		撤销选择

*  回溯算法框架的核心就是**for循环里面的递归,** 在递归调用之前 **\[做选择\],** 在递归调用之后 **\[撤销选择\]**

# 全排列问题 #

*  **全排列:** 对于**n**个 不重复的数,全排列共有**n!** 个
 *  **决策树:** 从根遍历全排列的决策树,就是所有的全排列
    
     *  可以将**路径**和**选择列表**作为决策树上每个节点的属性
 *  **定义的backTrack函数就像一个指针,在决策树上遍历,同时要正确维护每个节点的属性,每当走到树的底层,路径就会是一个全排列**
 *  树的遍历框架:

void traverse(TreeNode root) { 
    	for (TreeNode child : root.children) { 
    		/* * 前序遍历需要的操作 */
    		 ... 
    		 
    		 traverse(child);
    		 
    		 /* * 后序遍历需要的操作 */
    		  ...
    	}
    }

*  **前序遍历:** 代码在进入某一个节点之前的那个时间点执行
 *  **后序遍历:** 代码在离开某个节点之后的那个时间点执行
 *  函数在决策树上遍历时要正确维护节点的属性 **: 路径**和**选择**

for 选择 in 选择列表:
    	# 做选择
    	将该选择从选择列表中移除
    	路径.add(选择)
    	
    	backTrack(路径, 选择)
    	
    	# 撤销选择
    	路径.remove(选择)
    	将该选择再加入选择列表

*  **只要在递归之前做出选择,在递归之后撤销刚才的选择,就能得到每个节点的选择列表和路径**
 *  全排列问题代码:

// res-数字的全排列列表
    List<List<Integer>> res = new LinkedList<>();
    
    /** * 输入一组不重复的数字,返回这些数字的全排列 * * @param nums 用来获取全排列的一组不重复的数字 * @return List<List<Integer>> 全排列列表 */
    List<List<Integer>> permute(int[] nums) { 
    	// track-记录路径
     	LinkedList<Integer> track = new LinkedList<>();
     	backTrack(nums, track);
     	return res;
    }
    
    /** * 全排列遍历树: * 路径: 记录在track中 * 选择列表: nums中不存在track中的元素 * 结束条件: nums中的元素全在track中出现 * * @param nums 用来获取全排列的一组不重复的数字 * @param track 用于选择的路径 */
    void backTrack(int[] nums, List<List<Integer>> track) { 
    	/* * 触发结束的条件 */
    	if (track.size() == nums.length()) { 
    		res.add(new LinkedList(track));
    		return;
    	}
    
    	for (int i = 0; i < nums.length(); i++) { 
    		/* * 如果nums的值已经出现在track中,则跳过本次循环 */
    		 if (track.contains(num[i])) { 
    		 	continue;
    		 } 
    		 // 做选择
    		 res.add(nums[i]);
    		 // 进入下一层决策树
    		 backTrack(nums, track);
    		 // 取消选择
    		 track.removeLast();
    	}
    }

这里并没有显式记录**选择列表,** 而是通过**nums**和**track**推导出当前的选择列表

*  这就是回溯算法的底层应用框架,这个算法可以对**contains**方法进行优化
    
     *  **contains()** 的时间复杂度需要**O(N),** 可以使用交换元素达到判断是否包含的目的来降低算法时间复杂度
 *  回溯算法的时间复杂度都不可能低于**O(N!) :**
    
     *  因为使用回溯算法,穷举整棵决策树是无法避免的
 *  回溯算法的一个特点就是:
    
     *  **不像动态规划存在重叠子问题可以进行优化,回溯算法就是直接穷举,复杂度一般都很高**
 *  **示例:** 全排列解法代码

def permute(self, nums: List[int]) -> List[List[int]]:
    	# 回溯算法
    	result = []
    	track = [] # 可行路径
    	def backTrack(nums_, track_):
    		if len(track_) == len(nums_):	# 满足终止条件
    		result.append(track_[:])
    		return
    	for i in nums_:	# 所有可选项
    		if i in track_:	# 判断可选项是否可选
    			continue
    		track.append[i]	# 选择
    		backTrack(nums_, track_)	# 递归
    		track.pop();
    	backTrack(nums, track)
    	return result

# N皇后问题 #

*  **N皇后问题:**
    
     *  一个**N\*N**的棋盘,放置**N**个皇后,使得各个皇后之间不能相互攻击
     *  其中皇后可以攻击同一行,同一列,左上左下右上右下四个方向的任意单位
 *  **问题分析:**
    
     *  这个问题本质上和全排列问题相似:
        
         *  决策树的每一层表示棋盘上的每一行
         *  每个节点可以做出选择: 在该行的任意一列放置一个皇后

vector<vector<String>> res;
    
    /** * 根据棋盘的边长,获取所有合法的放置 * * @param n 棋盘的边长 * @return vector<vector<String>> 所有合法的放置 */
    vector<vector<String>> solveNQueens(int n) { 
    	/* * 初始化空棋盘 * '.' 表示空 * 'Q' 表示皇后 */
    	vector<String> board(n, String(n, '.'));
    	backTrack(board, 0);
    	return res;	
    }
    
    /** * 路径: board中小于row的那些行都已经成功放置了皇后 * 选择列表: 第row行所有列都是放置皇后的选择 * 结束条件: row超过board最后一行 * */
    void backTrack(vector<String>& board, int row) { 
    	/* * 触发结束条件 */
    	 if (row == board.size()) { 
    	 	res.push_back(board);
    	 	return;
    	 }
    
    	int n = board[row].size();
    	for (int col = 0; col < n; col++) { 
    		/* * 排出不合法的选择 */
    		 if (!isValid(board, row, col)) { 
    		 	continue;
    		 }
    
    		 // 做出选择
    		 board[row][col] = 'Q';
    		 // 进入下一行决策
    		 backTrack(board, row + 1);
    		 // 撤销选择
    		 board[row][col] = '.';
    	}
    }
    
    /** * 判断是否可以在board[row][col]放置皇后 * @param board 可以用于放置皇后的棋盘数组 * @param row 行参数 * @param col 列参数 * @return 是否可以在board[row][col]放置皇后 */
    boolean isValid(vector<String>& board, int row, int col) { 
    	int n = board.size();
    	
    	/* * 检查列是否有皇后互相冲突 */
    	 for (int i = 0; i < n; i++) { 
    	 	if (board[i][col] == 'Q') { 
    	 		return false;
    	 	}		 	
    	 }
    
    	/* * 检查右上方是否有皇后互相冲突 */
    	 for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { 
    	 	if (board[i][j] == 'Q') { 
    	 		return false;
    	 	}
    	 }
    
    	/* * 检查左上方是否有皇后互相冲突 */
    	 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { 
    	 	if (board[i][j] == 'Q') { 
    	 		return false;
    	 	}
    	 } 
    	 return true;
    }

*  函数**backTrack**类似在决策树上游走的指针,通过**row**和**col**就可以表示函数遍历到的位置,然后通过**isValid**函数将不符合条件的情况进行剪枝
 *  回溯算法问题 **: 确定做选择的方式,排除不合法的选择**

### 八皇后问题 ###

*  当**N=8**时,就是八皇后问题:
    
     *  **决策树:** 尽管使用了**isValid**剪枝,最坏的时间复杂度依然是**O(NN+1).** 并且无法优化
 *  **有时,并不是需要得到所有合法答案,只需要其中一个答案:**
    
     *  比如解数独的算法,找出所有解法的复杂度很高,只要找到一种解法即可
     *  优化回溯算法:
    
        /* * 函数找到一个答案后就返回true */
         boolean backTrack(vector<String>& board, int row) { 
         	// 当row超过board的最后一行时,触发结束条件
         	if (row == board.size()) { 
         		row.push_back(board);
         		return true;
         	}
         	...
         	for (col = 0; col < n; col++) { 
         		...
         		board[row][col] = 'Q';
         		/* * 只要找到一个答案,就会返回true * for循环的后续递归穷举都会被阻断 */
         		if (backTrack(board, row + 1)) { 
         			return true;
         		}
         		board[row][col] = '.';
         	}
         	return false;
         }

# 回溯算法总结 #

*  **回溯算法:** 就是多叉树的遍历问题,关键就是在前序遍历和后续遍历的位置做一些操作
 *  **回溯算法框架:**

def backTrack(...):
    	for 选择 in 选择列表:
    		做选择
    		backTrack(...)
    		撤销选择

*  **backTrack**函数中,需要维护走过的 **\[路径\]** 和当前可以做的 **\[选择列表\],** 当触发 **\[结束条件\]** 时,将 **\[路径\]** 记入结果集

>  *  **回溯算法和动态规划比较:**
>     
>      *  动态规划的三个需要明确的点:
>         
>          *  **状态**
>          *  **选择**
>          *  **base case**
>      *  对应着回溯算法中的:
>         
>          *  **路径**
>          *  **选择列表**
>          *  **结束条件**
>  *  动态规划的直接求解阶段就是回溯算法