什麼是分支定界法？基本思想是什麼？一般用於解決什麼問題

1樓：匿名使用者

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

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

1 ．產生當前擴充套件結點的所有子結點；

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

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

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

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

分支定界法本質還是一種列舉法，但是是隱列舉法。它是整數規劃領域中非常重要的一類演算法思想。是很多重要演算法的源頭。它能解決的實際問題很多，最著名的一個應該就是求解揹包問題。

2樓：匿名使用者

用c#程式設計通過分支定界法解決揹包問題。急急急。 using system; using 問題解決函式 ///

分支限界法的基本思想是什麼？

3樓：匿名使用者

分支限界法類似於回溯法，也是一種在問題的解空間樹t上搜尋問題的演算法。但分支限界法的求解目標是找出滿足約束條件的一個最優解。搜尋策略是廣度優先，既在擴充套件結點點，先生成其所有的兒子結點（分支），然後再從當前的活結點表中選擇下一個擴充套件結點。

在每一個活結點處，計算一個函式值（限界），並根據這些已計算出的函式值，從當前活結點佇列中選擇一個最有利的結點作為擴充套件結點，使搜尋朝著解空間樹上最優解的分枝推進，以便儘快找到一個最優解。