以下是5個Branch and Bound的問題:
在路徑規劃中，你需要找到通過一系列城市的最短路徑。使用Branch and Bound算法可以幫助你找到最短的路徑。
在資源分配問題中，你需要將可用資源分配給多個項目，以最大化全局效益。Branch and Bound算法可以幫助你找到最優解。
在排程問題中，你需要在多個工作之間分配時間，以最小化完成時間。Branch and Bound算法可以幫助你減少總體完成時間。
在0-1背包問題中，你需要填充一個有限大小的背包，以最大化價值。Branch and Bound算法可以幫助你找到最理想的裝載方案。
在數據壓縮中，你需要找到最小的壓縮方式，以減少數據量。Branch and Bound算法可以幫助你找到最佳的壓縮方法。
Branch and Bound（分支定界法）是一種求解最優解問題的算法，通常用於組合優化，如旅行商問題、背包問題等。該算法利用了一個重要原則：通過一系列分支和限制條件的不斷縮小搜索空間，同時利用上界和下界對每個搜索分支進行評估和剪枝，以找到最優解。
具體來說，Branch和Bound的搜索過程分為以下幾步：
分支：從初始狀態出發，不斷將問題拆分為若干個子問題，即各種可能的解決途徑。對於背包問題，一個可能的拆分方法是選或不選某個物品。
限制條件：給每個子問題限制條件，從而使得搜索空間逐漸地收斂。對於背包問題，限制條件是背包容量必須小於等於總容量。
上界估計：對每個子問題計算一個最大可行解的上界，用於和問題的實際解進行比較，確定是否需要進一步搜索。對於背包問題，上界可能是已經被選中的物品總價值加上剩餘物品中價值最大的物品的價值。
下界估計：對每個子問題計算一個最小可行解的下界，用於對搜索樹進行剪枝，即丟棄那些估值低於當前已知最優解的搜索分支。對於背包問題，下界可能是已選擇物品的總價值加上還能放入背包的最大價值。
搜索回溯：在搜索分支全部完成後，輸出最優解。如果搜索到某個分支的上界小於已知最優值，則剪枝退出。
舉例來說，假設我們要用Branch and Bound算法，解決一個旅行商問題，即從一個城市出發，依次經過其他城市回到原城市。已知每個城市之間的距離，求最短路程。
第一步是分支，我們從任意一個城市出發，可以分別選擇下一個要訪問的城市。例如，從城市A出發，我們可以選擇去B、C、D等城市。
第二步是限制條件，我們需要給每個分支設置約束條件，例如當前已經經過的城市不能再次經過。
第三步是上界估計，對於每個分支，我們需要計算已經選擇的路徑長度與未選擇的城市到起點的距離之和，同時加上一個下界估計。
第四步是下界估計，我們需要計算剩餘城市之間的最小距離，假設路徑已訪問過的城市均為i1，i2， …，ik，剩下未訪問的城市為j1， j2， …，jm，則下界估計為：
LB = Sum(D i j ) + min(D i1 k + D k j1 , D i2 k + D k j2 , … , D ik k + D k jm )
其中，D i j 表示城市i到城市j的距離。我們選擇未訪問城市中到目前為止距離最近的一個城市，加入已知路徑。以這種方式對每個分支進行下界估計。
第五步是回溯搜索，在已經遍歷整個搜索樹後，輸出最優的路徑及其長度。
總之，Branch and Bound是一種高效的求解組合優化問題的算法。通過不斷縮小搜索空間並且對每個搜索分支進行剪枝，算法可以在較短的時間內找到最優解。
答案: Kruskal algorithm 和 Prim’s algorithm
答案: Knapsack問題的分支限界解法
答案: 計算每個節點的大小並使用分支限制法
答案: 已知經過點集將事件分解為小問題的方法
答案: Branch and Bound解法