分支限界法

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

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

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

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

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

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

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

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

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

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