前言
首先我们来熟悉下前面学习的回溯框架:
- 路径:就是我们当前做出的选择
- 选择列表:就是我们当前可以做出的选择
- 结束条件:也就是到达决策树底部,无法再做出选择
result=[]; def backtrack(路径,选择列表) if 满足结束条件: result.add(路径); return for 选择 in 选择列表 做选择 backtrack(路径，选择列表) 撤销选择
N皇后问题
这道题很经典,相信很多小伙伴都见过,并且挺畏惧的,今天我们就跟着我们前面学的模板走一遍,你会豁然开朗,更加深刻的理解对于这个模板·的运用
首先剖析题目:
就是给定n*n的棋盘,在上面放置n个棋子,并且保证同一行，同一列,左上角,左下角,右上角，右下角只有一个棋子,下面我们来画图分析
首先我们从第一行第一个格子走,会发现走到第二行就走不下去了,那我们就撤销退回去,另辟其路
到这里又不行了,又要去撤销往回退,第二行已经没法选了,只能撤销到第一行，重新选
成功了！！这只是一种情况,还要继续去找其他类,。这里就不再找下去了,有兴趣的同学可以下去试试通过上面的画图了解，应该有点思考了,【路径]不就是小于这些行已经成功放置的皇后嘛,【选择列表]某一行的所有列都是皇后的选择.(不过这里有一些限制条件,下面分析)【结束条件]当超过最后一行即可;这里我们来分析下限制条件check:
行和列很好看,主要分析下对角线上的
会发现左对角线 x-y=1; 右对角线:x+y=5; ok，到这里我们就分析结束了,下面我们来看代码吧
#include<iostream> using namespace std; //这里用4*4来做演示 int n = 4; int ants; int rec[4]; //bool check(int x, int y) //{ // for (int i = 0; i < n; i++) // { // if (rec[i] == y)//同一列 // { // return false; // } // if (rec[i] + i == x + y)//右对角线 // { // return false; // } // if (i - rec[i] == x - y)//左对角线 // { // return false; // } // } // return true; //} void dfs(int row)//row当前处理的行 { if (row == n)//结束条件 { ants++; return; } for (int col = 0; col < n; col++) { bool ok = true; for (int i = 0; i < row; i++) { //检查是否合法,与check一样 if (rec[i] == col || i + rec[i] == row + col || rec[i] - i == col - row) { ok = false; break; } } if (ok) { rec[row] = col;//做选择 dfs(row + 1);//进入下一行决策 rec[row] = 0;//回溯,撤销选择 } } } int main() { dfs(0); cout << ants << endl; return 0; }
牛刀小试
最后总结
回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：
def backtrack(...): for 选择 in 选择列表: 做选择 backtrack(...) 撤销选择
写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。
某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。而今天的两个问题，都没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的。
