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

1、算法分析與設(shè)計查找迷宮的最短路徑(深度算法)計算機科學(xué)與技術(shù)12級16班 2012/12/16 【摘要】：迷宮求解是一個古老的游戲，要在迷宮中找到出口，需要經(jīng)過一連串的錯誤嘗試才能找到正確的路徑，有的時候甚至找不到路徑。類似于給定一個m*n的矩形網(wǎng)格，設(shè)其左上角為起點S。一輛汽車從起點出發(fā)駛向右下角終點T。在若干網(wǎng)格處設(shè)置了障礙，表示該網(wǎng)格不可到達。設(shè)計一個算法，求汽車從起點S出發(fā)到達終點T的一條路線。用計算機求解這個問題時，我們通常采用的是回溯方法，即從入口出發(fā)，順某方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回。換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置

2、上都能沿原路退回，顯然需要用一個后進先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中應(yīng)用“?！币簿褪亲匀欢坏氖?。當(dāng)然還有其他的方法來解決，例如順序表，深度優(yōu)先遍歷，廣度優(yōu)先遍歷等。【關(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 a series of trial and error to find the right path , and sometimes not ev

3、en 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 grid , indicates that the grid is unreachable . Design an algorithm , find t

4、he 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 forward to explore a direction , if we go through , and continue to move forward ; otherwise return

5、 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 to save the path from the entrance to the current position . Therefore ,

6、in seeking 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 phrase】Shortest path ; time complexity ; deep-first search目錄摘要1關(guān)鍵字1Summary1一、問題描述3二、

7、算法分析3三、設(shè)計方案31總體方案32主要設(shè)計思路3四、時間復(fù)雜度6五、總結(jié)6六、參考文獻7七、附錄7一、 問題描述迷宮最短路徑( the shortest path of maze) 問題是一個典型的搜索、遍歷問題, 其程序設(shè)計想在人工智能設(shè)計、機器人設(shè)計等事務(wù)中均有應(yīng)用。如圖 所示, 一個NM的大方塊迷宮, 帶斜線的單元格表示墻壁( 障礙) , 空白的單元格表示通道。迷宮問題可以表述為:尋找從某一個給定的起始單元格( 迷宮入口) 出發(fā), 經(jīng)由行相鄰或列相鄰的通道單元格, 最終可以到達目標(biāo)單元格( 迷宮出口) , 所走過的單元格序列。行進中, 只能沿上下左右四個方向前進。而迷宮最短路徑問題就

8、是找出從迷宮入口到出口所經(jīng)過單元格個數(shù)最少的路徑。二、 算法分析從入口出發(fā), 順著某一方向向前探索, 若能走通, 則繼續(xù)往前走; 否則沿原路退回( 回溯) , 換一個方向再繼續(xù)探索, 直至所有可能的通路都探索到為止。如果恰好某一步探索到出口, 則就找到了從入口到出口的路徑。為了保證在任何位置上都能沿原路退回, 防止死循環(huán), 需要使用堆棧來保存大量記錄。而要求解迷宮最短路徑, 則必須用深度優(yōu)先搜索出所有到達出口的路徑, 通過比較得到最短距離的路徑, 這樣也必然要求增加數(shù)據(jù)空間來保存搜索過程中當(dāng)前最短路徑, 增加了空間復(fù)雜度。三、 設(shè)計方案1總體方案 走迷宮問題的走迷宮的過程可以模擬為一個搜索的過

9、程：每到一處，總讓它按東、南、西、北、4個方向順序試探下一個位置；如果某方向可以通過，并且不曾到達，則前進一步，在新位置上繼續(xù)進行搜索；如果4個方向都走不通或曾經(jīng)到達過，則退回一步，在原來的位置上繼續(xù)試探下一位置。每前進或后退一步，都要進行判斷：若前進到了出口處，則說明找到了一條通路；若退回到了入口處，則說明不存在通路。2主要設(shè)計思路用一個字符類型的二維數(shù)組表示迷宮，輸入值的范圍是0，1，其中0表示路徑，1為非路徑(即障礙)，輸入的矩陣大小和矩陣的內(nèi)容是靠手動輸入。設(shè)計一個模擬走迷宮的算法，為其尋找一條從入口點到出口點的通路。解決迷宮問題，面對的第一個問題是迷宮的表示方法。假定用n*m矩陣來描

10、述迷宮。左上角為入口，右下角為出口。n和m分別表示迷宮的行數(shù)和列數(shù)。矩陣中，0表示可通行的路徑，1代表障礙。如圖1-1表示4*6的迷宮矩陣表示。011000000100 000000011000圖1-1 迷宮問題的矩陣表示如果現(xiàn)在的位置（i,j）,則下一步有：上、下、左、右四種走法，如圖1-2表示。(i-1,j)(i,j-1)（i,j）(i,j+1)(i+1,j)圖1-2 四種可能的移動方向迷宮內(nèi)部的位置有四種移動的位置：上、下、左、右。而迷宮的邊界位置有兩種或三種可能的移動。為避免在處理內(nèi)部和邊界位置是存在差異，可在迷宮的周圍增加一圈障礙物，如圖1-3表示。11111111101100011

11、0001001100000011011000111111111圖1-3 為迷宮增加一圈障礙物增加一圈障礙物之后，原迷宮中的每個位置都可以有四種移動方向。而且可以使程序不必去處理邊界條件，從而大大簡化代碼的設(shè)計。這種簡化是以稍稍增加數(shù)組amze的空間為代價的。分別用x和y來指定每個迷宮位置的行坐標(biāo)和列坐標(biāo)。可以定義一個類class T來表示迷宮的位置。class T /定義描述迷宮中當(dāng)前位置的結(jié)構(gòu)類型public: int x; /x代表當(dāng)前位置的行坐標(biāo) int y; /y代表當(dāng)前位置的列坐標(biāo) int dir; /0:無效,1:右,2:下,3:左,4:上;當(dāng)輸入一個二維數(shù)組時，每次輸入的元素都存

12、放在一個棧里面。所以定義一個棧Stack用于存放二維數(shù)組元素。這里用到棧，棧是限定盡在表位進行插入和刪除的線性表。對于棧來說，允許進行插入和刪除的一段，稱為棧頂；不允許插入和刪除的另一端，則成為棧底。在這個問題中主要運用了棧的各種基本操作，例如構(gòu)造空棧，判斷棧是否為空，入棧操作，出棧操作等等。這里是棧的一個重要應(yīng)用，就是實現(xiàn)遞歸。 class Stack public: Stack(); /構(gòu)造函數(shù)，置空棧 Stack(); /析構(gòu)函數(shù) void Push(T e); /把元素data壓入棧中 T Pop(); /使棧頂元素出棧 T GetPop(); /取出棧頂元素 void Clear()

13、; /把棧清空 bool empty(); /判斷棧是否為空，如果為空則返回1，否則返回0private: LinkNode *top; ; /指向第一個結(jié)點的棧頂指針調(diào)試結(jié)果如圖1-4：圖1-4 迷宮和矩陣的建立如果位置（i,j）的下一步的四個方向都是可以走的，假設(shè)出發(fā)的先后順序是向上.向下.向左.向右。每個結(jié)點都是按照先后順序來決定下一個結(jié)點的方向。一旦做出了決定，就需要知道下一個位置的坐標(biāo)?？赏ㄟ^保留一個如圖1-5所示的偏移量表來計算這些坐標(biāo)?？梢园严蛴?向左.向下.向上移動分別編號為0.1.2.3。在圖1-3中，movei.x和movei.y分別給出了從當(dāng)前位置沿方向移動到下一個相連位

14、置時，x和y坐標(biāo)的增量。方向索引值（dir）movedir.xmovedir.x方向001右110下20-1左3-10上圖1-5 偏移量表因此假設(shè)現(xiàn)在的位置是（2，3），則其右邊相連位置坐標(biāo)的行坐標(biāo)為2+move0.x=2,列坐標(biāo)為3+move0.y=4.定義一個主函數(shù)int main()，用于調(diào)用其他函數(shù)實現(xiàn)函數(shù)的嵌套調(diào)用，實現(xiàn)整個程序。這里運用的二維指針我是參考書上的。int main() int m=0,n=0; /定義迷宮的長和寬 int *maze; /定義二維指針存取迷宮maze=GetMaze(m,n); /調(diào)用GetMaze(int &m,int &n)函數(shù)，得到迷宮 if(M

15、azepath(maze,m,n) /調(diào)用Mazepath(int *maze,int m,int n)函數(shù)獲取路徑 cout迷宮路徑探索成功!n; else cout路徑不存在!n; return 0;調(diào)試結(jié)果：圖1-6 搜索迷宮完成界面四、 時間算法復(fù)雜度：O(n）（不確定,我不太會算這個。）對相關(guān)問題的思考：這個迷宮問題的算法中，要在開始設(shè)置迷宮的大小。在探索迷宮路線的過程中，是通過不斷的嘗試來得到最終的結(jié)果，由于不能對已經(jīng)設(shè)定為可走路徑進行返回，所以在這個算法中有時候可能不能得到走出迷宮的路徑。五、 總結(jié)本次設(shè)計進展比較順利，如期完成，并且達到了預(yù)先的設(shè)計要求，完全貫徹和執(zhí)行了設(shè)計的總

16、體方案。對于迷宮求解的模擬實現(xiàn)比較成功。然而，限于時間和水平，這個設(shè)計還有很多的不足之處。迷宮問題是一個古老的問題，要在迷宮中找到出口，需要經(jīng)過一連串的的錯誤嘗試才能找到正確的路徑，有時甚至找不到路徑。而且這里有很多方法可以完成迷宮問題，例如順序表，深度優(yōu)先遍歷，廣度優(yōu)先遍歷等，但是我寫不出程序。于是參考了數(shù)據(jù)結(jié)構(gòu)書和我以前的一些設(shè)計，所以我們這里用的是棧。在這個問題中主要運用了棧的各種基本操作，例如構(gòu)造空棧，判斷棧是否為空，入棧操作，出棧操作等等。通過這次的作業(yè)，我又學(xué)會了一種解決迷宮問題的方法，我很高興。當(dāng)讓在完成設(shè)計過程中，我也遇到了很多難題，比如用什么辦法解決問題，怎樣創(chuàng)建調(diào)用棧等等，

17、但在再次復(fù)習(xí)了當(dāng)時所學(xué)的C+,數(shù)據(jù)結(jié)構(gòu)等課程后，發(fā)現(xiàn)這些問題還是可以解決的，而且解決的方法不止一種。在這里我參考的最多的是數(shù)據(jù)結(jié)構(gòu)中“棧的應(yīng)用”那一節(jié)的知識，它給我了很大幫助。本程序雖然簡短，但是卻有很多難點出現(xiàn)。首先是對基類的調(diào)試。為了減少調(diào)試的難度，我先調(diào)試了一下類的程序。剛開始是在主函數(shù)里面直接對程序賦值，發(fā)現(xiàn)這將大大限制程序的可重用性，而且無法靈活運用。在指導(dǎo)老師的幫助下，我將程序改成用鍵盤直接輸出，這樣的話方便實現(xiàn)。當(dāng)然，在我遇到苦難時候，老師和同學(xué)的幫助也是很大的。他們使我進步。也讓我體會到了成功的來之不易，只有真正付出過才有滿意的收獲。在此，我誠心的對所有幫助過我的老師、學(xué)長、同

18、學(xué)們說一句：謝謝！ 六、 參考文獻1 嚴(yán)蔚敏, 吳偉民.數(shù)據(jù)結(jié)構(gòu)M.北京: 清華大學(xué)出版社, 2002.2 陳媛.算法與數(shù)據(jù)結(jié)構(gòu)M.北京: 清華大學(xué)出版社, 2005.3 蘇德富.計算機算法設(shè)計與分析M.北京: 電子工業(yè)出版社, 2005.七、 附錄：#includeusing namespace std;class T /定義描述迷宮中當(dāng)前位置的結(jié)構(gòu)類型public: int x; /x代表當(dāng)前位置的行坐標(biāo) int y; /y代表當(dāng)前位置的列坐標(biāo) int dir; /0:無效,1:右,2:下,3:左,4:上;class LinkNode /鏈表結(jié)點 friend class Stack;pu

19、blic: T data; LinkNode *next;class Stack public: Stack(); /構(gòu)造函數(shù)，置空棧 Stack(); /析構(gòu)函數(shù) void Push(T e); /把元素data壓入棧中 T Pop(); /使棧頂元素出棧 T GetPop(); /取出棧頂元素 bool empty(); /判斷棧是否為空，如果為空則返回1，否則返回0private: LinkNode *top; /指向第一個結(jié)點的棧頂指針;Stack:Stack() /構(gòu)造函數(shù)，置空棧 top=NULL;Stack:Stack() /析構(gòu)函數(shù)void Stack:Push(T e) /把

20、元素x壓入棧中 LinkNode *P; P=new LinkNode; P-data=e; P-next=top; top=P;T Stack:Pop() /使棧頂元素出棧 T Temp; LinkNode *P; P=top; top=top-next; Temp=P-data; delete P; return Temp;T Stack:GetPop() /取出棧頂元素 return top-data;bool Stack:empty() /判斷棧是否為空，如果為空則返回1，否則返回0 if(top=NULL) return 1; else return 0;int move42=0,1

21、,1,0,0,-1,-1,0; /定義當(dāng)前位置移動的4個方向bool Mazepath(int *maze,int m,int n); /尋找迷宮maze中從（0，0）到（m,n）的路徑 /到則返回true,否則返回falsevoid PrintPath(Stack p); /輸出迷宮的路徑int* GetMaze(int &m,int &n); /獲取迷宮 /返回存取迷宮的二維指針int main() int m=0,n=0; /定義迷宮的長和寬 int *maze; maze=GetMaze(m,n); /調(diào)用GetMaze(int &m,int &n)函數(shù)，得到迷宮 if(Mazepat

22、h(maze,m,n) /調(diào)用Mazepath(int *maze,int m,int n)函數(shù)獲取路徑 cout迷宮路徑探索成功!n; else cout路徑不存在!n; return 0;int* GetMaze(int &m,int &n)/返回存取迷宮的二維指針 int *maze; /定義二維指針存取迷宮 int i=0,j=0; coutab; /輸入迷宮的長和寬 cout請輸入迷宮內(nèi)容:n; m=a; n=b; /m,n分別代表迷宮的行數(shù)和列數(shù) maze=new int *m+2; /申請長度等于行數(shù)加2的二級指針 for(i= 0;im+2;i+) /申請每個二維指針的空間 m

23、azei=new intn+2; for(i=1;i=m;i+) /輸入迷宮的內(nèi)容，1代表不通，0代表可通 for(j=1;jmazeij; for(i=0;im+2;i+) mazei0=mazein+1=1; for(i=0;in+2;i+) maze0i=mazem+1i=1; return maze; /返回存貯迷宮的二維指針maze;bool Mazepath(int *maze,int m,int n)/尋找迷宮maze中從（0，0）到（m,n）的路徑 /到則返回true,否則返回false Stack q,p; /定義棧p、q,分別存探索迷宮的過程和存儲路徑 T Temp1,Te

24、mp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push(Temp1); /將入口位置入棧 p.Push(Temp1); maze11=-1; /標(biāo)志入口位置已到達過 while(!q.empty() /棧q非空，則反復(fù)探索 Temp2=q.GetPop(); /獲取棧頂元素 if(!(p.GetPop().x=q.GetPop().x&p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入棧，則把上一個探索的位置存入棧p for(loop=0;loop4;loop+) /探索當(dāng)前位置的4個相鄰位置 x=Temp2.x+moveloop0; /計算出新位置x位置值 y=Temp2.y+moveloop1; /計算出新位置y位置值 if(mazexy=0) /判斷新位置是否可達 Temp1.x=x; Temp1.y=y; mazexy=-1; /標(biāo)志新位置已到達過 q.Push(Temp1); /新位置入棧 if(x=(m)&(y=(n) /成功到達出口 Temp1.x=m; Temp1.y=n; Temp1.dir=0; p.Push(Temp1); /把最后一個位置入棧 PrintPath(p); /輸出路徑 return true; /表示成功找到路徑 if(p.