廣度優(yōu)先搜索-資料下載頁(yè)
2025-07-24 16:46本頁(yè)面
【正文】 6到3是成功的四步走法。請(qǐng)編一程序，用10步完成從原始狀態(tài)跳變成目標(biāo)狀態(tài)。要求打印跳每一步后的狀態(tài)。用數(shù)字表示棋盤格子的代號(hào)?！ ? 1 2 3 4 5 6 7 原始位置 0 + + + 目標(biāo)位置 + + + 0 分析:此題可以用廣度與深度搜索兩種方法求解，通過運(yùn)行兩種解法的程序，我們可以粗略地知道兩種算法的區(qū)別?！ ∷惴ú襟E: ?、睌?shù)據(jù)庫(kù)：數(shù)組ｇ構(gòu)成隊(duì)，存放棋子的狀態(tài)；數(shù)組ｐ作為指針指向其父結(jié)點(diǎn)位置；ｔ與ｓ分別表示隊(duì)頭與隊(duì)尾指針?！ 、步Y(jié)點(diǎn)的產(chǎn)生：與位置間距3到3的棋子可移入空位，生成新結(jié)點(diǎn)狀態(tài)?！ 、乘阉鞑呗裕簭V度優(yōu)先搜索。 源程序如下:program ex1431。 {廣度優(yōu)先搜索}uses time。type status=string[7]。const start: status =39。0+++39?！bj: status =39。+++039。var a,b,c: timetype?！: array [1..200] of status?！: array [1..200] of integer。 i,j,k: integer?！,s: integer。procedure draw(f: integer)。{輸出}var m: array [1..10] of integer?！,j: integer。begin j:=0?！hile f1 do begin inc(j)?！ [j]:=f?！ :=p[f]?！nd?！riteln?！riteln(39。Start: 39。,start)?！or i:=j downto 1 do writeln(39。Step No.39。,j+1i,39。: 39。,g[m[i]])?！riteln(39。End39。)?！ettimenow(b)。 howlong(a,b,c)?！rinttime(39。Time Take: 39。,c)。 halt。end。function exampass(w: integer): boolean。{判斷結(jié)點(diǎn)有否重復(fù)}var i: integer。begin for i:=1 to w1 do if g[i]=g[w] then begin exampass:=false?！ xit?！ nd?！xampass:=true。end。begin {生成新結(jié)點(diǎn)} gettimenow(a)。 g[1]:=start。 p[1]:=0?！:=1。 s:=2?！epeat k:=pos(39。039。,g[t])?！ or i:=3 to 3 do if (i0) and (k+i=1) and (k+i=7) then begin g[s]:=g[t]。 g[s,k]:=g[s,k+i]。 g[s,k+i]:=39。039?！ [s]:=t。 if exampass(s) then begin if g[s]=obj then draw(s)。 inc(s)?！ nd?！ nd?！ nc(t)?！ntil t=s?！riteln(39。NoWay39。)。end.算法驟(二): ?、睌?shù)據(jù)庫(kù)：數(shù)組ｇ構(gòu)成堆棧，存放棋子的狀態(tài)?！ 、步Y(jié)點(diǎn)的產(chǎn)生：與空位置間距－３到３的棋子可移入空位，生成新結(jié)點(diǎn)狀態(tài)?！ 、乘阉鞑呗裕汉猩疃冉缦薜纳疃葍?yōu)先搜索。 源程序如下:program ex1432。 {深度優(yōu)先搜索}uses time。type status=string[7]。const start: status =39。0+++39。 obj: status =39。+++039。var a,b,c: timetype。 g: array [0..10] of status。 i,j,k: integer。procedure draw。{輸出}var i,j: integer。begin writeln(39。Start: 39。,start)?！or i:=1 to 10 do writeln(39。Step No.39。,i,39。: 39。,g[i])。 writeln(39。End39。)。 gettimenow(b)。 howlong(a,b,c)?！rinttime(39。Take Time: 39。,c)。 halt。end。function exampass(w: integer): boolean。{判斷有否重復(fù)狀態(tài)}var i: integer。begin for i:=1 to w1 do if g[i]=g[w] then begin exampass:=false?！ xit?！ nd?！xampass:=true。end。procedure run(t: integer)。{搜索生成新結(jié)點(diǎn)}var i,k: integer。begin k:=pos(39。039。,g[t1])。 for i:=3 to 3 do if (i0) and (k+i=1) and (k+i=7) then begin g[t]:=g[t1]?！ [t,k]:=g[t,k+i]。 g[t,k+i]:=39。039?！ f exampass(t) then if g[t]=obj then draw else if t10 then run(t+1)?！ nd。end。begin gettimenow(a)。 g[0]:=start?！un(1)。end.運(yùn)行兩種算法程序可以發(fā)現(xiàn)，廣度優(yōu)先搜索運(yùn)行速度比深度優(yōu)先搜索快?！ ∧敲瓷疃葍?yōu)先搜索與廣度優(yōu)先搜索算法有何區(qū)別呢？ 通常深度優(yōu)先搜索法不全部保留結(jié)點(diǎn)，擴(kuò)展完的結(jié)點(diǎn)從數(shù)據(jù)庫(kù)中彈出刪去，這樣，一般在數(shù)據(jù)庫(kù)中存儲(chǔ)的結(jié)點(diǎn)數(shù)就是深度值，因此它占用空間較少。所以，當(dāng)搜索樹的結(jié)點(diǎn)較多，用其它方法易產(chǎn)生內(nèi)存溢出時(shí)，深度優(yōu)先搜索不失為一種有效的求解方法?！ V度優(yōu)先搜索算法，一般需存儲(chǔ)產(chǎn)生的所有結(jié)點(diǎn)，占用的存儲(chǔ)空間要比深度優(yōu)先搜索大得多，因此，程序設(shè)計(jì)中，必須考慮溢出和節(jié)省內(nèi)存空間的問題。但廣度優(yōu)先搜索法一般無回溯操作，即入棧和出棧的操作，所以運(yùn)行速度比深度優(yōu)先搜索要快些。 第 17 頁(yè) 共 17
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1