深搜廣搜遍歷算法

《深搜廣搜遍歷算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、信息學(xué)資料——算法JOY深度優(yōu)先搜索遍歷算法深度優(yōu)先搜索的過程深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖。在深度優(yōu)先搜索中，對于最新發(fā)現(xiàn)的節(jié)點，如果它還有以此為起點而未搜索的邊，就沿此邊繼續(xù)搜索下去。當(dāng)節(jié)點v的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點v有那條邊的始節(jié)點。這一過程一直進行到已發(fā)現(xiàn)從源節(jié)點可達的所有節(jié)點為止。如果還存在未被發(fā)現(xiàn)的節(jié)點，則選擇其中一個作為源節(jié)點并重復(fù)以上過程，整個進程反復(fù)進行直到所有節(jié)點都被發(fā)現(xiàn)為止。即⒈以給定的某個頂點V0為起始點，訪問該頂點；　?、策x取一個與頂點V0相鄰接且未被訪問過的頂點V1，用V1作為新的起始點，重復(fù)

2、上述過程；　?、钞?dāng)?shù)竭_一個其所有鄰接的頂點都已被訪問過的頂點Vi時，就退回到新近被訪問過的頂點Vi-　1，繼續(xù)訪問Vi-1尚未訪問的鄰接點，重復(fù)上述搜索過程；　　⒋直到從任意一個已訪問過的頂點出發(fā)，再也找不到未被訪問過的頂點為止，遍歷便告完成。　　這種搜索的次序體現(xiàn)了向縱深發(fā)展的趨勢，所以稱之為深度優(yōu)先搜索。深度優(yōu)先搜索算法描述：程序?qū)崿F(xiàn)有兩種方式--遞歸與非遞歸。一、遞歸　　遞歸過程為：　　ProcedureDEF-GO(step)　　　fori:=1tomaxdo　　　　if子結(jié)點符合條件then　　　　　產(chǎn)生新的子結(jié)點入棧；　　　　　　if子結(jié)點是目標

3、結(jié)點then輸出　　　　　　　elseDEF-GO(step+1)；　　　　　　棧頂結(jié)點出棧；　　　　　endif；　　　　enddo；　　主程序為：　　ProgramDFS；　　　初始狀態(tài)入棧；　　　DEF-GO(1)；　　二、非遞歸　　ProgramDEF(step)；　　step:=0；　　repeat　　step:=step+1；　　j:=0；p:=false　　　repeat　　　　j:=j+1；　　　　if結(jié)點符合條件then　　　　　產(chǎn)生子結(jié)點入棧；　　　　　　if子結(jié)點是目標結(jié)點then輸出　　　　　　　elsep:=true；　　　　　el

4、se　　　　　　ifj>=maxthen回溯p:=false；　　　　endif；　　　untilp=true；15分析鉆研第頁訓(xùn)練提高信息學(xué)資料——算法JOY　　untilstep=0；　　回溯過程如下：　　ProcedureBACK；　　　step:=step-1；　　　ifstep>0then棧頂結(jié)點出棧　　　　elsep:=true；例如　八數(shù)碼難題--已知８個數(shù)的起始狀態(tài)如圖1（ａ），要得到目標狀態(tài)為圖1(ｂ）?！　　　　　　。病。浮。场　　　　　　　　　　　　。薄。病。场　　　　　　。薄。丁。础　　　　　　　　　　　　。浮　觥。础　　　　　　。贰?/p>

5、■?。怠　　　　　　　　　　　。贰。丁。怠　　　　　　　。ǎ幔　　　　　　　　　　　　　　。ǎ猓┣蠼鈺r,首先要生成一棵結(jié)點的搜索樹，按照深度優(yōu)先搜索算法，我們可以生成圖1的搜索樹。圖中，所有結(jié)點都用相應(yīng)的數(shù)據(jù)庫來標記，并按照結(jié)點擴展的順序加以編號。其中，我們設(shè)置深度界限為５。粗線條路徑表示求得的一個解。從圖中可見，深度優(yōu)先搜索過程是沿著一條路徑進行下去，直到深度界限為止，回溯一步，再繼續(xù)往下搜索，直到找到目標狀態(tài)或OPEN表為空為止?！　　　　　　　　　　　　　　　　　D1深度優(yōu)先搜索圖程序：programNo8_DFS;　　　　　　{八數(shù)碼的深度優(yōu)先搜索

6、算法}ConstDir:array[1..4,1..2]ofinteger=((1,0),(-1,0),(0,1),(0,-1));15分析鉆研第頁訓(xùn)練提高信息學(xué)資料——算法JOYmaxN=15;　　　　　　　　　　　　　　　?。梢猿惺艿淖畲笊疃龋齌ypeT8No=array[1..3,1..3]ofinteger;tList=recordstate:T8No;x0,y0:integer;end;VarSource,Target:T8No;List,Save:array[0..maxN]oftList;　　　　　　?。C合數(shù)據(jù)庫，最優(yōu)解路徑｝Open,Be

7、st:integer;procedureGetInfo;　　　　　　　　　　　　　　{見程序1}FunctionSame(A,B:T8No):Boolean;　　　　　　{見程序1}functionNot_Appear(New:tList):boolean;　　　　{見程序1}procedureMove(N:tList;d:integer;varok:boolean;varNew:tList);{見程序1}procedureGetOutInfo;　　　　　　　　　　　{輸出｝vari,x,y:integer;beginwriteln('total=',bes

8、t);fori:=1tobest+1dobeginf