解迷宮演算法

解迷宮演算法gaai2 mai4 gung1 jin2 syun3 faat3（英文：maze-solving algorithm）係一類演算法，顧名思義係寫嚟教電腦程式行迷宮嘅。

一個機械人喺度行一個木造嘅迷宮，佢部電腦裏面應該有個有返咁上下功效嘅解迷宮演算法。

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

• 攞描述個迷宮環境嘅訊息做輸入 input－例：用一個矩陣，矩陣入面每個數字用嚟代表迷宮裏面嘅一格；
• 並且經過一啲運算之後，俾有關「應該點移動」嘅指示做輸出 output－例：+1, +1 表示「$x$ 坐標同 $y$ 坐標都要各加 1」。

個輸入視乎演算法類型而定：有啲演算法係寫嚟假設咗「部電腦經已鳥瞰式睇到嗮成個迷宮」做前題，所以 input 會描述嗮成個迷宮嘅環境；又有啲演算法係寫嚟教一部機械人行迷宮嘅，所以 input 只會描述機械人嘅視線範圍內嘅環境。解迷宮演算法呢家嘢喺人工智能、機械人學以至遊戲編程（教隻遊戲入面嘅角色點樣搵路）等嘅領域上相當常用。

另一方面，解迷宮演算法又引起咗數學家嘅注意，因為呢啲演算法同數學當中嘅圖論（graph theory）相當有拏褦：例如係「簡單噉連住」（simply connected）嘅迷宮噉，「簡單噉連住」或者「完美」迷宮係指唔包含任何循環（loop）喺入面嘅迷宮；呢種迷宮查實相當於圖論當中嘅樹狀圖（tree graph）－如果將行一個完美迷宮嗰陣嘅可能路線拉開嘅話，會得出一個好似圖論入面所講嘅樹狀圖噉嘅嘢。

常用演算法

睇埋：迷宮同搵路

隨機老鼠

隨機老鼠演算法（random mouse algorithm）係最簡單粗糙嗰種解迷宮演算法，教個程式完全唔靠任何技巧，齋靠耐性－隨機噉行，希望總有一日撞到啱嗰條路（「好似一條完全唔知自己做緊乜嘅老鼠噉」）。隨機老鼠演算法用虛擬碼表達嘅話如下：

 沿住家吓條路一路係噉直行，直至撞到一個交叉口；
 到咗交叉口，喺個交叉口嗰度是但（即係隨機噉）揀個方向轉過去；
 重複上述嘅程序。

事實係，假設個迷宮真係有出口嘅話，隨機老鼠演算法實會搵到出口，但用呢個方法行迷宮慢得好交關而且好冇技巧，喺實際應用上，唔會有專業嘅人用呢個演算法嚟解迷宮。

跟牆行

用跟牆行演算法解一個迷宮嘅路線圖

跟牆行演算法（wall follower）係最出名嗰種解迷宮演算法，又有叫做左手法則（left-hand rule）或者右手法則（right-hand rule）。如果個迷宮係簡單噉連住嘅話，佢啲牆冚唪唥都係一係相連一係連住個迷宮嘅外圍界限嘅，噉個人如果將佢其中一隻手一路掂住個迷宮埲牆一路行嘅話實唔會蕩失路，實會揾到個出口（假設個迷宮真係有個出口嘅話）。而如果個迷宮係冇出口嘅，佢會去勻個迷宮嘅每條走廊之後隻手會返到去開始嗰點嗰度。

總結嚟講，跟牆行演算法個做法如下：

1. 將是但一隻手掂住個迷宮埲牆。
2. 一路行一路隻手要掂住埲牆－唔可以中途放手。
3. 如果個迷宮係簡單噉連住嘅，最後會行到去出口。
4. 如果最後隻手返到去原先嘅位置，就表示個迷宮唔係簡單噉連住嘅。

點解掂

由拓樸學嘅角度分析可以了解跟牆行演算法點解掂。喺定義上，「簡單噉連住」嘅迷宮啲牆係冚唪唥都相連住嘅，即係冇循環路，所以喺一個噉嘅迷宮入面，每當行迷宮嗰個人撞到分叉路，每條分叉淨係有得再分叉或者做倔頭路。噉即係表示，如果將個人嘅可能路線畫做一幅樹狀圖嘅話，呢幅樹狀圖唔會有任何互相交叉嘅分枝，而且個迷宮有得變形做一個圓圈。即係話靠跟牆行演算法解一個迷宮基本上等同沿住一個圓圈由起點行到去終點噉樣。

弱點

