分支限界法

分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜尋問題的解空間樹。

在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優解的兒子結點被捨棄，其餘兒子結點被加入活結點表中。

此後，從活結點表中取下一結點成為當前擴展結點，並重複上述結點擴展過程。這個過程一直持續到找到所需的解或活結點表為空時為止。

基本介紹

• 中文名：分支限界法
• 外文名：Branch and Bound Method
• 方式：廣度優先
• 形式：最小耗費（最大效益）優先
• 性質：解空間樹
• 學科：數理科學

常見兩種方法

（1）佇列式(FIFO)分支限界法

按照佇列先進先出（FIFO）原則選取下一個節點為擴展節點。

（2）優先佇列式分支限界法

按照優先佇列中規定的優先權選取優先權最高的節點成為當前擴展節點。

方法區別

分支限界法與回溯法的不同

（1）求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優解。

（2）搜尋方式的不同：回溯法以深度優先的方式搜尋解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜尋解空間樹。

解空間樹

解空間樹的動態搜尋

（1）回溯求解0/1背包問題，雖剪枝減少了搜尋空間，但整個搜尋按深度優先機械進行，是盲目搜尋（不可預測本結點以下的結點進行的如何）。

（2）回溯求解TSP也是盲目的（雖有目標函式，也只有找到一個可行解後才有意義）

（3）分支限界法首先確定一個合理的限界函式，並根據限界函式確定目標函式的界[down, up]；然後按照廣度優先策略遍歷問題的解空間樹，在某一分支上，依次搜尋該結點的所有孩子結點，分別估算這些孩子結點的目標函式的可能取值（對最小化問題，估算結點的down，對最大化問題，估算結點的up）。如果某孩子結點的目標函式值超出目標函式的界，則將其丟棄（從此結點生成的解不會比如今已得的更好），否則入待處理表。

設計思路

設求解最大化問題，解向量為X=(x₁,…,x_n)，xi的取值範圍為S_i，|S_i|=r_i。在使用分支限界搜尋問題的解空間樹時，先根據限界函式估算目標函式的界[down, up]，然後從根結點出發，擴展根結點的r1個孩子結點，從而構成分量x₁的r₁種可能的取值方式。

對這r₁個孩子結點分別估算可能的目標函式bound(x₁)，其含義：以該結點為根的子樹所有可能的取值不大於bound(x₁)，即：

bound(x₁)≥bound(x₁,x₂)≥…≥ bound(x₁,…,x_n)

若某孩子結點的目標函式值超出目標函式的下界，則將該孩子結點丟棄；否則，將該孩子結點保存在待處理結點表PT中。

再取PT表中目標函式極大值結點作為擴展的根結點，重複上述。

直到一個葉子結點時的可行解X=(x₁,…,x_n)，及目標函式值bound(x₁,…,x_n)。

搜尋策略

在當前節點（擴展節點）處，先生成其所有的子節點（分支），然後再從當前的活節點（當前節點的子節點）表中選擇下一個擴展節點。為了有效地選擇下一個擴展節點，加速搜尋的進程，在每一個活節點處，計算一個函式值（限界），並根據函式值，從當前活節點表中選擇一個最有利的節點作為擴展節點，使搜尋朝著解空間上有最優解的分支推進，以便儘快地找出一個最優解。分支限界法解決了大量離散最最佳化的問題。