資源描述：
《廣度優(yōu)先搜索算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、廣度優(yōu)先搜索算法例八數(shù)碼難題。在3＊3的棋盤上，擺有八個棋子，每個棋子上標(biāo)有1至8的某一數(shù)字。棋盤中留有一個空格。空格周圍的棋子可以移到空格中。要求解的問題是，給出一種初始布局[初始狀態(tài)]和目標(biāo)布局[目標(biāo)狀態(tài)]，找到一種移動的方法，實現(xiàn)從初始布局到目標(biāo)布局的轉(zhuǎn)變。2831647512384765283164705283164075283164750283104765283064175283014765203184765283140765283164750083264175283604175083214765283714065280143765283145760283106754283163
2、754……………………………………………………………………綜合數(shù)據(jù)庫typenode=recordch:array[1..3,1..3]ofbyte;si,sj:byte;{空格的坐標(biāo)}pnt,dep:word;{父節(jié)點(diǎn)和深度}end;Vardata:array[1..2600]ofnode;temp:node;產(chǎn)生式規(guī)則:4條，空格向上，下，左，右四個方向移動生成結(jié)點(diǎn)的條件：（1）新狀態(tài)不出界（2）和已生成結(jié)點(diǎn)不重復(fù)ni:=temp.si+di[k];nj:=temp.sj+dj[k];withtempdobeginch[si,sj]:=ch[ni,nj];ch[ni,nj]:=0;si
3、:=ni;sj:=nj;pnt:=head;dep:=dep+1;end;r1234方向左上右下di0-101dj-1010搜索策略（BFS）框圖：初始head=0Tail=0初始化INIT;初始結(jié)點(diǎn)入隊結(jié)點(diǎn)出隊out(temp1)temp←temp1change(temp)Forr:=1to4doCheck(temp)andnot(dupe(temp))ynIn(temp)Temp=goalynPrint{打印}Exit{退出}Untilhead=tail練習(xí)：有兩個無刻度標(biāo)志的水壺，分別可裝5升水和2升水，設(shè)另有一水缸，可用來向水壺灌水或倒出水，兩水壺間，水也可以相互傾灌。已知5升壺為
4、滿壺，2升壺為空壺。問如何通過倒水或灌水操作，用最少步數(shù)能在2升壺中量出1升水來。編一程序解決問題。如圖是六個城市之間道路聯(lián)系的示意圖，連線表示兩城市間有道路相通，連線旁的數(shù)字表示路程。請編程序，由計算機(jī)找到從C1到C6的一條路徑及路程總長度，要求求出經(jīng)過城市最少的解和路程總長度最少的解。C63448492264C1C2C5C4C3綜合數(shù)據(jù)庫typenode=recordcity:integer;{城市編號}flag:setof[1..6];{到根結(jié)點(diǎn)的路徑}pnt:integer;{父節(jié)點(diǎn)}end;Vardata:array[1..1000]ofnode;temp:node;產(chǎn)生式規(guī)則:
5、5條，向R（R=2--6）城市移動生成結(jié)點(diǎn)的條件：（1）城市R不在已走路徑中（not(Rindata[head].flag)）（2）當(dāng)前城市到R有路（link[x,r]>0）Data[temp].city:=R;Data[temp].flag:=Data[temp].flag+[R];Data[temp].pnt:=head;搜索策略（BFS）框圖：初始head=0Tail=0初始化INIT;初始結(jié)點(diǎn)入隊結(jié)點(diǎn)出隊out(temp)temp1←tempchange(temp)Forr:=2to6do條件1and條件2ynIn(temp)Temp=goalynPrint{打印}Exit{退出}
6、Untilhead=tail翻幣問題。有N個硬幣（N>=6），正面朝上排成一排，每次將5個硬幣翻過來放在原來位置，直到最后全部硬幣翻成反面朝上為止。編程讓計算機(jī)找了步數(shù)最少的翻法，并把翻幣過程及次數(shù)打印出來（用O表示正面，＊表示反面）綜合數(shù)據(jù)庫typenode=recordr:integer;(由父節(jié)點(diǎn)翻了幾個正面朝上的硬幣得到當(dāng)前狀態(tài))num:integer;(當(dāng)前狀態(tài)中硬幣朝上的個數(shù))pnt:integer;(父節(jié)點(diǎn)位置)end;Vardata:array[1..1000]ofnode;temp:node;產(chǎn)生式規(guī)則:6條，即翻R個（R=0，1，2，3，4，5）正面朝上的硬幣生成結(jié)點(diǎn)的
7、條件：（1）當(dāng)前狀態(tài)有多于R個正面朝上的硬幣M>=R（M表示當(dāng)前結(jié)點(diǎn)正面朝上硬幣的個數(shù)），否則出現(xiàn)負(fù)數(shù)（2）當(dāng)前狀態(tài)有多于5-R個反面朝上的硬幣N-M>=5-R（N表示硬幣總數(shù)），例如當(dāng)全部是正面時，R只能取5，不能取0—4。這時N=M，只有R=5時，不等式才成立。（3）當(dāng)前狀態(tài)已存在狀態(tài)不重復(fù)新結(jié)點(diǎn)正面朝上硬幣個數(shù)=（M-R）+(5-R)搜索策略（BFS）框圖：初始head=0Tail=0初始化INIT;初始結(jié)點(diǎn)入隊結(jié)