當然，跟牆行演算法都有佢嘅弱點：首先，上述講咗呢柞嘢係以「個迷宮係簡單噉連住嘅」做前題嘅，如果個迷宮唔係簡單噉連住嘅話（例如係個入口或者出口喺個迷宮中心，俾循環路圍住；又或者係啲路彼此之間會喺對方上面或者下面過，而正確路線嘅某啲部份俾循環路圍住），跟牆行演算法就會行唔通；另一方面，如果一個人喺行行吓到咗半路先至開始用跟牆行演算法，而個迷宮唔係簡單噉連住嘅話，佢可能會永世沿住一列循環嘅牆打轉。如果一個人行到半路先開始用跟牆行演算法嘅話，佢可以搵個方法記低佢開始用跟牆行演算法嗰點，而因為跟牆行演算法如果去唔到出口隻手係會去返到去起點嘅，所以噉做起碼會幫到佢知道個迷宮係咪簡單噉連住嘅。

Pledge

左手邊：一個齋向左行嘅人俾個迷宮難到；
右手邊：用 Pledge 演算法成功噉解到個迷宮。

正如頭先提咗，跟牆行演算法有漏洞：例如係如果個起點喺個迷宮裡面，而個迷宮唔係簡單噉連住嘅話，個起點可能會噉啱得噉橋喺正一個啲牆同個出口嗰啲唔連接嘅地點，搞到用跟牆行演算法嘅人會永世喺個迷宮裡面打轉。但係 Pledge 演算法（Pledge algorithm；個名取自 Jon Pledge）曉解決呢個問題。

Pledge 演算法係為咗要能夠避開障礙物而設計嘅，需要行迷宮嗰個人或者俾指示嗰個人是但揀個方向嚟做前進方向。當跟呢個演算法行迷宮嗰個人撞到一舊障礙物嗰陣時，佢會轉方向，同時會一隻手會掂住舊嘢一路轉，個人會數住佢轉咗嘅角度（例如順時針當正，逆時針當負），並且時刻噉嘗試將個總共轉咗嘅角變做 0 度（例如係如果佢轉咗左，而行咗一格就撞到可以轉右嘅地方嘅話，佢會即刻轉右）。當行迷宮嗰個人轉到面向返佢原本嘅前進方向嗰陣，總共轉咗嘅角（圖入面個「S」）會係 0 度，而行迷宮嗰個人會離開舊障礙物，繼續向住佢原本個方向行。呢個演算法能夠幫到行迷宮嗰個人克服好似拉丁字母「G」噉形嘅陷阱。

一個淨係留意住自己目前方向嘅演算法會陷入一個無窮嘅循環：用返「G」形迷宮做例子，一個淨係曉記得自己目前方向（圖入面個「H」）嘅演算法會令到行迷宮嗰個人喺去到最右下角嗰埲牆嗰陣轉左，並且行返入去左手邊嗰一忽嗰度。Pledge 演算法唔會犯呢個錯，因為喺最右下角嗰埲牆嗰一點嗰度「總共轉咗嘅角」唔係 0 度（360 度唔當係 0 度），所以個人會沿住啲牆一路行返到去左下角嗰一個出口。

Pledge 演算法幫到一個攞住指南針嘅人由一個兩維嘅迷宮入面是但一點行到去個迷宮外面－無論佢個起點喺邊都好。但係呢個演算法做唔到相反嘅嘢－唔能夠幫個人由個迷宮外面行去一個身處於迷宮內部嘅目的地。

Trémaux

用 Trémaux 演算法解一個迷宮。

Trémaux 演算法（Trémaux algorithm）係由法國數學家 Charles Pierre Trémaux 發明嘅，係一種用到喺地下度畫線嘅解決迷宮方法，只要個迷宮有清楚定義咗嘅通道就包保有效。呢種做法會將每條通道分做「未去過嘅」、「去過一次嘅」、同埋「去過兩次嘅」三種。並且會跟住以下嘅規則運行：

• 每次第一次行經一條路嗰陣要做記號，個記號要係喺條路嘅兩端都睇得到嘅。所以如果個記號係物理性（而唔係用電腦記住）嘅話，噉個記號要喺條路嘅兩端都留低；
• 唔好行入去做咗兩個記號嘅路入面；
• 跟住有三個可能性：
  • 如果行到去一個乜記號都冇嘅交叉位嗰度，噉就是但揀一條路行，要跟住佢行，並且做好記號；
    • 如果行入嚟嗰條路得一個記號嘅話，噉就返轉頭，再做多個記號－呢個情況表示前面係倔頭路；
    • 再如果唔係嘅話，喺淨低行得嘅路嗰度揀最少記號嗰條，跟住佢行，並且做好記號。

