在時(shí)間復(fù)雜度上比較分支限界法和回溯法？別說(shuō)廢話，分支邊界和回溯是兩種不同的搜索方法，它們屬于并行搜索，不是誰(shuí)包含誰(shuí)。1）回溯方法一般采用深度優(yōu)先搜索解空間，并用邊界函數(shù)進(jìn)行修剪2）分支邊界一般采用廣度

在時(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ō)分支邊界是回溯的

八皇后問(wèn)題是一個(gè)古老而著名的問(wèn)題，這是回溯算法的一個(gè)典型例子。

19世紀(jì)著名數(shù)學(xué)家高斯在1850年提出了一個(gè)問(wèn)題：在8X8格棋上放置8個(gè)皇后，使它們不能互相攻擊，即任何兩個(gè)皇后不能在同一行、同一列或同一對(duì)角線上。有多少種鐘擺。高斯認(rèn)為有76種選擇。1854年，不同的作者在柏林的國(guó)際象棋雜志上發(fā)表了40種不同的解決方案。用圖論方法得到92個(gè)結(jié)果。對(duì)于八皇后問(wèn)題的實(shí)現(xiàn)，如果結(jié)合動(dòng)態(tài)圖形演示，對(duì)算法的描述可以更加生動(dòng)、生動(dòng)，教學(xué)效果良好。下面是一個(gè)用turboc實(shí)現(xiàn)的八皇后問(wèn)題的圖形程序，可以演示所有92個(gè)解。八皇后問(wèn)題動(dòng)態(tài)圖的實(shí)現(xiàn)