分支限界法的解空間樹的動(dòng)態(tài)搜索

（1）回溯求解0/1背包問(wèn)題，雖剪枝減少了搜索空間，但整個(gè)搜索按深度優(yōu)先機(jī)械進(jìn)行，是盲目搜索（不可預(yù)測(cè)本結(jié)點(diǎn)以下的結(jié)點(diǎn)進(jìn)行的如何）。
（2）回溯求解TSP也是盲目的（雖有目標(biāo)函數(shù)，也只有找到一個(gè)可行解后才有意義）
（3）分支限界法首先確定一個(gè)合理的限界函數(shù)，并根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界[down, up]；然后按照廣度優(yōu)先策略遍歷問(wèn)題的解空間樹，在某一分支上，依次搜索該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，分別估算這些孩子結(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值（對(duì)最小化問(wèn)題，估算結(jié)點(diǎn)的down，對(duì)最大化問(wèn)題，估算結(jié)點(diǎn)的up）。如果某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的界，則將其丟棄（從此結(jié)點(diǎn)生成的解不會(huì)比目前已得的更好），否則入待處理表。