回溯法——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=)