算法分析與設(shè)計查找迷宮的最短路徑廣度算法

1、算法分析與設(shè)計查找迷宮的最短路徑（廣度算法）計算機科學(xué)與技術(shù)12級16班2012/12/16【摘要】本論文提出了求解迷宮最短路徑問題的經(jīng)典廣度優(yōu)先搜索。通過合理的變換，將原問題轉(zhuǎn)化為迷宮路徑深度圖的生成問題。最后對算法進(jìn)行了嚴(yán)謹(jǐn)?shù)姆治龊蛯嵗郎y試。 迷宮求解是一個古老的游戲，要在迷宮中找到出口， 需要經(jīng)過一連串的錯誤嘗試才能找到正確的路徑，有的時候甚至找不到路徑。類似于給定一個 m*n的矩形網(wǎng)格，設(shè)其左上角為起點$ 一輛汽車從起點出發(fā)駛向右下角終點To在若干網(wǎng)格處設(shè)置了障礙，表示該網(wǎng)格不可到達(dá)。設(shè)計一個算法，求汽車從起點S出發(fā)到達(dá)終點T的一條路線。用計算機求解這個問題時，我們 通常采用的是回溯方

2、法，即從入口出發(fā)，順某方向向前探索，若能走通，則繼續(xù)往前走；否 則沿原路退回。換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路 徑。因此，在求迷宮通路的算法中應(yīng)用“棧”也就是自然而然的事。當(dāng)然還有其他的方法來 解決，例如順序表，深度優(yōu)先遍歷，廣度優(yōu)先遍歷等?！娟P(guān)鍵詞】：最短路徑；時間復(fù)雜度；廣度優(yōu)先搜索Summary Maze solving is an ancient game , you want to find the exit in the maze , need to go through

3、 a series of trial and error to find the right path , and sometimes not even find the path . A m * n rectangular grid , similar to a given set its upper-left corner as the starting point S . A car from the starting point towards the bottom right corner of the end of T . Set up barriers at certain gr

4、id , indicates that the grid is unreachable . Design an algorithm , find the car starting to reach the end point T, route from the starting point S . Use the computer to solve this problem , we usually use the backtracking method , that is, starting from the entrance , Shun forwardtoexplore a direct

5、ion , if we go through , and continue to move forward ; otherwise return along the same route . Continue to explore another direction , until all possible paths to explore to far . In order to ensure that in any position along the same route back , it is clear that the need to use a LIFO structure t

6、o save the path from the entrance to the current position . Therefore ,inseeking labyrinth path algorithm application "stack" is the natural thing to do . Of course , there are other ways to solve , for example, the sequence table , depth-first traversal , breadth -first traversal .【Key ph

7、rasd Shortest path ; time complexity ; breadth-first search摘要1關(guān)鍵字1一、問題描述3二、算法31深度優(yōu)先搜索32廣度優(yōu)先搜索3三、參考代碼 4四、編程調(diào)試方面 5五、小結(jié)5六、參考文獻(xiàn) 5問題描述迷宮最短路徑（the shortest path of maze）問題是一個典型的搜索、遍歷問題 ,其程序設(shè) 計想在人工智能設(shè)計、機器人設(shè)計等事務(wù)中均有應(yīng)用。如圖所示，一個NXM的大方塊迷宮，帶斜線的單元格表示墻壁（障礙），空白的單元格表示通道。迷宮問題可以表述為：而迷宮最短路徑問題就是找出從迷宮入口到出口所經(jīng)過單元格個數(shù)最少的路徑。求解迷

8、宮問題，經(jīng)典算法有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種。深度優(yōu)先搜索（DFS）:從入口出發(fā)，順著某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回（回 溯），換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。如果恰好某一步探索到出口，則就找到了從入口到出口的路徑。為了保證在任何位置上都能沿原路退回，防止死循環(huán)，需要使用堆棧來保存大量記錄。而要求解迷宮最短路徑，則必須用深度優(yōu)先搜索出所有到達(dá)出口的路徑，通過比較得到最短距離的路徑，這樣也必然要求增加數(shù)據(jù)空間來保存搜索過程中當(dāng)前最短路徑，增加了空間復(fù)雜度。廣度優(yōu)先搜索（BFS）:從入口出發(fā)，離開入口后依次訪問與當(dāng)前位置鄰接的單元格（上下左右方向

