以前一直以為分支限界跟回溯差不多，最近又看了看算法，其實兩者大不一樣。

?? ?回溯是對狀態空間樹進行深度優先搜索，通過約束函數來去除不符合條件的葉子或是樹枝（如果某個非葉子節點不符合約束函數，以該節點為根的樹杈就可以直接剪掉了，所以回溯其實是一個剪樹枝的過程）。到最后沒有被剪掉的部分，就是全部的可行解，如果要找最優解，可以在深度優先搜索的過程中一直保存當前的最優解，當遍歷結束后就是最終的最優解。

?? 以前總是認為分支限界也是一種剪枝的做法，其實完全不然——分支限界就完全沒有剪的過程。那么分支限界又是咋回事呢？分支限界的模型和動態規劃還有回溯比較類似，都是將問題分為若干個步驟，一步一步來，比如“貨郎擔”第一步選一個城市，第二步再選一個城市；再比如“01背包”，第一步，第一個物體放進去還是不放進去，第二步，第二個物體放進去還是不放進去……。分支限界，每沒一步之后，都會求出當前分支中目標函數的一個上界或是下界（當求目標函數的最小值時，就是下界），并將這一步生成的狀態節點放入最大（小）值堆中。然后選擇堆頂的那個節點，將其從堆中刪除并保存到temp中，繼續重復進行下一步，當完成最后一步時，那個狀態節點（肯定是個葉節點）就是最優解。

分支限界