一、回溯法
1. 基本思想與解題步驟
基本思想：
把問題的解空間轉化成了圖或者樹的結構表⽰，然後使⽤深度優先搜尋政策進⾏周遊，周遊的過程中記錄和尋找所有可⾏解或者最優解。
解題步驟：
- 針對所給問題，定義問題的解空間；
- 确定易于搜尋的解空間結構；
- 以深度優先⽅式搜尋解空間，并在搜尋過程中⽤剪枝函數避免⽆效搜尋。
2. ⼦集樹與排列樹
2.1 ⼦集樹
當所給問題是從n個元素的集合S中找出S滿⾜某種性質的⼦集時，相應的解空間樹稱為⼦集樹。例如從n個物品的0-1背包問題(如下圖)所相應的解空間樹是⼀棵⼦集樹，這類⼦集樹通常有2^n 個葉結點，其結點總個數為2^(n+1)-1 。周遊⼦集樹的算法需O(2^n)計算時間。
void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=0;i<=1;i++) {
x[t]=i;
if (constraint(t)&&bound(t)) backtrack(t+1);
}
}
2.2 排列樹
當所給問題是确定n個元素滿⾜某種性質的排列時，相應的解空間樹稱為排列樹。例如旅⾏售貨員問題(如下圖)的解空間樹是⼀棵排列樹，這類排列樹通常有n!個葉結點。周遊⼦集樹的算法需O(n!)計算時間。
void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=t;i<=n;i++) {
swap(x[t], x[i]);
if (constraint(t)&&bound(t)) backtrack(t+1);
swap(x[t], x[i]);
}
}
2.3 滿m叉樹
找滿足某種特性的n個元素取值的一個組合。
這類問題的解空間稱為滿m叉樹。
n皇後問題
圖的m着色問題
最小機器設計問題
參考學習：回溯法、子集樹、排列數、滿m叉樹
除了葉節點之外，每一個節點都有3個子節點，這就代表的3種選擇。
3. 回溯算法的實作：遞歸與疊代
一說：
二說：
3.1 遞歸
//針對N叉樹的遞歸回溯⽅法
void backtrack (int t)
{
if (t>n) output(x); //葉⼦節點，輸出結果，x是可⾏解
else
for i = 1 to k//目前節點的所有⼦節點
{
x[t]=value(i);//每個⼦節點的值指派給x
//滿⾜限制條件和限界條件
if (constraint(t)&&bound(t))
backtrack(t+1);//遞歸下⼀層
}
}
3.2 疊代（遞推）
void iterativeBacktrack ()
{
int t=1;
while (t>0) {
if(ExistSubNode(t)) //目前節點的存在⼦節點
{
for i = 1 to k //周遊目前節點的所有⼦節點
{
x[t]=value(i);//每個⼦節點的值指派給x
if (constraint(t)&&bound(t))//滿⾜限制條件和限界條件
{
//solution表⽰在節點t處得到了⼀個解
if (solution(t)) output(x);//得到問題的⼀個可⾏解，輸出
else t++;//沒有得到解，繼續向下搜尋
}
}
}
else //不存在⼦節點，傳回上⼀層
{
t--;
}
}
}
4.避免無效搜尋的政策
在搜尋過程中，通常采⽤兩種政策避免⽆效搜尋：
- ⽤限制條件剪除得不到可⾏解的⼦樹
-
⽤⽬标函數剪取得不到最優解的⼦樹
（這兩種⽅式統稱為：剪枝函數）
5.經典案例問題
- 0-1背包問題（子集樹）： 回溯法求0/1背包的解空間樹
算法分析五：回溯法與分⽀限界法 算法分析五：回溯法與分⽀限界法 - 裝載問題：
- 圖的m着⾊問題：
- n後問題（n叉樹）：
- 貨郎問題（排列數）：
二、分⽀限界法
1. 基本思想與解題步驟
問題的解空間樹是表⽰問題解空間的⼀棵有序樹，常見的有⼦集樹和排列樹，滿m叉樹。
在搜尋問題的解空間樹時，分⽀限界法和回溯法的主要差別在于它們對目前擴充節點所采⽤的擴充⽅式不同。在分⽀限界法中，每⼀個活結點隻有⼀次機會成為擴充節點。活結點⼀旦成為擴充節點，就⼀次性産⽣其所有⼉⼦節點。在這些⼉⼦節點中，導緻不可⾏解或導緻⾮最優解的⼉⼦節點被舍棄，其餘⼉⼦節點被加⼊活結點表中。此後，從活結點表中取下⼀節點為目前擴充節點。并重複上述節點擴充過程。這個過程移⾄持續到找到所需的解或活結點表為空為⽌。
總結如下
-
基本思想：
分⽀限界法常以⼴度優先或以最⼩耗費有限的⽅式搜尋問題的解空間樹。
-
解題步驟
1.（定義問題解空間，确定解空間組織結構，）按廣度優先周遊的方法求解空間樹。
2.在求解過程中，每⼀個活結點隻有⼀次機會成為擴充節點。活結點⼀旦成為擴充節點，就⼀次性産⽣其所有⼉⼦節點。
4.在這些⼉⼦節點中，導緻不可⾏解或導緻⾮最優解的⼉⼦節點被舍棄，其餘⼉⼦節點被加⼊活結點表中。此後，從活結點表中取下⼀節點為目前擴充節點。
4.重複上述節點擴充過程。這個過程移⾄持續到找到所需的解或活結點表為空為⽌。
注：擴充節點、活結點、死結點：所謂擴充節點，就是目前正在求出它的子節點的節點，在深度優先搜尋中，隻允許有一個擴充節點。活結點就是通過與限制函數的對照，節點本身和其父節點均滿足限制函數要求的節點；死結點反之。由此很容易知道死結點是不必求出其子節點的（沒有意義）。
2. 分支限界法的分類
從活結點表中選擇下⼀擴充節點的不同⽅式導緻不同的分⽀限界法。最常見的有以下兩種⽅式。
-
隊列式分⽀限界算法
隊列式分⽀限界法将活結點表組織成⼀個隊列，并按隊列的先進先出原則選取下⼀個節點為目前擴充節點。
在活結點表中，按照FIFO先進先出原則選取下一個結點做擴充結點。
-
優先隊列式分⽀限界算法
優先隊列式的分⽀限界法将活結點表組織成⼀個優先隊列，并按優先隊列中規定的節點優先。
活結點表中的每個結點對應了一個耗費或收益（其實就是如果擴充該結點，會帶來多大的效益），以此決定結點的優先級。 注：通常采用堆實作。
3. 分支限界法與回溯法的相同之處
- 都是在問題的解空間樹中搜尋問題解的算法
4. 分支限界法與回溯法的差別
- 求解目标不同：
- 回溯法的求解目标是找出空間樹中滿足限制條件的所有解。
- 分支限界法的求解目标則是找出滿足限制條件的一個解，或是在滿足限制條件的解中找出（使某一目标函數值達到極大或極小的解，即在）某種意義下的最優解。
- 搜尋方式不同
- 回溯法:深度優先周遊結點搜尋解空間樹。
- 分支限界法:廣度優先或最小耗費有限搜尋解空間樹。
- 存儲空間不同
- 分支限界法由于加入了活結點表，是以存儲空間比回溯法大得多。是以當記憶體容量有限時，回溯法的成功率要大一些。
- 回溯一般使用堆棧，而分支限界使用隊列或優先隊列.
- 擴充結點的方式不同
- 回溯法中，活結點的所有可行子結點被周遊後才從棧中彈出;
- 分支限界中，每個活結點隻有一次機會變成擴充結點，一旦成為擴充結點便一次性生成其所有子結點。
差別小結：回溯法空間效率更高，分支限界法由于隻需要求到一個解，是以往往更“快”。
5. 經典案例問題
0/1背包問題、單源最短路徑問題、最優裝載問題。
一般做題時會出現的問題：
1.構造求解該問題的解空間樹。
2.給出隊列式分支限界算法的求解過程。
3.設計該問題的分支限界算法并分析其時間複雜度。
- 0/1背包問題
- 待續
參考：連結1，連結2
增：