跳至內容

解迷宮演算法

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書
正在走木製迷宮的機械人

解迷宮演算法又稱走迷宮演算法是一種自動求解迷宮的方法。解迷宮演算法主要可以分成兩大類，一種是用來走沒走過的迷宮且無法得知整個迷宮的方法，這類方法較常見的有隨機老鼠演算法、沿牆法、普萊吉演算法和特雷莫演算法；另一類是適用於可以一次看到整個迷宮時所使用的方法，這類方法較常見的有死路填充法和最短路徑演算法。

不包含循環路徑的迷宮稱為「簡單連接」或「完美」的迷宮，其等價於圖論中的樹。解迷宮演算法與圖論密切相關。直觀上來說，若以適當的方式拉開迷宮中的路徑，其結果可能會是一棵樹。[1][2]

概述

一個典型的解迷宮演算法會

  • 取描述某個迷宮環境的訊息做為輸入。例如：用一個矩陣，矩陣中每個數字用來代表迷宮裏面的一格；
  • 並且經過一些運算之後，給出有關「應該如何移動」的指示作為輸出。例如：+1, +1 表示「x坐標和y坐標都要各加1」。

演算法的輸入根據其類型而定：有的演算法是假設了「能以鳥瞰式的方式看到整個迷宮」為前提，所以輸入時會描述整個迷宮的環境；有的演算法是設計給機械人實際在迷宮裏走迷宮的，所以輸入時僅會描述機械人視線範圍內的環境[3]。 解迷宮演算法在人工智能、機械人學甚至是遊戲編程（遊戲內NPC的尋路演算法）等領域中都有相當的應用[4][5]。

另一方面，解迷宮演算法也引起了數學家的注意，因為這演算法與圖論中的演算法有相當的關連。例如：單連通的迷宮，迷宮中的路線簡單地連接着，並且不包含任何循環。這種迷宮相當於圖論中的樹狀圖：如果將迷宮中的路線拉開的話會得到類似圖論中討論的樹狀結構。[2]

  • 一個迷宮與其可能的路徑
    一個迷宮與其可能的路徑
  • 將迷宮中的路徑拉開成一個樹狀結構
    將迷宮中的路徑拉開成一個樹狀結構

隨機老鼠演算法

這是一種非常簡單的演算法，可以由非常不智能的機械人或一隻普通的老鼠來實現。這個演算法的內容就是單純的延着迷宮中的路徑前進，遇到岔路時，隨機選擇一個方向來前進。雖然這個方法最終總是能解開迷宮，但過程可能十分緩慢。[6]

沿牆法

使用右手規則走迷宮

解迷宮演算法中最著名的方法是沿牆法[7]，也稱為左手規則（左手法則、左手定則）或右手規則（右手法則、右手定則）[8]。如果迷宮是單連通的，也就是說迷宮的所有牆壁都與迷宮的外邊界相連，那麼只要靠着迷宮的一側牆不斷前進（或者說每次遇到岔路都轉向同個方向，如每次遇岔路都右轉或都左轉），那麼就能保證不迷路地到達迷宮的出口（如果有出口的話），如果迷宮沒有出口則會回到原地，且至少遍歷了與該牆連接的部分旁邊的每個走廊。這個演算法是一個深度優先的中序樹遍歷。

關於為何沿牆法能解迷宮的另一個觀點是基於拓樸學的解釋。如果迷宮是單連通的，代表迷宮的牆壁是相連的，且沒有迴路[9][10]，所以在一個這樣的迷宮裏，每當走迷宮那個人遇到岔路，每條岔路只有可能再分岔或者是死路。這就表示如果將這迷宮化成樹狀圖，這個樹狀圖不會有任何互相相交的分支，且在拓樸學上它們可能可以拓樸形變為一個環[11]，然後沿牆法可簡化為在這個環上從頭到尾繞一圈。為了進一步推進這個想法，可留意將迷宮牆壁的連通元件組合在一起，而這些元件的邊界正是迷宮的解。

起點位於被環狀通道包圍之結構的中心的迷宮使用右手規則結果繞回入口

