分支限界法的分支限界法與回溯法的不同？在時(shí)間復(fù)雜度上比較分支限界法和回溯法？別在樓上胡說(shuō)八道。分支邊界法和回溯法是兩種不同的搜索方法，它們屬于并行搜索，不是誰(shuí)包含誰(shuí)1）回溯法一般采用深度優(yōu)先搜索解空間

分支限界法的分支限界法與回溯法的不同？

在時(shí)間復(fù)雜度上比較分支限界法和回溯法？

別在樓上胡說(shuō)八道。分支邊界法和回溯法是兩種不同的搜索方法，它們屬于并行搜索，不是誰(shuí)包含誰(shuí)

1）回溯法一般采用深度優(yōu)先搜索解空間，并用邊界函數(shù)進(jìn)行修剪

2）一般采用廣度優(yōu)先搜索解空間，回溯法采用優(yōu)先級(jí)隊(duì)列進(jìn)行剪枝，解空間中的節(jié)點(diǎn)可以多次出現(xiàn)，但分支邊界只出現(xiàn)一次，不存在回溯。怎么說(shuō)分支邊界是回溯的

用約束函數(shù)對(duì)擴(kuò)展節(jié)點(diǎn)上不滿(mǎn)足約束的子樹(shù)進(jìn)行切割；用約束函數(shù)對(duì)沒(méi)有得到最優(yōu)解的子樹(shù)進(jìn)行切割。這兩類(lèi)函數(shù)稱(chēng)為修剪函數(shù)。使用剪枝函數(shù)可以避免無(wú)效搜索，提高回溯法的搜索效率。在分枝定界法中使用剪枝函數(shù)可以加快搜索速度。該函數(shù)給出了每個(gè)可行節(jié)點(diǎn)對(duì)應(yīng)子樹(shù)最大值的上界。如果上界不大于當(dāng)前的最優(yōu)值，則相應(yīng)的子樹(shù)不包含問(wèn)題的最優(yōu)解，因此可以將其截?cái)唷Ａ硪环矫妫梢詫⒂缮辖绾瘮?shù)確定的每個(gè)節(jié)點(diǎn)的上界值作為優(yōu)先級(jí)，并且可以按優(yōu)先級(jí)的非遞增順序提取當(dāng)前擴(kuò)展節(jié)點(diǎn)。這種策略有時(shí)可以更快地找到最優(yōu)解。