摸牆算法

摸牆算法稱繞牆走算法，是一種用運用左手/右手法則進行迷宮搜尋的初級算法。

基本介紹

• 中文名：摸牆算法
• 外文名：wall-following algorithm
• 拼音：Mo Qiang Suan Fa
• 別稱：繞牆走算法
• 法則：左手/右手法則

概述

（wall-following algorithm）

又稱繞牆走算法，是一種用運用左手/右手法則進行迷宮搜尋的初級算法。

簡介

如果迷宮是簡單連通的，即迷宮的牆總是相互相連的或與迷宮的外輪廓相連，那么迷宮的搜尋者從起點開始將一隻手扶在牆面前行，總能保證不會迷失並且找到迷宮中存在的出口(若忽略出口將回到迷宮起點)。這種策略在剛進入迷宮時即執行的效果是最佳的。

另外可以從拓撲學的角度來看待這種搜尋策略。如果牆是互相連線的，那么它們可以被轉換成一個迴路或者說圓環。那么摸牆走就可以被看作是從一個圓環的起點行進至其到終點。

當迷宮不是簡單連通的，比如迷宮的起始或終止點在迷宮結構的內部並且其外部有迴路包圍，那么這種策略就不能保證出口一定會被找到。

摸牆算法還可以被套用到三維或更高維度的情況下，只要迷宮多出的維度可以用一種確定的方式投影到二維平面。比如在三維迷宮中，“上”這個方向可以被映射為二維平面中的“西北”，而“下”則可以被映射為“東南”。然後摸牆算法就可以被套用到這個被轉換後的模型中。然而不像二維平面，這種模型需要得知當前搜尋者的具體朝向，以便確定哪個方向才是第一個左手或右手方向。

左手摸牆算法流程圖：