如果迷宮不是單連通的，（例如起點和終點位於被環狀通道包圍之結構的中心、或者路徑互相交叉且能解迷宮的路徑的部分被環狀通道包圍）則沿牆法不一定有效。

另一個須留意的點是如果不是在迷宮入口處就開始就依循沿牆法走迷宮時。如果迷宮不是單連通的，並且是在迷宮中的任意點才開始依循沿牆法走迷宮，那麼可能會發現自己被困在單獨一堵牆之中，該牆壁圍繞着自己，並且無法返回入口也無法抵達出口，還會永遠沿着這一系列的牆打轉。如果是走迷宮半路上才開始依循沿牆法走迷宮時，應嘗試記住或標記迷宮中的一個點，並從那個點開始依循沿牆法走迷宮，因為沿牆法總是會帶你回到同一個地方，如果第二次又繞回同一個點，那麼就能斷定迷宮不是單連通的，這時就應該切換到另一面尚未依循的牆或方向。有關的替代方法可以參考下面列出的普萊吉演算法。

普萊吉演算法

左圖：依循左手規則走迷宮陷入循環；
右圖：依循普萊吉演算法成功走出迷宮

不相交（存在不與外邊界相連的牆之迷宮、或邊界不封閉的迷宮）的迷宮可以使用沿牆法解決。然而，如果從迷宮內部某點才開始求解迷宮，那麼使用沿牆法可能會沿着一道不與出口相連的牆，並且不斷繞着這些牆打轉。普萊吉演算法（Pledge algorithm；名稱取自約翰·普萊吉（John Pledge））可以解決這一問題。[12][13][14]

普萊吉演算法是為了要能夠避開障礙物而設計的，需要走迷宮那個人也許隨便選擇一個方向來做前進方向。當依循這個演算法走迷宮那個人撞到一塊障礙物的時候，他會轉方向，同時會一隻手會觸摸着舊東西一邊轉，並且會數旋轉的角度（例如順時針當正，逆時針當負）， 並且不斷嘗試把總共轉了的角變為0度（例如：如果走迷宮者左轉了，並走了一格就撞到可以右轉的地方的話，他會馬上右轉）。當走迷宮那個人轉到面向回他原本的前進方向時，總共轉的角（圖裏的「S」）會是0度，而走迷宮那個人會離開舊障礙物，繼續向着他原本的方向走。[12]

只有當「總共轉的角」（圖裏的「S」）和「當前方向」（圖裏的「H」）都為零時，手才會從牆上移開。這個演算法能夠幫走迷宮的那個人克服像拉丁字母「G」那樣形狀的無限循環陷阱（使用沿牆法時會在「G」形迷宮牆壁上不斷打轉）。

一個僅僅留意著自己目前方向的演算法會陷入一個無窮迴圈：以「G」形迷宮為例，一個僅僅留意著自己目前方向（圖裏的「H」）的演算法會讓走迷宮那個人走到最右下角向內凸出來那堵牆時左轉，並且走回去左手邊那一塊那裏，然後開始無限打轉。普萊吉演算法不會犯這個錯，因為在最右下角向內凸出來那堵牆的那一點「總共轉的角」不是0度（360度不當0度）， 所以那個人會沿着牆邊走到去左下角那一個出口。[12]

該演算法允許擁有指南針的人從任何有限二維迷宮的內部任何點找到前往外部出口的路，而不管從迷宮中的何處才開始依循此演算法，也就是無論從迷宮中的何處作為初始位置都能找到出口。然而，這個演算法在做相反的事情時不起作用，即找到從迷宮外面的入口到迷宮內某個目的地的路。

特雷莫演算法

依循特雷莫演算法解一個迷宮。大綠點表示當前位置，小藍點表示路徑上有1個記號，紅色叉叉表示路徑上有2個記號。一旦找到出口，就會標出通過單一記號的路徑

