text: 解迷宮演演算法又稱走迷宮演演算法是一種自動求解迷宮的方法。解迷宮演演算法主要可以分成兩大類，一種是用來走沒走過的迷宮且無法得知整個迷宮的方法，這類方法較常見的有隨機老鼠演演算法、沿牆法、普萊吉演演算法和特雷莫演演算法；另一類是適用於可以一次看到整個迷宮時所使用的方法，這類方法較常見的有死路填充法和最短路徑演演算法。不包含迴圈路徑的迷宮稱為「簡單連線」或「完美」的迷宮，其等價於圖論中的樹。解迷宮演演算法與圖論密切相關。直觀上來說，若以適當的方式拉開迷宮中的路徑，其結果可能會是一棵樹。概述.一個典型的解迷宮演演算法會演演算法的輸入根據其型別而定：有的演演算法是假設了「能以鳥瞰式的方式看到整個迷宮」為前提，所以輸入時會描述整個迷宮的環境；有的演演算法是設計給機械人實際在迷宮裡走迷宮的，所以輸入時僅會描述機械人視線範圍內的環境。解迷宮演演算法在人工智慧、機器人學甚至是遊戲程式設計等領域中都有相當的應用。另一方面，解迷宮演演算法也引起了數學家的注意，因為這演演算法與圖論中的演演算法有相當的關連。例如：單連通的迷宮，迷宮中的路線簡單地連線著，並且不包含任何迴圈。這種迷宮相當於圖論中的樹狀圖：如果將迷宮中的路線拉開的話會得到類似圖論中討論的樹狀結構。隨機老鼠演演算法.這是一種非常簡單的演演算法，可以由非常不智慧的機器人或一隻普通的老鼠來實現。這個演演算法的內容就是單純的延著迷宮中的路徑前進，遇到岔路時，隨機選擇一個方向來前進。雖然這個方法最終總是能解開迷宮，但過程可能十分緩慢。沿牆法.解迷宮演演算法中最著名的方法是沿牆法，也稱為左手規則，如果迷宮沒有出口則會回到原地，且至少遍歷了與該牆連線的部分旁邊的每個走廊。這個演演算法是一個深度優先的中序樹遍歷。關於為何沿牆法能解迷宮的另一個觀點是基於拓樸學的解釋。如果迷宮是單連通的，代表迷宮的牆壁是相連的，且沒有迴路，所以在一個這樣的迷宮裡，每當走迷宮那個人遇到岔路，每條岔路只有可能再分岔或者是死路。這就表示如果將這迷宮化成樹狀圖，這個樹狀圖不會有任何互相相交的分支，且在拓樸學上它們可能可以拓樸形變為一個環，然後沿牆法可簡化為在這個環上從頭到尾繞一圈。為了進一步推進這個想法，可留意將迷宮牆壁的連通}-當迷宮有多個解時，就會希望能找到入口到出口的最短路徑。有幾種演演算法能找到最短路徑，其中大部分來自圖論。一種方法是使用廣度優先搜尋來找尋解迷宮的最短路徑，而另一種方法——A*搜尋演演算法則是使用了啟發式的技術。廣度優先搜尋使用佇列以距離遞增的順序走訪迷宮的單元格，每個被走訪的單元格都需要追蹤它與起點的距離、哪個相鄰的單元格更靠近起點導致它被加進佇列中。找到迷宮的終點後，沿著單元格往回找到起點則為最短路徑。最簡單形式的廣度優先搜尋有其侷限性，例如在加權圖中找到最短路徑。
metadata.dataset: erhwenkuo/wikipedia-zhtw
metadata.title: 解迷宮演演算法
metadata.url: https://zh.wikipedia.org/wiki?curid=8104218