廣度優(yōu)先搜索(參考版)
2024-08-04 16:46本頁(yè)面
【正文】 但廣度優(yōu)先搜索法一般無(wú)回溯操作，即入棧和出棧的操作，所以運(yùn)行速度比深度優(yōu)先搜索要快些。所以，當(dāng)搜索樹(shù)的結(jié)點(diǎn)較多，用其它方法易產(chǎn)生內(nèi)存溢出時(shí)，深度優(yōu)先搜索不失為一種有效的求解方法。end.運(yùn)行兩種算法程序可以發(fā)現(xiàn)，廣度優(yōu)先搜索運(yùn)行速度比深度優(yōu)先搜索快?！[0]:=start。end?！ f exampass(t) then if g[t]=obj then draw else if t10 then run(t+1)。 g[t,k+i]:=39。 for i:=3 to 3 do if (i0) and (k+i=1) and (k+i=7) then begin g[t]:=g[t1]。039。{搜索生成新結(jié)點(diǎn)}var i,k: integer。end?！ nd。begin for i:=1 to w1 do if g[i]=g[w] then begin exampass:=false。function exampass(w: integer): boolean?！alt。Take Time: 39。 howlong(a,b,c)。)?！riteln(39。: 39。Step No.39。,start)。begin writeln(39。procedure draw。 g: array [0..10] of status。+++039。0+++39。type status=string[7]。 源程序如下:program ex1432?！ 、步Y(jié)點(diǎn)的產(chǎn)生：與空位置間距－３到３的棋子可移入空位，生成新結(jié)點(diǎn)狀態(tài)。)?！riteln(39?！ nc(t)?！ nd?！ f exampass(s) then begin if g[s]=obj then draw(s)。039。 g[s,k]:=g[s,k+i]。,g[t])?！epeat k:=pos(39。 t:=1?！[1]:=start。end?！ nd。begin for i:=1 to w1 do if g[i]=g[w] then begin exampass:=false。function exampass(w: integer): boolean。 halt。Time Take: 39?！owlong(a,b,c)。)?！riteln(39。: 39。Step No.39。,start)?！riteln(39。 end。 m[j]:=f。begin j:=0。{輸出}var m: array [1..10] of integer?！,s: integer?！: array [1..200] of integer。var a,b,c: timetype?！bj: status =39。const start: status =39。 {廣度優(yōu)先搜索}uses time。 ?、乘阉鞑呗裕簭V度優(yōu)先搜索。 算法步驟: ?、睌?shù)據(jù)庫(kù)：數(shù)組ｇ構(gòu)成隊(duì)，存放棋子的狀態(tài)；數(shù)組ｐ作為指針指向其父結(jié)點(diǎn)位置；ｔ與ｓ分別表示隊(duì)頭與隊(duì)尾指針。用數(shù)字表示棋盤(pán)格子的代號(hào)。請(qǐng)編一程序，用10步完成從原始狀態(tài)跳變成目標(biāo)狀態(tài)。跳棋的規(guī)則是： ?、比我庖粋€(gè)棋子可移到相鄰的空位上； ?、部商^(guò)一個(gè)或兩個(gè)棋子到空位上，與跳過(guò)的棋子的顏色無(wú)關(guān)； ?、称遄酉蜃笙蛴姨幌?。end. 例2 跳棋的原始狀態(tài)如下圖。NoWay39。 until t=s。 end?！ nc(s)?！ [s]:=t?！ [s,j]:=v[j]。 d[s,i]:=0。 repeat for i:=1 to 3 do if d[t,i]0 then for j:=1 to 3 do if (ij) and (d[t,j]v[j]) then begin d[s]:=d[t]?！:=1。 d[1,3]:=0。begin {生成新結(jié)點(diǎn),將一個(gè)不空的杯子水倒入一個(gè)不滿的杯子中} d[1,1]:=80。{是否為目標(biāo)結(jié)點(diǎn)}begin if (d[w,1]=40) and (d[w,2]=40) then isobject:=true else isobject:=false。end。 end。begin for i:=1 to w1 do if (d[i,1]=d[w,1]) and (d[i,2]=d[w,2]) and (d[i,3]=d[w,3]) then begin exampass:=false。function exampass(w: integer): boolean?！alt。End.39。 end?！ or k:=1 to 3 do write(d[m[i],k]:3)。: 39。Step No.39。,d[1,1]:3,d[1,2]:3,d[1,3]:3)。 writeln(39?！nd?！ [j]:=f。begin j:=0。{輸出}var m: array [1..20] of integer。 t,s,i,j: integer。var d: array [1..200] of status。type status= array [1..3] of integer?！ 、乘阉鞑呗? 廣度優(yōu)先搜索?！ ∷惴ú襟E: ?、睌?shù)據(jù)庫(kù): 用數(shù)組d構(gòu)成存放生成結(jié)點(diǎn)(杯子水狀態(tài))的隊(duì)；數(shù)組p作為指向父結(jié)點(diǎn)的指針；t和s作為隊(duì)頭與隊(duì)尾指針。End.例1 在一個(gè)瓶中裝有80毫升化學(xué)溶劑，實(shí)驗(yàn)中需要精確地平分成兩份，沒(méi)有量具，只有兩個(gè)杯子，其中一個(gè)杯子的容量是50毫升，另一個(gè)是30毫升，試設(shè)計(jì)一個(gè)程序?qū)⒒瘜W(xué)溶劑對(duì)分成兩個(gè)40毫升，并以最少步驟給出答案。 Close(Input)。 Initialize。ReWrite(Output)。39。ReSet(Input)。39。 {無(wú)解} end。No answer39。 {擴(kuò)展Closed} Until (Closed=Open) or Found。 {搜索主過(guò)程} begin Repeat Inc(Closed)。 end。,Best)。 begin Writeln(39。 writeln。 writeln。 39。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1