特雷莫演算法是由法國數學家查爾斯·皮埃爾·特雷莫（英語：Charles Pierre Trémaux）發明的[15]一種能有效地找到迷宮出路的方法[16][17]。這個方法需要在地板上畫線來標記路徑，只要迷宮有清楚定義了的通道就保證有效[18]。這種做法會把每條通道分成「沒去過的」、「去過一次的」、和「去過兩次的」三種。並且會接着以下的規則運行：

  • 每次第一次行經一條路時要做記號，這個記號要是在這條路的兩端都看得到的。所以如果那個記號是物理性（而不是用電腦記住）的話，這個記號要在這條路的兩端都留下；
  • 不進入做記號的位置上有兩個記號的路徑裏；
  • 接着有三個可能性：
    • 如果走到去一個什麼記號都沒有的岔路那裏，那麼就是選擇一條路走，並且做好記號；
      • 如果走進來那條路只有一個記號的話，那就回頭，「轉身返回」，再多做一次記號。這個情況表示前面是死路；
      • 如果都不是的話，則任意選擇具有最少記號的剩餘路徑走，並且做好記號。

「轉身返回」規則有效地將任何帶有循環的迷宮轉換為單連通的迷宮；每當我們找到一條可以循環的路徑時，我們就將其視為死路並返回。如果沒有這條規則，也就是說若遇到迷宮迴路時沒有回頭，而是隨意地走另一條路，就有可能切斷能進入迷宮中尚未探索部分的通道。

在用這個演算法走到去出口後，只要跟着「僅有做一次記號」的路徑當指示就能返回起點。如果迷宮根本沒有出口的話，這個方法會帶着走迷宮的人回去起點，而且每條路都會有兩個記號。在後者這個情況下，每條路恰好走過兩次，而兩個方向各一次。這個走路過程被人稱之為雙向雙重跟蹤（bidirectional double-tracing）[19]。

從本質上講，這種在19世紀發現的演算法在大約在發現後的一百年後被用作深度優先搜尋。[16][17]

死路填充演算法

外部影片連結
video icon 迷宮策略：死路填充法. [2022-09-06]. （原始內容存檔於2020-07-27）. 
video icon 解迷宮演算法. [2022-09-06]. （原始內容存檔於2021-02-06）. 
做完死路填充演算法的迷宮

死路填充演算法（dead-end filling）是一個解迷宮演算法，做法如下：[20]把迷宮裏的死路全部找出來；再用記號填滿所有死路，每條死路填到第一個岔路那裏；這樣就可以很容易看到整個迷宮裏有哪些路是能走的。這種做法可以拿來說明一個完全已知的迷宮，例如是在紙上面玩的迷宮遊戲，但是因為這個演算法要求解迷宮那個人能夠從迷宮上方鳥瞰看到整個迷宮，所以無法用於未知的迷宮。

死路填充演算法不會意外地切掉從起點到終點的路線，因為演算法的每一個步驟都保留了迷宮的拓樸結構。此外該過程不會提早結束，因為最終的結果不會包含任何死路。因此，如果所解的迷宮是一個完美的迷宮（沒有循環迴路的迷宮），那麼做完死路填充演算法後將會留下迷宮的解，也就是從入口到出口的路線；如果所解的迷宮帶有一些循環迴路，那麼做完死路填充演算法後將會保留迷宮的所有可行解，僅此而已。[21]

遞歸法

假如解迷宮的那個人知道整個迷宮的路線（例如是紙上面玩的迷宮遊戲），那麼透過一個簡單的遞歸演算法就能將這個迷宮從起點走到終點。這個演算法會接收一個起始的座標值：X和Y。如果X和Y的值不在一堵牆上面的話，這個演算法會在所有周圍鄰近的X和Y值呼叫自己，確保呼叫的是之前沒有使用過的這些X和Y值，而如果他找到終點的X和Y值，那他會以走過那些路以X和Y值的型式記下來一條正確路線。以下是這種演算法用Java程式語言寫出來的樣本： 

int[][] maze = new int[width][height]; //儲存整個迷宮的陣列，每個X和Y值都代表迷宮中的一個位置，「1」代表路，「2」代表牆。
boolean[][] wasHere = new boolean[width][height];
boolean[][] correctPath = new boolean[width][height]; // 迷宮解法陣列，等一下用來記下來解迷宮的正確路線。
int startX, startY; //設兩個變數做起點的X和Y值。
int endX, endY; //設兩個變數做終點的X和Y值。

