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

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

2、法，即從入口出發(fā)，順某方向向前探索，若能走通，則繼續(xù)往前走；否 則沿原路退回。換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來(lái)保存從入口到當(dāng)前位置的路 徑。因此，在求迷宮通路的算法中應(yīng)用“?！币簿褪亲匀欢坏氖?。當(dāng)然還有其他的方法來(lái) 解決，例如順序表，深度優(yōu)先遍歷，廣度優(yōu)先遍歷等。【關(guān)鍵詞】：最短路徑；時(shí)間復(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一、問(wèn)題描述3二、算法31深度優(yōu)先搜索32廣度優(yōu)先搜索3三、參考代碼 4四、編程調(diào)試方面 5五、小結(jié)5六、參考文獻(xiàn) 5問(wèn)題描述迷宮最短路徑（the shortest path of maze）問(wèn)題是一個(gè)典型的搜索、遍歷問(wèn)題 ,其程序設(shè) 計(jì)想在人工智能設(shè)計(jì)、機(jī)器人設(shè)計(jì)等事務(wù)中均有應(yīng)用。如圖所示，一個(gè)NXM的大方塊迷宮，帶斜線的單元格表示墻壁（障礙），空白的單元格表示通道。迷宮問(wèn)題可以表述為：而迷宮最短路徑問(wèn)題就是找出從迷宮入口到出口所經(jīng)過(guò)單元格個(gè)數(shù)最少的路徑。求解迷

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

9、），然后分別從這些相鄰單元格出發(fā)依次訪問(wèn)它們的鄰接格 ，并使“先被訪問(wèn)的單元格的鄰接格 先于 后被訪問(wèn)的單元格的鄰接格”被訪問(wèn) ，直至訪問(wèn)到迷宮出口 ，則找到了迷宮問(wèn)題的最優(yōu)解 ， 即迷宮最短路徑。該算法的顯著特點(diǎn)是“層層推進(jìn)”，探索點(diǎn)會(huì)隨著探索的深入急劇增加，相 應(yīng)地，需要大量的空間用來(lái)保存探索過(guò)程的記錄 ，空間復(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é)點(diǎn)由哪一步擴(kuò)展而來(lái) 本結(jié)點(diǎn)是走到第幾步產(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); 隊(duì)列首指針加1,取下一結(jié)點(diǎn)for r:=1 to 4 do begin以4個(gè)方向擴(kuò)展當(dāng)前結(jié)點(diǎn)x:=lujingclosed.nowx+fangxiangr,1; 擴(kuò)展形成新的坐標(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未出界，未走過(guò)則可視為新的結(jié)點(diǎn)1記錄新的結(jié)點(diǎn)數(shù)據(jù)新結(jié)點(diǎn)由

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