廣度優(yōu)先搜索-展示頁(yè)
2024-08-08 16:46本頁(yè)面
【正文】 Procedure Recursive。 end。 end。)。 for i:=1 to best+1 do begin for x:=1 to 3 do begin for y:=1 to 3 do write(Save[i].State[x,y],39。total = 39。 {輸出｝ var i,x,y : integer。var New : tList)。d : integer。 {見(jiàn)程序1} function Not_Appear(New : tList):boolean。 procedure GetInfo。 List,Save : array[0..maxN]of tList。 end。 tList = record state : T8No。 maxN = 15?！ ?圖1程序：program No8_DFS。粗線條路徑表示求得的一個(gè)解。圖中，所有結(jié)點(diǎn)都用相應(yīng)的數(shù)據(jù)庫(kù)來(lái)標(biāo)記，并按照結(jié)點(diǎn)擴(kuò)展的順序加以編號(hào)。一、遞歸 遞歸過(guò)程為： Procedure DEFGO(step) for i:=1 to max do if 子結(jié)點(diǎn)符合條件 then 產(chǎn)生新的子結(jié)點(diǎn)入棧； if 子結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn) then 輸出 else DEFGO(step+1)； 棧頂結(jié)點(diǎn)出棧； endif； enddo； 主程序?yàn)椋骸 rogram DFS； 初始狀態(tài)入棧； DEFGO(1)； 二、非遞歸 Program DEF(step)； step:=0； repeat step:=step+1； j:=0；p:=false repeat j:=j+1； if 結(jié)點(diǎn)符合條件 then 產(chǎn)生子結(jié)點(diǎn)入棧； if 子結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn) then 輸出 else p:=true； else if j=max then 回溯 p:=false； endif； until p=true； until step=0； 回溯過(guò)程如下： Procedure BACK； step:=step1； if step0 then 棧頂結(jié)點(diǎn)出?！ lse p:=true；例如 八數(shù)碼難題已知８?jìng)€(gè)數(shù)的起始狀態(tài)如圖1（ａ），要得到目標(biāo)狀態(tài)為圖1(ｂ）?！ ∵@種搜索的次序體現(xiàn)了向縱深發(fā)展的趨勢(shì)，所以稱之為深度優(yōu)先搜索。如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)，則選擇其中一個(gè)作為源節(jié)點(diǎn)并重復(fù)以上過(guò)程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被發(fā)現(xiàn)為止。當(dāng)節(jié)點(diǎn)v的所有邊都己被探尋過(guò)，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v有那條邊的始節(jié)點(diǎn)。（一）深度優(yōu)先搜索遍歷算法深度優(yōu)先搜索的過(guò)程深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖。在深度優(yōu)先搜索中，對(duì)于最新發(fā)現(xiàn)的節(jié)點(diǎn)，如果它還有以此為起點(diǎn)而未搜索的邊，就沿此邊繼續(xù)搜索下去。這一過(guò)程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。即⒈以給定的某個(gè)頂點(diǎn)V0為起始點(diǎn)，訪問(wèn)該頂點(diǎn)； ?、策x取一個(gè)與頂點(diǎn)V0相鄰接且未被訪問(wèn)過(guò)的頂點(diǎn)V1，用V1作為新的起始點(diǎn)，重復(fù)上述過(guò)程； ⒊當(dāng)?shù)竭_(dá)一個(gè)其所有鄰接的頂點(diǎn)都已被訪問(wèn)過(guò)的頂點(diǎn)Vi時(shí)，就退回到新近被訪問(wèn)過(guò)的頂點(diǎn)Vi 1，繼續(xù)訪問(wèn)Vi1尚未訪問(wèn)的鄰接點(diǎn)，重復(fù)上述搜索過(guò)程； ?、粗钡綇娜我庖粋€(gè)已訪問(wèn)過(guò)的頂點(diǎn)出發(fā)，再也找不到未被訪問(wèn)過(guò)的頂點(diǎn)為止，遍歷便告完成。深度優(yōu)先搜索算法描述：程序?qū)崿F(xiàn)有兩種方式遞歸與非遞歸?！ 。病。浮。场 。薄。病。场 。薄。丁。础 。浮 觥。础 。贰 觥。怠 ? ７?。丁。怠 。ǎ幔 。ǎ猓 D 1 求解時(shí),首先要生成一棵結(jié)點(diǎn)的搜索樹(shù)，按照深度優(yōu)先搜索算法，我們可以生成圖1的搜索樹(shù)。其中，我們?cè)O(shè)置深度界限為５。從圖中可見(jiàn)，深度優(yōu)先搜索過(guò)程是沿著一條路徑進(jìn)行下去，直到深度界限為止，回溯一步，再繼續(xù)往下搜索，直到找到目標(biāo)狀態(tài)或OPEN表為空為止。 {八數(shù)碼的深度優(yōu)先搜索算法}Const Dir : array[1..4,1..2]of integer = ((1,0),(1,0),(0,1),(0,1))。 ?。梢猿惺艿淖畲笊疃龋齌ype T8No = array[1..3,1..3]of integer。 x0,y0 : integer。Var Source,Target : T8No?！ 。C合數(shù)據(jù)庫(kù)，最優(yōu)解路徑｝ Open,Best : integer。 {見(jiàn)程序1} Function Same(A,B : T8No):Boolean。 {見(jiàn)程序1} procedure Move(N : tList。var ok : boolean。 {見(jiàn)程序1} procedure GetOutInfo。 begin writeln(39。,best)。 39。 writeln。 writeln。 end?！ ? ｛遞歸搜索過(guò)程｝ Var i : integer。 ok : boolean。 If Same(List[Open].state,Target) then begin ｛如果找到解，保存當(dāng)前最優(yōu)解｝ Best:=Open1。 end。 if ok and not_Appear(New) then begin ｛如果沒(méi)有重復(fù)｝ inc(open)。 Recursive。 {退棧} End。 End。 {搜索主過(guò)程} var x,y : integer。 {初始化} for x:=1 to 3 do for y:=1 to 3 do if Source[x,y]=0 then begin List[1].x0:=x。 end。 Open:=1。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1