解迷宮的一個數學方法

這篇文章翻譯自這裏,原作者是我,想可能早有數學家提出,只不過是了一了自己的心願而已。
要解迷宮就必須借助矩陣,而且一定是具備可解的條件,就是迷宮可清清楚楚地拆開成由外而內的一層層,每一層之間是獨立(換句話說,如何改動這一層也影響不了另一層的空間分佈),而用可通達性矩陣(accessibility matrix)就可以完整地描述這一層的空間分佈,而每一層的空間分佈指的是它到底被牆璧分成了幾多個不可以不經另一層才抵達的區間,簡單點說,如果第一層被分成了三區間,玩家處身於其中一個區間中是不可能在同一層穿牆而到另一個區間,其他遊戲的物件也需循守同樣的規則,這些區間亦是獨立的,發生在一區間的事不可以影響的另一區間。另外,我們亦假設玩家必須由一層進入最近的一層,不可以有隊道由第一層跳到第三層。
可通達性矩陣(accessibility matrix)就是整個解迷宮方式的靈魂,它借用了圖論的慨念,把一層中各區間能否去到另一層的各區間用1和0去表達,例如第一層有3個區間而第二層有5個區間,則我們可以用一3*5的可通達性矩陣來表達雙方的互通程度;又或者用一幅三點到五點的可通達性圖來表達。我們可以如是者把由第一層到第二層,第二層到第三層….如此類推的可通達性圖或n幅可通達性矩陣來表達。如此我們便完整地述描整個迷宮的可通達性,要解迷﹐即利用可通達性圖找出一條在入口所在的層及區間到出口所在的層及區間的路徑,而通常迷宮都是把入口定在最外層的一個區間而出口定在最外層的另一個區間,另外亦可利用n幅可通達性矩陣作運算而求指定的解,用人算來可能會很麻煩,但用電腦去解則一點難度也沒有。

廣告

~ 由 newnewhkcc1976 於 七月 10, 2009.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

 
%d 位部落客按了讚: