摸著牆走迷宮

在迷宮裡，要如何找到出口呢？

很多人應該都聽過「摸著牆壁走」的方法：只要一直摸著右邊（或者左邊）的牆走，最後一定可以走出迷宮（例如，「迷宮、黃金比、索馬立方體」這本書，就有提到這種策略）。

但是，為什麼這種策略可以行得通呢？


原來，在概念上，沿著一邊的牆壁走，就相當於在執行「深度優先搜尋」(DFS, depth-first search)。參考上面的圖形，應該可以給我們一些感覺：給定左側的小迷宮，目標是由 A 點走到 C 點；而迷宮的樹狀圖（在此先假設迷宮任兩點間只有唯一的一條路）如中間圖所示：最右側的圖，則畫出「摸著右側牆壁走」的路線（迷宮中的藍線，就相當於樹狀圖）。

這樣的走迷宮策略，有什麼限制嗎？如果，迷宮是多連通（multiple-connected，兩個迷宮格之間，不必然只有唯一的路）的，那怎麼辦呢？

一般來說，即使迷宮是多連通的，「摸著牆走迷宮」的策略依然行得通。例如，在下面的圖形裡，我們要從入口 A 點，走到出口 D 點。因為 F-E-I-M-N-O-P-L-K-G-F 構成一個圈 (circle, loop)，因此從 F 到 G 有兩條路可走：F-E-I-M-N-O-P-L-K-G 或者 F-G。中間的圖形，說明了沿著右側牆壁走，依然可以從 A 點走到 D 點。（事實上，只要「迷宮出入口」不在這個圈子內 --- 例如 J 點 --- 這個方法就行得通。）


像這樣的圖說，當然不能算是證明。不過，有了直觀後，通常證明就呼之欲出了。有趣的是，這樣的走迷宮策略，與現實生活處理問題的方式，還有著可類比之處：有 時，我們會找不到方法來解決現實環境碰到的問題。這種時候，或許只能依靠「摸著牆壁走」的方式，藉由拓展對問題（空間）的認知，一步一步地走出迷宮呢。