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

?? ?回溯是對(duì)狀態(tài)空間樹進(jìn)行深度優(yōu)先搜索，通過約束函數(shù)來去除不符合條件的葉子或是樹枝（如果某個(gè)非葉子節(jié)點(diǎn)不符合約束函數(shù)，以該節(jié)點(diǎn)為根的樹杈就可以直接剪掉了，所以回溯其實(shí)是一個(gè)剪樹枝的過程）。到最后沒有被剪掉的部分，就是全部的可行解，如果要找最優(yōu)解，可以在深度優(yōu)先搜索的過程中一直保存當(dāng)前的最優(yōu)解，當(dāng)遍歷結(jié)束后就是最終的最優(yōu)解。

?? 以前總是認(rèn)為分支限界也是一種剪枝的做法，其實(shí)完全不然——分支限界就完全沒有剪的過程。那么分支限界又是咋回事呢？分支限界的模型和動(dòng)態(tài)規(guī)劃還有回溯比較類似，都是將問題分為若干個(gè)步驟，一步一步來，比如“貨郎擔(dān)”第一步選一個(gè)城市，第二步再選一個(gè)城市；再比如“01背包”，第一步，第一個(gè)物體放進(jìn)去還是不放進(jìn)去，第二步，第二個(gè)物體放進(jìn)去還是不放進(jìn)去……。分支限界，每沒一步之后，都會(huì)求出當(dāng)前分支中目標(biāo)函數(shù)的一個(gè)上界或是下界（當(dāng)求目標(biāo)函數(shù)的最小值時(shí)，就是下界），并將這一步生成的狀態(tài)節(jié)點(diǎn)放入最大（?。┲刀阎小Ｈ缓筮x擇堆頂?shù)哪莻€(gè)節(jié)點(diǎn)，將其從堆中刪除并保存到temp中，繼續(xù)重復(fù)進(jìn)行下一步，當(dāng)完成最后一步時(shí)，那個(gè)狀態(tài)節(jié)點(diǎn)（肯定是個(gè)葉節(jié)點(diǎn)）就是最優(yōu)解。

分支限界