[LeetCode 核心演算法] 用 100 字搞懂 Branch-and-Bound 演算法（分支限界法）
我的理解是，分支限界法 （Branch and Bound）有點貪婪演算法（Greedy Algorithm）和回溯法（Backtracking）的精神。(可見 回溯法（Backtracking）和 貪婪演算法（Greedy Algorithm）文章)。在每次做出選擇當下選擇最優解，並且將找到的最短路徑作為新的約束條件，若在遍歷過程中不符合此約束條件，就退回一步甚至是上幾步的計算重新選擇。
![[LeetCode 核心演算法] 用 100 字搞懂 Branch-and-Bound 演算法（分支限界法）](/content/images/size/w2000/2024/04/image.png)
這篇文章會最精簡解釋 Branch-and-Bound 演算法，是如何找出最優解？
分支限界法 （Branch and Bound）有點貪婪演算法（Greedy Algorithm）和回溯法（Backtracking）的演算法精神。
延伸：可見 回溯法（Backtracking）的解題技巧和「貪婪演算法」（Greedy Algorithm）的解題技巧文章
在每次做出選擇當下選擇「最優解」，
並且將「找到的最短路徑」作為「新的約束條件」。
若在「遍歷過程」中不符合「此約束條件」，
就退回一步甚至是上幾步的計算重新選擇。
參考資料
1. 超圖解！一次搞懂演算法｜入門篇（Python）
2. 使用分支定界的旅行推銷員問題
3. branch and bound（分支定界）算法求解TSP旅行商问题