雙向廣度優(yōu)先搜索

雙向廣度優(yōu)先搜索

ByHelang搜索優(yōu)化一POJ1077八數(shù)碼問題八數(shù)碼問題是人工智能中的經(jīng)典問題POJ1077八數(shù)碼問題：經(jīng)典搜索問題有一個3*3的棋盤，其中有0-8共9個數(shù)字，0表示空格，其他的數(shù)字可以和0交換位置。求由初始狀態(tài)

到達(dá)目標(biāo)狀態(tài)

123

456

780

的步數(shù)最少的解？廣度優(yōu)先搜索（bfs）優(yōu)先擴(kuò)展淺層節(jié)點(diǎn)，逐漸深入廣度優(yōu)先搜索用隊列保存待擴(kuò)展的節(jié)點(diǎn)，從隊首隊取出節(jié)點(diǎn)，擴(kuò)展出的新節(jié)點(diǎn)放入隊尾，直到找到目標(biāo)節(jié)點(diǎn)（問題的解）廣度優(yōu)先搜索的代碼框架BFS(){ 初始化隊列 while(隊列不為空且未找到目標(biāo)節(jié)點(diǎn)) {

取隊首節(jié)點(diǎn)擴(kuò)展，并將擴(kuò)展出的節(jié)點(diǎn)放入隊尾； 必要時要記住每個節(jié)點(diǎn)的父節(jié)點(diǎn)； }}判重新擴(kuò)展出的節(jié)點(diǎn)如果和以前擴(kuò)展出的節(jié)點(diǎn)相同，則這個新節(jié)點(diǎn)就不必再考慮如何判重？判重合理編碼，減小存儲代價不同的編碼方式所需要的存儲空間會有較大差別需要考慮的問題狀態(tài)數(shù)目巨大，如何存儲？怎樣才能較快的找到重復(fù)節(jié)點(diǎn)為節(jié)點(diǎn)編號把每個節(jié)點(diǎn)都看一個排列，以此排列在全部排列中的位置作為其編號排列總數(shù)：9!=362880只需要一個整數(shù)(4字節(jié))即可存下一個節(jié)點(diǎn)一個boolean標(biāo)志數(shù)組flag記錄當(dāng)前狀態(tài)是否重復(fù)判重用的標(biāo)志數(shù)組只需要362,880字節(jié)即可。此方案需要編寫給定排列求序號和給定序號求排列的函數(shù)，這些函數(shù)的執(zhí)行速度慢于字符串形式的9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)。時空時間與空間的權(quán)衡對于狀態(tài)數(shù)較小的問題，可以用最直接的方式編碼以空間換時間對于狀態(tài)數(shù)太大的問題，需要利用好的編碼方法以時間換空間具體問題具體分析BFS中的關(guān)鍵問題：

1）如何進(jìn)行狀態(tài)擴(kuò)展？

2）如何判斷擴(kuò)展標(biāo)記已經(jīng)存在？

3）對未擴(kuò)展?fàn)顟B(tài)，如何置已擴(kuò)展標(biāo)記？

4）字符串形式的9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)廣度優(yōu)先搜索的過程1.從某個頂點(diǎn)出發(fā)開始訪問，被訪問的頂點(diǎn)作相應(yīng)的標(biāo)記，并輸出訪問頂點(diǎn)號；2.從被訪問的頂點(diǎn)出發(fā)，依次搜索與該頂點(diǎn)有邊的關(guān)聯(lián)的所有未被訪問的鄰接點(diǎn)，并作相應(yīng)的標(biāo)記；3.再依次根據(jù)2中所有被訪問的鄰接點(diǎn)，訪問與這些鄰接點(diǎn)相關(guān)的所有未被訪問的鄰接點(diǎn)，直到所有頂點(diǎn)被訪問為止；廣度優(yōu)先搜索流程廣度優(yōu)先搜索的特點(diǎn)

廣度優(yōu)先搜索遵循從初始結(jié)點(diǎn)開始一層層擴(kuò)展直到找到目標(biāo)結(jié)點(diǎn)的搜索規(guī)則，它只能較好地解決狀態(tài)不是太多的情況，承受力很有限。如果擴(kuò)展結(jié)點(diǎn)較多，而目標(biāo)結(jié)點(diǎn)又處在較深層，搜索量就會非常龐大，往往就會出現(xiàn)內(nèi)存空間不夠用的情況。例題：移字母（NKOJ1688）

移動一個只含字母A和B的長度不超過20字符串，給定初始狀態(tài)為(a)表，目標(biāo)狀態(tài)為(b)表，給定移動規(guī)則為：只能互相對換相鄰字母。請找出一條移動最少步數(shù)的辦法。

