分支限界法

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

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

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

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

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

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

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

解空間樹的動態搜索

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

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

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

設求解最大化問題，解向量為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) ^[2]  。

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