public void solveMaze() {
   maze = generateMaze(); //產生出整個迷宮，「 1 」代表路，「 2 」代表牆。
   for (int row = 0; row < maze.length; row++)  
      // 將 boolean Arrays 設定為預設值
      for (int col = 0; col < maze[row].length; col++){
         wasHere[row][col] = false;
         correctPath[row][col] = false;
      }
   boolean b = recursiveSolve(startX, startY);

// 會得出一個 Boolean 的陣列（correctPath）
// 其中「真」（true）值會用來代表解迷宮的正確路線。
// 如果b為「假」（false），那就代表個迷宮根本是無解的。
}

public boolean recursiveSolve(int x, int y) {
   if (x == endX && y == endY) return true; // 如果到了終點，回傳「真」值出去。
   if (maze[x][y] == 2 || wasHere[x][y]) return false;  
// 如果撞到牆或已經來過這一點，回傳「假」值出去。
   wasHere[x][y] = true;
   if (x != 0) // 檢查一下是不是到了最左的邊界。
      if (recursiveSolve(x-1, y)) {
         correctPath[x][y] = true;
         return true;
      }
   if (x != width - 1) // 檢查一下是不是到了最右的邊界。
      if (recursiveSolve(x+1, y)) {
         correctPath[x][y] = true;
         return true;
      }
   if (y != 0)  // 檢查一下是不是到了最底的邊界。
      if (recursiveSolve(x, y-1)) {
         correctPath[x][y] = true;
         return true;
      }
   if (y != height - 1) // 檢查一下是不是到了最頂的邊界。
      if (recursiveSolve(x, y+1)) {
         correctPath[x][y] = true;
         return true;
      }
   return false;
}

鏟起迷宮演算法

鏟起迷宮演算法（maze-routing algorithm）是一種用來找出一個迷宮裏任意兩點之間之路線的方法。[22]這個演算法能夠得知兩點之間是不是真有路通到，而且無論個迷宮多大都好，他都能讓一個從迷宮內部開始走、記憶力有限、事前完全不知道個迷宮是什麼樣子的個體成功地解完迷宮，只是要求走迷宮的個體記住4個變數就可以找到這條路線出來。但是這個演算法不保證能找到最短路徑。

鏟起迷宮演算法用了曼哈頓距離（Manhattan distance；簡稱「MD」）的概念。這個概念指的是兩點之間的空間可以用格子代表，而假設一個個體只有沿着格子的邊線行走的話，在兩點之間穿梭都會有很多條「最短路線」，這些路線的長度就是以所謂的MD計算的。以下是一段偽代碼： 