[AABBAA][BAAAAB](a)(b)搜索過程1AABBAA2ABABAA3AABABA4ABBAAA5BAABAA6ABAABA7AAABBA8AABAAB[AABBAA]→[AABABA]→[AABAAB]→[ABAAAB]→[BAAAAB]

·························································ABAAABBAAAAB······························································怎樣判重？[AABBAA]

(110011)

2

==(51)

10字符串長度不超過20，總共有220狀態(tài)，用大小為flag[1048576]布爾數(shù)組來標(biāo)記即可。若字符串長度很長，比如有100位，怎么判重？針對字符串的一些hash算法，比如ELFHash和BKDRHash雙向廣度優(yōu)先搜索

有些問題按照廣度優(yōu)先搜索法則擴(kuò)展結(jié)點(diǎn)的規(guī)則，既適合順序，也適合逆序，于是我們考慮在尋找目標(biāo)結(jié)點(diǎn)或路徑的搜索過程中，初始結(jié)點(diǎn)向目標(biāo)結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)向初始結(jié)點(diǎn)同時進(jìn)行擴(kuò)展，直至在兩個擴(kuò)展方向上出現(xiàn)同一個子結(jié)點(diǎn)，搜索結(jié)束，這就是雙向搜索過程。

如果確實存在一條從初始結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的最佳路徑，那么按雙向搜索進(jìn)行搜索必然會在某層出現(xiàn)“相交”，即有相交點(diǎn)，初始結(jié)點(diǎn)→相交點(diǎn)→目標(biāo)結(jié)點(diǎn)所形成的一條路徑即是所求最佳路徑。AABBAAABABAAAABABAABBAAABAABAAABAABAAAABBAAABAABBAAAABABAAABBAAABAAABAAB正向擴(kuò)展逆向擴(kuò)展雙向搜索結(jié)點(diǎn)擴(kuò)展順序雙向擴(kuò)展結(jié)點(diǎn)，在兩個方向的擴(kuò)展順序上，可以輪流交替進(jìn)行，但由于大部分的解答樹并不是棵完全樹，在擴(kuò)展完一層后，下一層則選擇結(jié)點(diǎn)個數(shù)較少的那個方向先擴(kuò)展，可以克服兩個方向結(jié)點(diǎn)生成速度不平衡的狀態(tài)，明顯提高搜索效率。雙向搜索的數(shù)據(jù)結(jié)構(gòu)

雙向廣度優(yōu)先搜索從兩個方向進(jìn)行擴(kuò)展，我們需要建立兩個隊列，OPEN[1]，CLOSED[1]，OPEN[2]，CLOSED[2]分別存儲兩個方向上的新生成結(jié)點(diǎn)和已討論結(jié)點(diǎn)。基于廣度優(yōu)先搜索算法的雙向，建立三個二維指針：head，tail，next其作用如下：

head[1]，head[2]：分別指向兩個方向上當(dāng)前待討論層的第一個結(jié)點(diǎn)。

tail[1]，tail[2]：分別指兩個方向上隊尾新產(chǎn)生的結(jié)點(diǎn)。

為了區(qū)分當(dāng)前搜索方向，設(shè)方向標(biāo)志：

t=1表示處于正向搜索，t=2表示處于逆向搜索。

Fail—有一個方向搜索失敗時，為真，并且結(jié)束搜索過程，否則為假。

i—全局變量，指向當(dāng)前要擴(kuò)展的結(jié)點(diǎn)。雙向廣度優(yōu)先搜索算法模板//DOUBFS初始化，初始結(jié)點(diǎn)，和目標(biāo)結(jié)點(diǎn)分別進(jìn)入OPEN[1]和OPEN[2]表；head[1]=1;

tail[1]=1;

head[2]=1;

tail[2]=1；

do{

if(tail[1]-head[1]<=tail[2]-head[2])t=1;elset=2；//優(yōu)先擴(kuò)展待討論節(jié)點(diǎn)比較少那個方向

for(i=head[t];i<=tail[t];i++)expand(t)；//討論隊列中的結(jié)點(diǎn)}while(head[t]<=tail[t])；//函數(shù)expand(t)的結(jié)構(gòu)如下：voidexpand(intt){

intj；

for(j=1;j<=n;j++

)//n為最多后繼狀態(tài)數(shù)

{

產(chǎn)生i點(diǎn)的第j個后繼狀態(tài)，將它加入到隊尾(tail[t]+1)；

if(新結(jié)點(diǎn)未與其上一層以上的所有點(diǎn)重復(fù))

{

ifisans(t){輸出結(jié)果；return；}}

else{將新點(diǎn)從隊列中去掉(tail[t]-1);}

}

}

//判斷兩個方向是否是相交點(diǎn)的函數(shù)isans(t)如下：

boolisans(intt){

intj,k；

if(t==1)k=2