02年05月14日廣度優(yōu)先搜索算法

1、廣度優(yōu)先搜索算法深度優(yōu)先與廣度優(yōu)先深度優(yōu)先的特點是在每一個多岔路口,如果能找到一條路往下走,就走,而不管別的路是否也能走下去，直到到達(dá)終點或無路可走時回溯。所以利用深度優(yōu)先搜索，只要有路，總能找到，但找到的那條并不一定是最優(yōu)的。廣度優(yōu)先的特點是在每一個多岔路口，都要把所有的路都嘗試一下，直到到達(dá)終點。所以利用廣度優(yōu)先搜索，只要有路，也總能找到，而且一旦找到，一定是最優(yōu)解（也即最少步驟）。 例：八數(shù)碼難題。在33的棋盤上，擺有八個棋子，每個棋子上標(biāo)有18的某一數(shù)字，棋盤中還有一個空格，空格周圍的棋子可以移至空格中?，F(xiàn)有給出的一種初始布局（初始狀態(tài)）如圖和目標(biāo)布局（目標(biāo)狀態(tài)）如圖。找出一種最少步驟

2、的移動方法，實現(xiàn)從初始布局到目標(biāo)布局的轉(zhuǎn)變，編程打印出每一步的狀態(tài)。2318476512384765初始狀態(tài)目標(biāo)狀態(tài)23184765283147652318476523184765123847652341876528314765283147652831647512384765本程序所要用到的數(shù)據(jù)結(jié)構(gòu)：1、結(jié)點數(shù)據(jù)（記錄類型） type a33=array1.3,1.3 of byte; node=record mode:a33; fa:byte; end; 2、用做廣度優(yōu)先搜索的樹（用數(shù)據(jù)來表示）A:array1.100 of node;3、一些重要的變量和常量：Open:integer; 用

3、來表示當(dāng)前所擴展到的結(jié)點。close:integer; 用來表示當(dāng)前所被擴展的結(jié)點。fxx:array1.4=(0,-1,0,1);fxy:arrray1.4=(-1,0,1,0);整體結(jié)構(gòu) 框圖：初始close=0I1 to 4open open+1生成子節(jié)點；aopen .mode?Aopen.faclose不滿足條件或與前面節(jié)點重復(fù)ynopen open-1成功達(dá)到目標(biāo)ynPrint 打印Exit 退出close close+1 父結(jié)點指針加1Until close=open初始化過程init：open 1; close 1i 1 to nj 1 to nRead(a1.modeI,j)

4、A1.fa 0i 1 to 3j 1 to 3Aclose.modeI,j=0ynk 1 to 4 4個方向i1 I+fxxk; j1 j+fxyk是否超界yn創(chuàng)建新結(jié)點是否是重復(fù)結(jié)點ny添加此結(jié)點，判斷是否目標(biāo)是目標(biāo)yn打??； 退出close close+1Until (close=open)創(chuàng)建新結(jié)點： （放在buffer里）buffer aclose.modeBufferI,j bufferi1,j1Bufferi1,j1 0添加新結(jié)點：Inc(open);Aopen.mode buffer;Aopen.fa close;判斷是否目標(biāo)：kk 0ii 1 to njj 1 to nAopen.modeii,jj=bii,jjynkk kk+1kk=9yn是目標(biāo)不是目標(biāo)k 1 to openq truei 1 to nj 1 to nModeI,jak.modeI,jynq false; i n; j nqynsame true; exit;same false判斷是否是重復(fù)結(jié)點：打印函數(shù)（遞歸打?。簂 =0 根結(jié)點？