喺用呢個演算法行到去出口之後，跟住啲得一個記號嘅路行就可以一路行返去起點嗰度。如果個迷宮根本冇出口嘅話，呢個方法會帶行迷宮嗰個人返返去起點，而且每條路都會有兩個記號－喺後者呢個情況下，個人每條路都行過兩次，而兩個方向各一次。呢個行路過程俾人稱之為雙向雙重跟蹤（bidirectional double-tracing）。

倔頭路充填法

倔頭路充填法（dead-end filling）係一個演算法，做法如下：將個迷宮入面嗰啲倔頭路冚唪唥揾嗮出嚟；再用啲記號填滿嗮啲倔頭路，一路填到第一個交叉位嗰度；噉就可以好容易睇到嗮成個迷宮入面有邊啲路係行得嘅。呢種做法可以攞嚟解一個完全已知嘅迷宮，例如係喺紙上面玩嘅迷宮遊戲，但係因為佢要求解迷宮嗰個人能夠由上高鳥瞰睇到嗮成個迷宮，所以幫唔到手解一啲未知嘅迷宮。

倔頭路充填法嘅好處係，無論個迷宮係咪完美（冇循環）嘅都好，呢個演算法都會解到個迷宮：呢個做法唔會擝走啲唔係倔頭嘅路，所以如果個迷宮係完美嘅，噉用咗倔頭路充填法之後衹會淨低條正確路線；而如果個迷宮係唔完美（有循環）嘅，噉用咗倔頭路充填法之後會淨低所有嘅可行路線。

遞迴法

假如解迷宮嗰個人知道嗮成個迷宮嘅路線（例如係紙上面玩嘅迷宮遊戲），一個簡單嘅遞迴演算法就幫到個人由起點一路行到終點。個演算法會接收一個起始嘅值：X 同 Y。如果 X 同 Y 嘅值唔喺一埲牆上面嘅話，個演算法會記返所有周圍鄰近嘅 X 同 Y 值，確保自己唔會返用啲 X 同 Y 值，而如果佢揾到終點嘅 X 同 Y 值，噉佢會以行過嗰啲路嘅 X 同 Y 值嘅型式記低條正確路線。以下係呢種演算法用 Java 程式語言寫出嚟嘅樣本：

int[][] maze = new int[width][height]; // 幫個迷宮每一點設返個 X 同 Y 值代表佢方位－呢個演算法假設咗個人知道嗮個迷宮係點樣嘅。
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 係假，噉就代表個迷宮根本係冇可能解到嘅。
}

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) // Check 吓係咪到咗最左嘅邊界。
      if (recursiveSolve(x-1, y)) {
         correctPath[x][y] = true;
         return true;
      }
   if (x != width - 1) // Check 吓係咪到咗最右嘅邊界。
      if (recursiveSolve(x+1, y)) {
         correctPath[x][y] = true;
         return true;
      }
   if (y != 0)  // Check 吓係咪到咗最底嘅邊界。
      if (recursiveSolve(x, y-1)) {
         correctPath[x][y] = true;
         return true;
      }
   if (y != height - 1) // Check 吓係咪到咗最頂嘅邊界。
      if (recursiveSolve(x, y+1)) {
         correctPath[x][y] = true;
         return true;
      }
   return false;
}

剷起迷宮

兩點之間嘅空間可以用格仔代表，綠色線係最短距離，但係現實係，好多時實際應用嗰度都冇得由 A 點直線行去 B 點－好似係喺曼哈頓揸車揾食嘅的士司機嘅處境噉。

剷起迷宮演算法（maze-routing algorithm）係一種用嚟揾出一個迷宮入面是但兩點之間嘅路線嘅方法。呢個演算法識得睇到嗰兩點之間係咪真係有路通到 ，而且無論個迷宮幾大都好，佢都幫到個由迷宮內部開始行、記憶力有限、兼事前完全唔知道個迷宮係乜樣嘅個體成功噉解到個迷宮，淨係要求行迷宮嗰個人記住 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* 搜尋演算法
• 程式編寫
• 人工智能
• 電子遊戲 AI

拎

• Think Labyrinth: Maze algorithms (details on these and other maze solving algorithms)
• MazeBlog: Solving mazes using image analysis
• Video: Maze solving simulation
• Simon Ayrinhac, Electric current solves mazes, © 2014 IOP Publishing Ltd.