概述
(wall-following algorithm)
又稱繞牆走算法,是一種用運用左手/右手法則進行迷宮搜尋的初級算法。
簡介
如果迷宮是簡單連通的,即迷宮的牆總是相互相連的或與迷宮的外輪廓相連,那么迷宮的搜尋者從起點開始將一隻手扶在牆面前行,總能保證不會迷失並且找到迷宮中存在的出口(若忽略出口將回到迷宮起點)。這種策略在剛進入迷宮時即執行的效果是最佳的。
另外可以從拓撲學的角度來看待這種搜尋策略。如果牆是互相連線的,那么它們可以被轉換成一個迴路或者說圓環。那么摸牆走就可以被看作是從一個圓環的起點行進至其到終點。
當迷宮不是簡單連通的,比如迷宮的起始或終止點在迷宮結構的內部並且其外部有迴路包圍,那么這種策略就不能保證出口一定會被找到。
摸牆算法還可以被套用到三維或更高維度的情況下,只要迷宮多出的維度可以用一種確定的方式投影到二維平面。比如在三維迷宮中,“上”這個方向可以被映射為二維平面中的“西北”,而“下”則可以被映射為“東南”。然後摸牆算法就可以被套用到這個被轉換後的模型中。然而不像二維平面,這種模型需要得知當前搜尋者的具體朝向,以便確定哪個方向才是第一個左手或右手方向。
左手摸牆算法流程圖: