87 lines
2.2 KiB
Markdown
87 lines
2.2 KiB
Markdown
# 回溯法
|
|
|
|
也叫 `试探法`。 是一种选优搜索法，按照选优条件搜索，当搜索到某一步，发现原先选择并不优或达不到目标，就退回重新选择。
|
|
|
|
回溯算法其实就是我们常说的 DFS 算法，本质上就是一种暴力穷举算法。
|
|
|
|
一般步骤
|
|
|
|
1. 针对问题，定义解空间（ 这时候解空间是一个集合，且包含我们要找的最优解）
|
|
2. 组织解空间，确定易于搜索的解空间结构，通常组织成`树结构` 或 `图结构`
|
|
3. 深度优先搜索解空间，搜索过程中用剪枝函数避免无效搜索
|
|
|
|
回溯法求解问题时，一般是一边建树，一边遍历该树；且采用非递归方法。
|
|
|
|
|
|
#### 案例
|
|
|
|
* 迷宫问题
|
|
* 全排列
|
|
|
|
|
|
|
|
## 代码框架
|
|
|
|
```python
|
|
result = []
|
|
def backtrack(路径, 选择列表):
|
|
if 满足结束条件:
|
|
result.add(路径)
|
|
return
|
|
|
|
for 选择 in 选择列表:
|
|
做选择
|
|
backtrack(路径, 选择列表)
|
|
撤销选择
|
|
```
|
|
|
|
|
|
|
|
## 全排列问题
|
|
|
|
> n 个不重复的数，全排列共有 n! 个
|
|
|
|
|
|
```Java
|
|
// 路径：记录在 track 中
|
|
// 选择列表：nums 中不存在于 track 的那些元素
|
|
// 结束条件：nums 中的元素全都在 track 中出现
|
|
void backtrack(int[] nums, LinkedList<Integer> track) {
|
|
// 触发结束条件
|
|
if (track.size() == nums.length) {
|
|
res.add(new LinkedList(track));
|
|
return;
|
|
}
|
|
|
|
for (int i = 0; i < nums.length; i++) {
|
|
// 排除不合法的选择
|
|
if (track.contains(nums[i]))
|
|
continue;
|
|
|
|
// 做选择
|
|
track.add(nums[i]);
|
|
|
|
// 进入下一层决策树
|
|
backtrack(nums, track);
|
|
// 取消选择
|
|
track.removeLast();
|
|
}
|
|
}
|
|
```
|
|
|
|
|
|
|
|
## 八皇后问题
|
|
|
|
8x8的国际象棋棋盘上放置8个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。任意2个皇后都不能处于同一个 横线，纵线，斜线上。
|
|
|
|
分析
|
|
|
|
1. 任意2个皇后不能同一行，也就是每个皇后占据一行，通用的，每个皇后也要占据一列
|
|
2. 一个斜线上也只有一个皇后
|
|
|
|
|
|
|
|
|
|
|