- 定義：
分支限界算法是按照廣度優(yōu)先的方式對(duì)解空間樹（狀態(tài)空間樹）進(jìn)行搜索驹闰，從而求得最優(yōu)解的算法熔恢。在搜索的過(guò)程中贾费，采用限界函數(shù)（bound function）估算所有子節(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值穿铆，從而選擇使目標(biāo)函數(shù)取極值（極大值或者極小值）的節(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)（如果限界值沒有超過(guò)目前的最優(yōu)解艺演，則剪枝）進(jìn)行下一步搜索（重復(fù) BFS -> 計(jì)算所有子節(jié)點(diǎn)限界 -> 選擇最優(yōu)子節(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)的過(guò)程）热芹，從而不斷調(diào)整搜索的方向贱傀，盡快找到問(wèn)題的最優(yōu)解。
（ps：回溯算法求出滿足約束的所有可行解伊脓，分支限界求出滿足約束的解中使得目標(biāo)函數(shù)達(dá)到極值的最優(yōu)解）
分支限界的思想類似于：圖的廣度優(yōu)先搜索府寒，樹的層序遍歷。
- 分支限界算法和回溯算法的不同點(diǎn)：
（1）分支限界算法與回溯算法在子結(jié)點(diǎn)的擴(kuò)展方式上不同：
回溯一般采用輪流遍歷子節(jié)點(diǎn)的方式擴(kuò)展結(jié)點(diǎn)。
分支限界則采用活結(jié)點(diǎn)的方式株搔，一次性對(duì)所有的可行子節(jié)點(diǎn)進(jìn)行擴(kuò)展剖淀，估算子節(jié)點(diǎn)目標(biāo)函數(shù)的可能值，如果該子節(jié)點(diǎn)的目標(biāo)函數(shù)值差于當(dāng)前最優(yōu)解纤房，則丟棄纵隔；否則將其加入活葉子表，依次從表中選取使目標(biāo)函數(shù)取極值的節(jié)點(diǎn)作為當(dāng)前的擴(kuò)展結(jié)點(diǎn)炮姨。重復(fù)這一過(guò)程捌刮，直到找到最優(yōu)解。
（2）分支限界算法與回溯算法在解空間樹的搜索方式上不同：
回溯采用深度優(yōu)先搜索的方式去搜索解空間樹剑令。搜索過(guò)程中糊啡，對(duì)所有的子節(jié)點(diǎn)輪流進(jìn)行深度優(yōu)先搜索，一旦發(fā)現(xiàn)有不滿足約束的子節(jié)點(diǎn)吁津，則對(duì)該子節(jié)點(diǎn)為根的子樹進(jìn)行剪枝；否則就從該子節(jié)點(diǎn)深度優(yōu)先搜索堕扶，直到搜索到一個(gè)滿足約束條件的葉子節(jié)點(diǎn)碍脏，即求得一個(gè)可行解。
分支限界采用廣度優(yōu)先搜索的方式去搜索解空間樹稍算。搜索過(guò)程中典尾，先生成所有的子節(jié)點(diǎn)（分支），然后對(duì)所有分支計(jì)算一個(gè)函數(shù)值（限界）糊探，并根據(jù)這些函數(shù)值（計(jì)算出的上界或者下界）钾埂，從中選擇一個(gè)使目標(biāo)函數(shù)最優(yōu)（限界最優(yōu)）的子節(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使得搜索朝著最優(yōu)解的方向快速推進(jìn)科平，從而很快求得一個(gè)最優(yōu)解褥紫。（ps：我的理解是每次從所有子節(jié)點(diǎn)中找出一個(gè)最有潛力的，作為擴(kuò)展結(jié)點(diǎn)進(jìn)行下一次的BFS）
- 分支限界算法的一般步驟：
（1）將問(wèn)題的解空間轉(zhuǎn)化為圖或者樹的結(jié)構(gòu)表示瞪慧，維護(hù)一張活葉子表（可以是優(yōu)先隊(duì)列）髓考。
（2）初始將根節(jié)點(diǎn)計(jì)算一個(gè)限界后加入活葉子表。
（3）當(dāng)活葉子表不為空時(shí)弃酌，從活葉子表中取出一個(gè)限界最優(yōu)的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)氨菇，并將該節(jié)點(diǎn)去除出表。當(dāng)活結(jié)點(diǎn)表為空時(shí)妓湘，算法結(jié)束查蓉。
（4）判斷當(dāng)前的擴(kuò)展結(jié)點(diǎn)是否可以滿足所有約束，并且得到一個(gè)可行解（該擴(kuò)展結(jié)點(diǎn)是葉子節(jié)點(diǎn)）榜贴。
如果是豌研，判斷優(yōu)于當(dāng)前最優(yōu)解后，記錄并更新最優(yōu)解，隨后將當(dāng)前最優(yōu)解與所有活葉子節(jié)點(diǎn)的限界做比較聂沙，對(duì)于限界差于最優(yōu)解的活葉子結(jié)點(diǎn)秆麸，去除出活葉子表，并返回（3）及汉。
如果不是沮趣，則進(jìn)入（5）。
（5）計(jì)算擴(kuò)展結(jié)點(diǎn)的所有子節(jié)點(diǎn)是否滿足約束條件坷随，對(duì)于不滿足約束條件的子節(jié)點(diǎn)房铭，將以該節(jié)點(diǎn)為根的子樹剪枝（丟棄）。
（6）根據(jù)限界函數(shù)温眉，計(jì)算該節(jié)點(diǎn)滿足約束的所有子節(jié)點(diǎn)的限界缸匪。對(duì)于限界差于當(dāng)前最優(yōu)解的子節(jié)點(diǎn)（ps：廢了，沒潛力）类溢，將以該子節(jié)點(diǎn)為根的子樹丟棄凌蔬；對(duì)于限界優(yōu)于當(dāng)前最優(yōu)解的子節(jié)點(diǎn)（ps：還有潛力），將這些潛力節(jié)點(diǎn)作為活葉子結(jié)點(diǎn)添加到活葉子表闯冷，并返回（3）
（ps：對(duì)于上述步驟的推導(dǎo)砂心，參考了《算法分析與設(shè)計(jì)基礎(chǔ)》12.2 分支限界法 ）
- 分支限界算法應(yīng)用的難點(diǎn)：
（1）解空間的構(gòu)造，即狀態(tài)空間樹的構(gòu)造方法（節(jié)點(diǎn)的生成順序）
（2）剪枝函數(shù)的確定蛇耀，即約束規(guī)則的確定
（3）限界函數(shù)的確定辩诞，邊界的評(píng)估方法
