回溯法——N皇后问题与TSP问题
对于一般的问题而言，很多时候无法找到其最优子结构性质或者其不是一个最优化问题，这些问题都是NP的。我们无法采用像动态规划一样的技巧简化求出某个具体解的过程，唯一能做的就是蛮力遍历所有可能的解。在蛮力法的基础上，假如把求每个解的过程组织成一个树状结构，从根节点到叶节点的每次遍历就是一个可能解，那么就可以采用深搜+剪枝的方式来简化计算，在计算之前就知道某些解是不可行的，因此可以说回溯法是特殊情况下对蛮力法的优化。
问题：
N后问题：在N×N的棋盘中放置N个皇后，使得任何两个皇后之间不能相互攻击（不在同一行，同一列，同一对角线），试给出所有的放置方法。
旅行售货员（货郎担TSP）问题：某售货员要到若干城市去推销商品，已知各城市间的路程耗费（代价），如何选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使得总路程耗费最小。
分析：
N皇后问题，不是最优化问题，仅仅是可行解问题，可行解也不唯一。即使将可行解视为最优解，子问题求得了一个可行解，该可行解也不一定构成父问题的可行解。
TSP问题，没有最优子结构，即使求得了一个最优路径，其子问题也不一定是最优的，因为有经过所有节点的要求。
二者都是蛮力求解。
尝试建立树状解空间，用回溯法求解。解空间的表示分为四个步骤：
- 问题解的表示：将问题的解表示成一个n元式 (x1, x2, …, xn) 的形式。
- 显示约束：对分量xi的取值限定。
- 隐示约束：为满足问题的解而对不同分量之间施加的约束。
- 解空间：解向量满足约束条件的所有多元组，构成了问题的一个解空间
因此N皇后问题：
- 问题解表示为(x1, x2, …, xn)
- 显示约束：xi in {1, 2, 3, … ,n}
- 隐示约束：xi和前面的所有x不同行不同列不同斜线，即xi != xj, |i - j| != |xi - xj|
- 解空间为满足显示约束和隐示约束的所有(x1, x2, …, xn)
TSP问题：
- 问题解表示为(x1, x2, …, xn)
- 显示约束：xi in {1, 2, 3, … ,n}
- 隐示约束：(xi, xi+1 ) in E和任意i, k in{1,2, 3, … ,n}, xi != xk， (xn, x1) in E
- 解空间为满足显示约束和隐示约束的所有(x1, x2, …, xn)
解空间的组织形式一般可分为两类，子集树和排列树。当所给的问题是从n个元素，每个元素有m种不同选择的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树，子集树通常有mn个叶结点。当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树，排列树通常有n!个叶结点。
其中，已经被完全访问过的子树的根节点称为黑节点，未被完全访问过的子树的根节点称为灰节点，完全尚未被访问的子树的根节点称为白节点。其中白节点和灰节点统称为活结点，黑节点为死节点。
对于N皇后问题而言，目的是求可行解，而按可行解构造树比较难以实现，因此实际上常常会放宽搜索的范围。易于实现的解空间树就是子集树和排列树，N皇后问题两种树均可使用，其实就是判不判列的问题。
对于TSP问题而言，其可行解比较容易构造，就是排列树，其目的是求可行解中的一个最优解，因此可以用排列树求解。
由此刚好引出了两种剪枝方式。对于N皇后问题而言，假如当前灰节点已经不符合约束了，那么以其为根节点的所有子树都可以舍弃，这是约束函数剪枝；对于TSP问题而言，假如当前灰节点求得的值已经使得后面无论取什么值，得到的可行解都比当前记录的最优解小或者大了，那么以其为根节点的所有子树都可以舍弃，这是限界函数剪枝。
针对限界剪枝，回溯法必须满足多米诺性质，就是限界剪枝一定是正确的：
设P(x1, x2, …, xi)是关于向量<x1, x2, …, xi>的某个性质，那么P(x1, x2, …, xi+1)真蕴含P(x1, x2, …, xi)为真，即
P(x1, x2, …, xi+1) → P(x1, x2, …, xi) (0< i < n) (n为向量维数)
翻译过来就是子问题不对了，父问题也不能对（逆否命题）。
代码：
代码有挺多细节的，还是背一下模板比较好
#include<bits/stdc++.h>
using namespace std;
// 判断pos层选择的位置是否和前面已选的冲突
bool check(int res[],int pos){
for(int i = 1;i < pos;i++){
if((abs(i - pos) == abs(res[i] - res[pos])) || (res[pos] == res[i])){
return false;
}
}
return true;
}
// 子集树求解N皇后问题，递归写法
// 输入：初始层号pos，皇后数量n，结果记录数组res[]
void queenBacktrace(int pos,int n,int res[]){
// 假如求得了一个可行解，那就输出这个解
// res最后的结果不是最后一个可行解，这一点特别注意
if(pos>n){
for(int i = 1;i <= n;i++)
cout<<res[i]<<" ";
cout<<endl;
}else{
// 遍历当前节点的所有扩展节点
for(int i = 1;i <= n;i++){
// 假如该扩展节点满足要求
res[pos] = i;
if(check(res, pos)){
res[pos] = i;
queenBacktrace(pos+1, n, res);
}
}
}
}
// 子集树求解N皇后问题，迭代写法
// 输入：皇后数量n，结果记录数组res[]
void queenIterate(int n, int res[]){
// 初始从第一行开始
int pos = 1;
// 需要手动记录每一层的中断返回位置
int f[9];
// memset(f, 1, sizeof(f));
// memset按照字节赋值，只能赋值0或-1
for(int i = 0;i <= n;i++)
f[i] = 1;
// 难点在于何时退出while循环，观察递归可以发现，递归最后的动作是完成了第一行的所有扩展节点
// 只有当某个节点的所有扩展节点都遍历完时，才会退回这个节点的上一层
// 因此最后将会退回到第0层，递归终止
while(pos>0){
// 假如还有没遍历的扩展节点
if(f[pos] <= n){
// 遍历当前节点的所有未检查的扩展节点
// 与递归的区别，没有递归自然的入栈出栈和记录断点了
for(;f[pos] <= n;f[pos]++){
res[pos] = f[pos];
// 假如该节点满足要求
if(check(res, pos)){
// 假如求得了一个可行解，那么就输出这个解
// 不能像递归一样pos++然后统一到下一层处理，因为数组下标会越界
if(pos==n){
for(int i = 1;i <= n;i++)
cout<<res[i]<<" ";
cout<<endl;
}else{
pos++;
// 易错点，每一层有多个独立的子树，这些子树公用一个f[]
// 假如新来到一棵子树，那必须要重置这颗子树的f[]
// 否则f[]还是上一棵子树的值
f[pos] = 0;// 最坑的地方，这个循环出去的时候还有一次++，因此初始化为0
}
}
}
}else{// 也可以在每一个子树遍历完之后清除f[]
// 所有的扩展节点都遍历完了，那就回退一层
pos--;
f[pos]++;//易错点
}
}
}
int main(){
int n = 8;
int res[9];
memset(res, 0, sizeof(res));
queenIterate(n, res);
cout<<endl;
queenBacktrace(1, n, res);
}
#include<bits/stdc++.h>
using namespace std;
#define MAXN 105
#define INF 0x3f3f3f
// 邻接矩阵存储
int m[MAXN][MAXN];
// 结果记录数组，下标为第几个点，对应的是选的哪个点
int res[MAXN];
// 记录最优解
int bestRes[MAXN];
// 最优解的大小
int minRes = INF;
// 检查当前这一步选出的结果是否满足约束
// 当前共选了pos个点，一共有n个待选点
bool check(int pos,int n){
// 就一个点，肯定是可行解，一般也不会用到，因为第一次就是从第二个点开始算的
if(pos < 2) return true;
// pos加入后，若当前的解还是处于中间过程中，检查新加入的点和上一个加入的点之间有没有连通
if(pos<n && m[res[pos-1]][res[pos]]!=INF) return true;
// pos加入后，若当前的解就是最终的解，检查新加入的点和上一个加入的点之间有没有连通，还要检查是否能构成一个闭合的回路
if(pos==n && m[res[pos-1]][res[pos]]!=INF && m[res[pos]][res[1]]!=INF) return true;
return false;
}
// 计算当前部分解的大小
int sum(int pos,int n){
int nowRes = 0;
if(pos < n){
for(int i = 2;i <= pos;i++){
nowRes += m[res[i]][res[i-1]];
}
return nowRes;
}else{
for(int i = 2;i <= n;i++){
nowRes += m[res[i]][res[i-1]];
}
nowRes += m[res[n]][res[1]];
return nowRes;
}
}
// 限界函数
bool bound(int pos,int n){
if(pos < 2) return true;
if(pos <= n && sum(pos, n) <= minRes) return true;
return false;
}
// 排列树求解TSP问题，递归
// 输入：起始城市是第pos个，默认从2开始，一共有n个城市
void TSPbacktrace(int pos,int n){
// 假如找到了一个可行解
if(pos>n){
// 假如这个可行解比当前记录的最小可行解还要小
if(sum(pos, n) < minRes){
minRes = sum(pos, n);
// 记录可行解为当前最优解
for(int i = 0;i <= n;i++){
bestRes[i] = res[i];
}
}
}else{
// 遍历所有的扩展节点
// 由于是排列树，因此每次要选取没有选过的那个点
// 为了方便，可以把已经选过的点放在一起，每次从没选过的那个点开始选就可以了
// 为此需要做两点，第一点，不能单纯的按序号从小到大的顺序来遍历所有点了，因为选过的点可能是乱序的，因此要将res初始化为序号从小到大
// 第二点，每次选了某个点后，将该点与当前res所对应的那个序号的点交换，这样就保证了选过的点放在一起
for(int i = pos;i <= n;i++){
swap(res[pos], res[i]);
// 假如该点满足条件，约束函数+限界函数
if(check(pos, n) && bound(pos, n)){
TSPbacktrace(pos+1, n);
}
// 注意恢复现场，已经选过这个点了
swap(res[pos], res[i]);
}
}
}
// 排列树求解TSP问题，迭代
// 输入：起始城市是第pos个，默认从2开始，一共有n个城市
void TSPiterate(int pos,int n){
// 记录每一层访问到了哪个扩展节点
int f[n+1];
// 排列树和子集树的初始化不同
for(int i = 0;i <= n;i++){
f[i] = i;
}
while (pos >= 2) {
for(;f[pos] <= n;f[pos]++){
swap(res[pos], res[f[pos]]);
if(check(pos, n) && bound(pos, n)){
// 找到了可行解
if(pos == n){
if(sum(pos, n) < minRes){
minRes = sum(pos, n);
// 记录可行解为当前最优解
for(int i = 0;i <= n;i++){
bestRes[i] = res[i];
}
}
// 理论分析应该有三种恢复现场的swap
// 2. 选了这个扩展节点，这个扩展节点还是叶节点，那么将不会向更深一层进发，会选下一个扩展节点，和第一种没选的情况同理
//（这里已经是最后一个位置了实际上没有交换）
//swap(res[pos], res[f[pos]]);
}else{
pos++;
f[pos] = pos-1;// 排列树和子集树的初始化不同
}
}else{
// 1.没选这个扩展节点，在check完之后就应该换回来
swap(res[pos], res[f[pos]]);
}
}
// 当前子树被遍历完了，也可以不写在for循环完成的地方而是写成八皇后代码里的那种单独判断
pos--;
// 3. 选了这个扩展节点，这个扩展节点是内节点，在其子树访问完成后，需要回复现场，否则肯定出错
swap(res[pos], res[f[pos]]);
f[pos]++;
}
}
int main(){
int n = 4;
// 初始化操作
for(int i = 0;i <= n;i++){
res[i] = i;
bestRes[i] = 0;
for(int j = 0;j <= n;j++){
m[i][j] = INF;
}
}
m[1][2] = 10;
m[1][3] = 6;
m[1][4] = 4;
m[2][3] = 5;
m[2][4] = 10;
m[3][4] = 20;
m[2][1] = 10;
m[3][1] = 6;
m[4][1] = 4;
m[3][2] = 5;
m[4][2] = 10;
m[4][3] = 20;
// pos从第二个城市开始，因为第一个城市已经默认选择了第一个编号的城市
TSPbacktrace(2, n);
//TSPiterate(2, n);
for(int i = 1;i <= n;i++)
cout<<bestRes[i]<<" ";
cout<<endl<<minRes;
}
复杂度分析：
时间复杂度下界视为解空间树叶节点的个数，因此
N皇后问题：Ω(nn)
TSP问题：Ω((n-1)!) = Ω(n!)
时间复杂度的上界比较难以分析，需要考虑其约束函数和限界函数，在这篇博客和后面的几篇回溯博客中，约束函数和限界函数的写法其实包含了重复的计算，但是分析时间复杂度的时候是按照最简的计算方式来分析的。
N皇后问题最差情况下每个节点要与其他N个节点比较，这是O(n)，节点数量级为O(nn)级，因此时间复杂度为
O(nn)
TSP问题约束函数和限制函数都是O(1)，因此时间复杂度为
O(n!)
空间复杂度都是O(n2)
P.S.回溯法写起来真的很难想，写非递归的时候全程如下表情：
![求解最大子段和问题----分治 蛮力 dp[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)