什么是分支限界法

分支限界法是一種用于求解最優化問題的算法，其核心思想是通過剪枝策略減少搜索空間。
分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜索問題的解空間樹。
在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被加入活結點表中。
此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所需的解或活結點表為空時為止。

設計思路

設求解最大化問題，解向量為X=(x1,…,xn)，xi的取值范圍為Si，|Si|=ri。在使用分支限界搜索問題的解空間樹時，先根據限界函數估算目標函數的界[down, up]，然后從根結點出發，擴展根結點的r1個孩子結點，從而構成分量x1的r1種可能的取值方式。
對這r1個孩子結點分別估算可能的目標函數bound(x1)，其含義：以該結點為根的子樹所有可能的取值不大于bound(x1)，即：
bound(x1)≥bound(x1,x2)≥…≥ bound(x1,…,xn)
若某孩子結點的目標函數值超出目標函數的下界，則將該孩子結點丟棄；否則，將該孩子結點保存在待處理結點表PT中。
再取PT表中目標函數極大值結點作為擴展的根結點，重復上述。
直到一個葉子結點時的可行解X=(x1,…,xn)，及目標函數值bound(x1,…,xn)

常見分支限界法

（1）隊列