Point src, dst;// 起點和終點的座標
// 「cur」表示現在的位置。
int MD_best = MD(src, dst);//儲存走迷宮個體和目的地之間的最短MD。
// 一條好（productive）的路線就是一條能夠讓MD最小化的路線。
while(cur != dst){
    if(there exists a productive path){
        Take the productive path;
    }else{
        MD_best = MD(cur, dst);
        Imagine a line between cur and dst; // 想像一條目前位置和目的地之間的線。
        Take the first path in the left/right of the line;
        while(MD(cur, dst) != MD_best || there does not exist a productive path) {
            Follow the right-hand/left-hand rule; // 使用沿牆法（左右手法則）。
    }
}

最短路徑演算法

更多資訊：尋路
一個有多種解且沒有死路的迷宮，在其中找到最短路徑可能很有用
使用廣度優先搜尋來解迷宮

當迷宮有多個解時，就會希望能找到入口到出口的最短路徑。有幾種演算法能找到最短路徑，其中大部分來自圖論。一種方法是使用廣度優先搜尋來找尋解迷宮的最短路徑，而另一種方法——A*搜尋演算法則是使用了啟發式的技術。廣度優先搜尋使用佇列以距離遞增的順序走訪迷宮的單元格，每個被走訪的單元格都需要追蹤它與起點的距離、哪個相鄰的單元格更靠近起點導致它被加進佇列中。找到迷宮的終點後，沿着單元格往回找到起點則為最短路徑。最簡單形式的廣度優先搜尋有其局限性，例如在加權圖中找到最短路徑。

參見

參考文獻

  1. ^ YouTube上的Maze to Tree
  2. ^ 2.0 2.1 Sadik, Adil MJ and Dhali, Maruf A and Farid, Hasib MAB and Rashid, Tafhim U and Syeed, A. A comprehensive and comparative study of maze-solving techniques by implementing graph theory. 2010 International Conference on Artificial Intelligence and Computational Intelligence (IEEE). 2010, 1: 52–56. 
  3. ^ Provost, Jefferson; Benjamin Kuipers; Risto Miikkulainen. Self-organizing distinctive-state abstraction for learning robot navigation. Connection Science. 2006, (18.2). doi:10.1080/09540090600768609. 
  4. ^ Mishra, Swati; Bande, Pankaj. Maze solving algorithms for micro mouse. 2008 IEEE International Conference on Signal Image Technology and Internet Based Systems (IEEE). 2008: 86–93. 
  5. ^ Wyard-Scott, L; Meng, Q-HM. A potential maze solving algorithm for a micromouse robot. IEEE Pacific Rim Conference on Communications, Computers, and Signal Processing. Proceedings (IEEE). 1995: 614–618. 
  6. ^ Babula, Michał. Simulated maze solving algorithms through unknown mazes. Organizing and Program Committee (Citeseer). 2009, 13. 
  7. ^ Saman, Abu Bakar Sayuti and Abdramane, Issa, Solving a reconfigurable maze using hybrid wall follower algorithm (PDF), 2013 
  8. ^ Zarkasi, Ahmad and Ubaya, Huda and Amanda, Cora Deri and Firsandaya, Reza. Implementation of ram based neural networks on maze mapping algorithms for wall follower robot. Journal of Physics: Conference Series (IOP Publishing). 2019, 1196 (1). 
  9. ^ Fritzke, Bernd. A growing neural gas network learns topologies. Advances in neural information processing systems. 1994, 7. 
  10. ^ Maze Types and Topology: A Summary. Amazeing Art. （原始內容存檔於2018-09-14）. 
  11. ^ YouTube上的Maze Transformed
  12. ^ 12.0 12.1 12.2 Klein, Rolf and Kamphans, Tom. Pledge's Algorithm-How to Escape from a Dark Maze. Algorithms Unplugged (Springer). 2011: 69–75. 
  13. ^ Abelson; diSessa, Turtle Geometry: the computer as a medium for exploring mathematics, 1980, ISBN 9780262510370 
  14. ^ Seymour Papert, Uses of Technology to Enhance Education (PDF), MIT Artificial Intelligence Memo No. 298, June 1973, （原始內容 (PDF)存檔於2017-07-06） 
  15. ^ Public conference, December 2, 2010 – by professor Jean Pelletier-Thibert in Academie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – ISSN 0980-6032)
    Charles Tremaux (° 1859 – † 1882) Ecole Polytechnique of Paris (X:1876), French engineer of the telegraph
  16. ^ 16.0 16.1 Even, Shimon. Graph Algorithms (2nd ed.). Cambridge University Press. 2011: 46–48. ISBN 978-0-521-73653-4. 
  17. ^ 17.0 17.1 Sedgewick, Robert. Algorithms in C++: Graph Algorithms (3rd ed.). Pearson Education. 2002. ISBN 978-0-201-36118-6. 
  18. ^ Lucas, Édouard. Récréations mathématiques Volume I. Récréations mathématiques. Gauthier-Villars. 1882. 
  19. ^ Maze Activity Using Maze Solving Algorithms (PDF). cs4all.org. （原始內容 (PDF)存檔於2020-03-28）. .
  20. ^ Maze Classification. astrolog.org. [2022-09-06]. （原始內容存檔於2019-04-06）. 
  21. ^ Fattah, Mohammad and Airola, Antti and Ausavarungnirun, Rachata and Mirzaei, Nima and Liljeberg, Pasi and Plosila, Juha and Mohammadi, Siamak and Pahikkala, Tapio and Mutlu, Onur and Tenhunen, Hannu. A low-overhead, fully-distributed, guaranteed-delivery routing algorithm for faulty network-on-chips. Proceedings of the 9th International Symposium on Networks-on-Chip. 2015: 1–8. 

外部連結

取自 "https://zh.wikipedia.org/w/index.php?title=解迷宮演算法&oldid=80499048"