一茬缩、基本思路
與回溯法一樣，分支限界法也是在問題的解空間樹上搜索問題的解的一種算法吼旧。
二凰锡、分支限界法與回溯法的區(qū)別
兩者很類似，很容易混淆，但有如下顯著的區(qū)別可區(qū)分兩者：
1掂为、求解目標(biāo)不同
回溯法的求解目標(biāo)一般是找出解空間樹中滿足條件的所有解裕膀。
分支限界法則是盡快找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解勇哗。
2昼扛、搜索方式不同
回溯法——>深度優(yōu)先 遍歷結(jié)點(diǎn)搜索解空間樹。
分支限界法——>廣度優(yōu)先或最小耗費(fèi)優(yōu)先搜索解空間樹智绸。
3野揪、存儲(chǔ)空間不同
分支限界法由于加入了活結(jié)點(diǎn)表，所以存儲(chǔ)空間比回溯法大得多瞧栗。因此當(dāng)內(nèi)存容量有限時(shí)斯稳，回溯法的成功率要大一些。
4迹恐、擴(kuò)展結(jié)點(diǎn)的方式不同
分支限界法中挣惰，每個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)變成擴(kuò)展結(jié)點(diǎn)，一旦成為擴(kuò)展結(jié)點(diǎn)便一次性生成其所有子結(jié)點(diǎn)殴边。
區(qū)別小結(jié)：回溯法空間效率更高憎茂，分支限界法由于只需要求到一個(gè)解，所以往往更“快”锤岸。
就拿0/1背包問題做例子竖幔，回溯法求解0/1背包問題實(shí)際上是盲目地搜索解空間樹，回溯法只會(huì)不斷地往下走是偷，雖然通過剪枝函數(shù)能減少一定的計(jì)算拳氢，但是當(dāng)經(jīng)過一個(gè)結(jié)點(diǎn)時(shí)，并不知曉其子結(jié)點(diǎn)會(huì)是怎樣的情況蛋铆，從而盲目繼續(xù)搜索馋评。而分支限界法則不一樣，在經(jīng)過某一結(jié)點(diǎn)時(shí)刺啦，會(huì)根據(jù)限界條件判斷其結(jié)點(diǎn)之下的情況是否能夠?qū)С鲎顑?yōu)解留特，如若不能，直接不走這條路玛瘸。這樣雖然在空間上不占優(yōu)勢(shì)蜕青，但是搜索并不盲目，速度上快了很多糊渊。
三市咆、求解步驟
1、定義解空間（對(duì)解編碼）
2再来、確定解空間樹結(jié)構(gòu)（得解空間樹）
3蒙兰、按BFS廣度優(yōu)先方式搜索解空間樹：
（1）：每個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)變成擴(kuò)展結(jié)點(diǎn)磷瘤。
（2）：由擴(kuò)展結(jié)點(diǎn)生成一步可達(dá)的新結(jié)點(diǎn)。
（3）：在新結(jié)點(diǎn)中刪除不可能導(dǎo)出最優(yōu)解的結(jié)點(diǎn)（限界策略搜变，利用限界函數(shù)）采缚。
（4）：將剩余新結(jié)點(diǎn)加入到活結(jié)點(diǎn)表中。
（5）：在活結(jié)點(diǎn)表中再取每個(gè)結(jié)點(diǎn)（按順序）進(jìn)行擴(kuò)展（分支策略）挠他。
（6）：直到活結(jié)點(diǎn)表為空扳抽。
注：活結(jié)點(diǎn)表通常采用堆結(jié)構(gòu)，當(dāng)求解極大值問題時(shí)用大頂堆殖侵，極小值問題時(shí)用小頂堆贸呢。
四、三個(gè)重要的函數(shù)
1拢军、約束函數(shù)：問題定義時(shí)需給出的約束條件楞陷，如0/1背包問題不能超過其容量。
2茉唉、目標(biāo)函數(shù)：是問題要求解的目標(biāo)函數(shù)固蛾，分支限界法中需給出一個(gè)關(guān)于該函數(shù)的上下界，方便之后剪枝度陆。
3艾凯、限界函數(shù)：用于記錄當(dāng)前結(jié)點(diǎn)之下可得的最優(yōu)值，若超出上下界懂傀，則可放棄該結(jié)點(diǎn)趾诗；還用于活結(jié)點(diǎn)表中結(jié)點(diǎn)排序，限界函數(shù)值最優(yōu)的在第一位蹬蚁，優(yōu)先擴(kuò)展遍歷沧竟。
五、分支限界法的分類
1缚忧、隊(duì)列式分支限界法：在活結(jié)點(diǎn)表中，按照FIFO先進(jìn)先出原則選取下一個(gè)結(jié)點(diǎn)做擴(kuò)展結(jié)點(diǎn)杈笔。
2闪水、優(yōu)先隊(duì)列式分支限界法：活結(jié)點(diǎn)表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)了一個(gè)耗費(fèi)或收益（其實(shí)就是如果擴(kuò)展該結(jié)點(diǎn)，會(huì)帶來多大的效益）蒙具，以此決定結(jié)點(diǎn)的優(yōu)先級(jí)球榆。
六、經(jīng)典案例問題
0/1背包問題禁筏、單源最短路徑問題持钉、最優(yōu)裝載問題。
