分支結構算法是什麼

分支限界算法：

分支定界 (branch and bound) 算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯算法不同，分支定界算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界算法中，每一個活結點只有一次機會成為擴展結點。

利用分支定界算法對問題的解空間樹進行搜索，它的搜索策略是：

1 ．產生當前擴展結點的所有孩子結點

2 ．在產生的孩子結點中，拋棄那些不可能產生可行解（或最優解）的結點

3 ．將其餘的孩子結點加入活結點表

4 ．從活結點表中選擇下一個活結點作為新的擴展結點。

如此循環，直到找到問題的可行解（最優解）或活結點表為空。

從活結點表中選擇下一個活結點作為新的擴展結點，根據選擇方式的不同，分支定界算法通常可以分為兩種形式：

1 ． FIFO(First In First Out) 分支定界算法：按照先進先出原則選擇下一個活結點作為擴展結點，即從活結點表中取出結點的順序與加入結點的順序相同。

2 ．最小耗費或最大收益分支定界算法：在這種情況下，每個結點都有一個耗費或收益。如果要查找一個具有最小耗費的解，那麼要選擇的下一個擴展結點就是活結點表中具有最小耗費的活結點如果要查找一個具有最大收益的解，那麼要選擇的下一個擴展結點就是活結點表中具有最大收益的活結點。

又稱分支定界搜索法。過程系統綜合的一類方法。該法是將原始問題分解，產生一組子問題。分支是將一組解分為幾組子解，定界是建立這些子組解的目標函數的邊界。如果某一子組的解在這些邊界之外，就將這一子組捨棄（剪枝）。分支定界法原為運籌學中求解整數規劃(或混合整數規劃)問題的一種方法。用該法尋求整數最優解的效率很高。將該法原理用於過程系統綜合可大大減少需要計算的方案數日。

分支定界法的思想是：首先確定目標值的上下界，邊搜索邊減掉搜索樹的某些支，提高搜索效率。

在競賽中，我們有時會碰到一些題目，它們既不能通過建立數學模型解決，又沒有現成算法可以套用，或者非遍歷所有狀況才可以得出正確結果。這時，我們就必須採用搜索算法來解決問題。

搜索算法按搜索的方式分有兩類，一類是深度優先搜索，一類是廣度優先搜索。我們知道，深度搜索編程簡單，程序簡潔易懂，空間需求也比較低，但是這種方法的時間複雜度往往是指數級的，倘若不加優化，其時間效率簡直無法忍受而廣度優先搜索雖然時間複雜度比前者低一些，但其龐大的空間需求量又往往讓人望而卻步。

分支結構算法是什麼

分支結構是根據給定條件成立與否，決定執行不同的語句的算法結構。

分支結構常用的有三種形式，分別是

單分支結構: if

雙分支結構: if-else

多分支結構: if-elif-else