9、），然后分別從這些相鄰單元格出發(fā)依次訪問它們的鄰接格 ，并使“先被訪問的單元格的鄰接格 先于 后被訪問的單元格的鄰接格”被訪問 ，直至訪問到迷宮出口 ，則找到了迷宮問題的最優(yōu)解 ， 即迷宮最短路徑。該算法的顯著特點是“層層推進(jìn)”，探索點會隨著探索的深入急劇增加，相 應(yīng)地，需要大量的空間用來保存探索過程的記錄 ，空間復(fù)雜度大。三、參考代碼:uses crt;constmigong:array 1.5,1.5 of integer=(0,0,-1,0,0), (0,-1,0,0,-1),(0,0,0。0), (0,-1,0,0,0), (-1,0,0,-1,0);迷宮數(shù)組fangxiang:arr

10、ay 1.4,1.2 of -1.1=(1,0),(0,1),(-1,0),(0,-1);方向增量數(shù)組type node=record lastx:integer; lasty:integer; nowx:integer; nowy:integer; pre:byte; dep:byte;end;上一位置坐標(biāo)當(dāng)前位置坐標(biāo)本結(jié)點由哪一步擴展而來 本結(jié)點是走到第幾步產(chǎn)生的記錄走法數(shù)組varlujing:array1.25 of node;closed,open,x,y,r:integer;procedure output;var i,j:integer;beginfor i:=1 to 5 do

11、beginfor j:=1 to 5 dowrite(migongi,j:4); writeln;end;i:=open;repeatwith lujingi dowrite(nowy:2,',',nowx:2,' <-'); i:=lujingi.pre;until lujingi.pre=0;with lujingi dowrite(nowy:2,',',nowx:2);end;beginclrscr;with lujing1 do begin 初始化第一步lastx:=0; lasty:=0; nowx:=1;nowy:=1;pre:

12、=0;dep:=1;end;closed:=0;open:=1;migong1,1:=1;repeatinc(closed); 隊列首指針加1,取下一結(jié)點for r:=1 to 4 do begin以4個方向擴展當(dāng)前結(jié)點x:=lujingclosed.nowx+fangxiangr,1; 擴展形成新的坐標(biāo)值y:=lujingclosed.nowy+fangxiangr,2;if not (x>5)or(y>5) or (x<1) or (y<1) or (migongy,x<>0) then begin未出界，未走過則可視為新的結(jié)點1記錄新的結(jié)點數(shù)據(jù)新結(jié)點由

13、哪個坐標(biāo)擴展而來新結(jié)點走到第幾步新結(jié)點由哪個結(jié)點擴展而來當(dāng)前結(jié)點的覆蓋范輸出找到的第一種方案inc(open); 隊列尾指針加with lujingopen do begin nowx:=x; nowy:=y;lastx:=lujingclosed.nowx; lasty:=lujingclosed.nowy;dep:=lujingclosed.dep+1; pre:=closed;圍end; migongy,x:=lujingclosed.dep+1; if (x=5) and (y=5) then begin writeln('ok,thats allright');out

14、put;halt;end; end;end;直到首指針大于等于尾指針，即所有結(jié)點已擴展完until closed>=open; end.四、編程調(diào)試方面：用廣度優(yōu)先算法進(jìn)行編成時，由于牽涉到回溯、遞歸等較復(fù)雜的算法 ，非常容易出錯。 尤其牽涉到復(fù)雜數(shù)據(jù)結(jié)構(gòu)隊列的操作，調(diào)試跟蹤比較麻煩。五、小結(jié)本論文主要討論一種解決迷宮最短路徑問題的經(jīng)典算法，從廣度優(yōu)先方面方面證明了該算法的正確性，分析了算法的時間空間復(fù)度 ，迷宮問題是一個古老的問題，要在迷宮中找到 出口，需要經(jīng)過一連串的的錯誤嘗試才能找到正確的路徑，有時甚至找不到路徑。 而且這里有很多方法可以完成迷宮問題，例如順序表，深度優(yōu)先遍歷，廣度優(yōu)先遍歷等，但是我寫不出程序。于是參考了數(shù)據(jù)結(jié)構(gòu)書和我以前的一些設(shè)計，所以我們這里用的是棧。在這個 問題中主要運用了棧的各種基本操作，例如構(gòu)造空棧，判斷棧是否為空，入棧操作，出棧操 作等等。通過這次的作業(yè)，我又學(xué)會了一種解決迷宮問題的方法，我很高興。當(dāng)讓在