回溯法（Backtracking）& 分支定界法（Branch and Bound）

「回溯法（backtracking）」是經過優化的暴力法、「分支界定法（branch and bound）」透過制定上界或下界更快找到最佳解，兩者可以混用，但各有其較為適合的使用時機。

本文除簡介兩種方法各自的運作方式外，並以「0/1 背包問題（0/1 knapsack problem）」演示兩者在處理相同問題時的差異性。

回溯法（backtracking）

將每種可能性列出，但只要算到絕對不可行的結果就退回、不再依照該路徑往下計算，跟傳統的「暴力法」相比，可以省去計算行不通的解之時間。

範例一：Permutations (Leetcode 46.)

以「A、B、C」三字母來說，要找出所有排列可能性，可以用「暴力法」列舉如下，一共可以找到六種排列方式，如黃字所示：

然而，因為一個字母只能出現一次，算到某些步驟時，其實就會發現：順著該路徑再怎麼往下算，都不會找到可行解，因此可以就此打住，往回退一步再找出其他可能，減少總運算步驟，這就是「回溯法」的精神：

「Permutations」通用解法

上述方法僅適用於三個字母的排列，若要推廣至排列任何長度，可改用「i」與「start」兩個「pointer」輔助，用迴圈分別讓「start」與「i」以不同步調頭跑到尾，再一一將兩者所指的項目對調，實現：

範例二：N-Queens (Leetcode 51.)

「N 皇后問題（n queens problem）」是可用回溯法求解的經典題型。在西洋旗的規則中，若要讓兩皇后無法吃掉彼此，則一皇后必不在另一皇后縱向、橫向或斜對角。

以下圖來說，若灰旗為皇后，則另一皇后必不可在紅線所經的所有格子，僅能在綠底格才不會被吃掉。

「四皇后問題」解題步驟

1. 先將第一枚棋子放入第一行、第一列中：
   

2. 在第二行放第二枚棋子，但發現第一列不能放：
   

3. 將第二行棋子往下移一列，發現還是不能放：
   

4. 將第二行棋子再往下移一列，發現可以放後確定位置：
   

5. 將第三行的棋子放到可行的位置，發現全部走完後，沒有地方可以放：
   

6. 往回一步調整第二行棋子的位置，讓第三行的棋子有位置可放：
   

7. 將第四行的棋子放到可行的位置，發現全部走完後，沒有地方可以放：
   

8. 往回調整第三、第二行棋子位置，發現無其他地方可放，於是改調整第一行棋子位置：
   

9. 將第二行棋子放到新的位置：
   

10. 將第三行棋子放到新的位置：
    

11. 將第四行棋子放到可行位置：
    

12. 完成「四皇后問題」的其中一解：
    

若再將第一行棋子往下移一格，可用相同方法求出「四皇后問題」的第二個解如下：

若再將第一行的棋子往下移一格，將發現並無對應的可行解，其中一行必無法有位置可放棋：

若將「四皇后問題」延伸至「八皇后問題」、「十六皇后問題」，甚至到「N 皇后問題」，都可以用「回溯法」一一處理，雖然仍屬時間複雜度極高的「暴力法」，但在找到更有效的演算法可以處理前，回溯法已經是所有暴力解法中最優者。

範例三：0/1 Knapsack Problem

跟使用貪婪演算法（Greedy Algorithm）處理的「fractional knapsack problem」不同的是，這裡的物品只有「取」或「不取」兩種選擇，任一物品無法只取其中一部分。

假設有一背包，最多可裝 9 公斤的物品，另有三物品價值（value）與重量（weight）資訊如下：

若使用「回溯法」，則只要總重量超重就不再往下計算，最後可求得在只取 A、不取 B 與 C 的情況下，可讓背包內物品的總價值為最高又不會超重。

分支定界法（Branch and Bound）

透過計算特定條件下可達成的界線，用以決定是否要順著該條件往下走；如果滿足該條件的上界或下界不比原本狀態優，即可以停止計算該方向的所有可能。

範例：0/1 Knapsack Problem

一樣以上述的「0/1 Knapsack Problem」為例，除了計算到超重就不再往下算外，另計算將其當作「fractional knapsack problem」處理時，可能組成的最高價值。

在下圖中，每個項目除了價值（value）與重量（weight）組合資訊外，另有下列兩項資訊：

1. Lower Bound：在符合當時挑選條件、每項物品又不能僅取一部分時，可以組成的最高價值。
2. Max Value Possible：將其視為「fractional knapsack problem」、每項物品都可以只取一部分時，可以組成的最高價值。
   

由上圖可以發現，在不取 A 時，就算把背包可裝的重量 9 公斤用好用滿，可組成的最高價值還比原本低，也就是說，只要不取 A，就不可能產生最高價值的組合，因此順著該方向往下的所有可能都可以忽略不算。

去除不取 A、再排除超重的情況後，可發現最佳且唯一的選擇是只取 A，不取 B、C，跟用回溯法求得的結果相同，但運算步驟又更少一些。

「回溯法」與「分支定界法」比較

「回溯法」與「分支定界法」是演算法的兩大策略，各有其適合的使用時機，若要交替使用也並非不行，但操作起來會較為複雜。

1. 使用函數：回溯法使用「可行性函數（feasibility function）」決定是否可以照原本方向往下列出不同可能；分支定界法除了用「可行性函數」決定是否繼續往下走外，另用「有界函數（bounding function）」決定符合當下狀況的上界或下界，若當下出的情況超出原本的上界或下界，就不再往下算。
2. 處理方式：回溯法一一探索不同可能，確定不可行就往回走，類似「深度優先搜尋（depth-first-search, DFS）」；分支定界法則在進入每個階段後，就判斷該階段的不同可能是否可行，一層一層判斷就像「廣度優先搜尋（breadth-first-search, BFS）」。
3. 適合時機：回溯法適合在給定限制條件下做出最佳的「決定」，通常用於「約束滿足問題（constraint satisfaction problems, CSPs）」，如上述範例的「N 皇后問題（n queens problem）」，以及屬於「NP 完全問題（NP-Complete problem）」的「哈密頓路徑問題（Hamiltonian path problem）」；分支定界法適合處理「組合最佳化問題（combinatorial optimization problems）」，例如上述範例的「0/1 背包問題（0/1 knapsack problem）」，以及屬於「NP 完全問題（NP-Complete problem）」的「旅行推銷員問題（travelling salesman problem, TSP）」。

兩種演算法策略的比較表如下：