渡河問題

本文的閱讀等級:初級

傳教士與食人族問題 (Missionaries and cannibals problem) 是一個典型的渡河問題,簡述如下:

三個傳教士和三個食人族土著一起渡河,小船一次僅能載二人。不論此岸或彼岸,如果土著人數多於傳教士人數,土人便會吃掉傳教士。當然,小船來回都必須有人操作。問路程最短的安全渡河法?又共有多少種方式?

本文介紹如何利用圖論方法建立分析模型,並以矩陣運算求得解答。閱讀前,讀者可於下列網站線上作答:http://www.plastelina.net/examples/games/game2.html

 
為方便說明,假設傳教士和食人族土著從東岸渡河前往西岸。旅程中,我們令 (m,c,e) 代表 m 個傳教士和 c 個土人及小船在河的東岸,並令 (m,c,w) 代表 m 個傳教士和 c 個土人及小船在河的西岸。根據題意,m=0,1,2,3c=0,1,2,3,因此總共有 4\times 4\times 2=32 個狀態。然而,我們要求傳教士人數必須多於土人的人數,故不存在下列狀態:

\begin{aligned}  &(1,2,e), (1,2,w), (1,3,e), (1,3,w), (2,3,e), (2,3,w)\\  &(2,1,e), (2,1,w), (2,0,e), (2,0,w), (1,0,e), (1,0,w)\end{aligned}

此外,還可以排除 (0,0,e)(0,0,w),也就是小船所在的岸邊沒有任何人。扣除上述 14 個狀態,剩下 18 個合法狀態,用頂點 (vertex) 集合 \{v_1,v_2,\ldots,v_{18}\} 表示如下:

\begin{matrix}  v_1=(3,3,e) &&v_{10}=(3,3,w)\\  v_2=(3,2,e) &&v_{11}=(3,2,w)\\  v_3=(3,1,e) &&v_{12}=(3,1,w)\\  v_4=(3,0,e) &&v_{13}=(3,0,w)\\  v_5=(2,2,e) &&v_{14}=(2,2,w)\\  v_6=(1,1,e) &&v_{15}=(1,1,w)\\  v_7=(0,3,e) &&v_{16}=(0,3,w)\\  v_8=(0,2,e) &&v_{17}=(0,2,w)\\  v_9=(0,1,e) &&v_{18}=(0,1,w)  \end{matrix}

因為所有人一起由東岸出發,可知初始頂點為 v_1。若令一傳教士和一土人駛船至西岸,即從 v_1 移動至 v_{15},我們稱 v_1v_{15} 鄰接 (adjacent),如下:

v_{1}\xrightarrow[]{\{m,c\}}v_{15}

其中 \{m,c\} 代表小船搭載一個傳教士和一個土人。明顯地,旅程可以逆轉,因此也有

v_{15}\xrightarrow[]{\{m,c\}}v_{1}

這說明兩頂點之間有對稱關係,我們用一無向邊 (edge) 連接它們。小船僅容二人搭乘又必須有人操作,所以並非任何兩頂點皆鄰接。從 v_1 出發,共有以下三種可能:

\begin{aligned}  v_1&\xrightarrow[]{\{m,c\}}v_{15}\\  v_1&\xrightarrow[]{\{c,c\}}v_{17}\\  v_1&\xrightarrow[]{\{c\}}v_{18}\end{aligned}

重複此程序,所有頂點及其鄰接可表示為下面的無向圖 (undirected graph)。我們發現 v_4v_{13} 並未與任何頂點鄰接,意思是不可能發生三個傳教士與小船在此岸且三個土人在彼岸的情況。

傳教士與食人族問題的無向圖

 
為便於後續分析計算,我們用 18\times 18 階鄰接矩陣 A=[a_{ij}] 來表示無向圖:若 v_iv_j 鄰接,則 a_{ij}=a_{ji}=1,否則 a_{ij}=0;另外,對於所有 i,設 a_{ii}=0。因為同屬一岸的狀態彼此無鄰接,可知 A 具有以下分塊形式:

A=\begin{bmatrix}  0&B\\  B&0  \end{bmatrix}

其中 B=[b_{ij}]9\times 9 階對稱分塊:

B=\begin{bmatrix}  0&0&0&0&0&1&0&1&1\\  0&0&0&0&0&1&1&1&0\\  0&0&0&0&1&0&1&0&0\\  0&0&0&0&0&0&0&0&0\\  0&0&1&0&1&0&0&0&0\\  1&1&0&0&0&0&0&0&0\\  0&1&1&0&0&0&0&0&0\\  1&1&0&0&0&0&0&0&0\\  1&0&0&0&0&0&0&0&0  \end{bmatrix}

上式中,b_{16}=1 表示 v_1v_{6+9}=v_{15} 鄰接。定義旅程 (journey) 為由 v_iv_j 的一序列頂點:

v_i=u_0\to u_1\to\cdots\to u_k=v_j

如果途經的頂點都不重複拜訪,也就是 u_p 彼此相異,則稱之為長度等於 k 的路徑 (path)。我們的目標是從 v_1 抵達 v_{10},因為 v_1 屬於東岸,而 v_{10} 屬於西岸,故路徑長度 k 必為奇數。

 
對於奇數 k,不難確認

A^k=\begin{bmatrix}  0&B^k\\  B^k&0  \end{bmatrix}

鄰接矩陣的冪矩陣 A^k(i,j) 元,以 (A^k)_{ij} 表示,等於連接頂點 v_iv_j 且長度等於 k 的旅程總數 (證明見“線性代數在圖論的應用 (一):鄰接矩陣”)。連接頂點 v_iv_j 的最短旅程稱為 v_iv_j 的距離,記作 d(i,j)。如果 d(i,j)=d,則 (A^d)_{ij}>0,且對於 k< d, 定有 (A^k)_{ij}=0。此性質提供了一個尋找最短路徑的簡易方法:連續計算 A^kk=1,3,5,\ldots,直至 A^d(1,10) 元大於零,即 (B^d)_{11}>0,這表示我們已抵達目的地 v_{10},同時還知道最短路徑長等於 d,路徑總數為 (B^d)_{11}

 
在以下計算過程中,我們一併記錄所有拜訪過的西岸頂點及路徑。提醒讀者:當 B^k(1,j) 元第一次出現非零元時 (數字加註底線),即表示我們拜訪了 v_{j+9}

k=3

B^3=\begin{bmatrix}  0&0&0&0&0&5&\underline{2}&5&3\\  0&0&0&0&1&5&4&5&2\\  0&0&1&0&3&1&3&1&0\\  0&0&0&0&0&0&0&0&0\\  0&1&3&0&3&0&1&0&0\\  5&5&1&0&0&0&0&0&0\\  2&4&3&0&1&0&0&0&0\\  5&5&1&0&0&0&0&0&0\\  3&2&0&0&0&0&0&0&0  \end{bmatrix}

首次拜訪頂點:v_{7+9}=v_{16}
最短路徑長:d(1,16)=3
路徑總數:2
路徑:

\begin{aligned}  &v_1\to v_{15}\to v_2\to v_{16}\\  &v_1\to v_{17}\to v_2\to v_{16}\end{aligned}

k=5

B^5=\begin{bmatrix}  0&0&0&0&\underline{2}&25&14&25&13\\  0&0&1&0&6&26&19&26&12\\  0&1&5&0&10&7&11&7&2\\  0&0&0&0&0&0&0&0&0\\  2&6&10&0&10&1&5&1&0\\  25&26&7&0&1&0&0&0&0\\  14&19&11&0&5&0&1&0&0\\  25&26&7&0&1&0&0&0&0\\  13&12&2&0&0&0&0&0&0  \end{bmatrix}

首次拜訪頂點:v_{5+9}=v_{14}
最短路徑長:d(1,14)=5
路徑總數:2
路徑:

\begin{aligned}  &v_1\to v_{15}\to v_2\to v_{16}\to v_3\to v_{14}\\  &v_1\to v_{17}\to v_2\to v_{16}\to v_3\to v_{14}\end{aligned}

k=7

B^7=\begin{bmatrix}  0& 0& \underline{2}& 0& 18& 127& 80& 127& 63\\  0& 1& 8& 0& 32& 135& 96& 135& 64\\  2& 8& 21& 0& 36& 41& 46& 41& 16\\  0& 0& 0& 0& 0& 0& 0& 0& 0\\  18& 32& 36& 0& 35& 9& 22& 9& 2\\  127& 135& 41& 0& 9& 0& 1& 0& 0\\  80& 96& 46& 0& 22& 1& 7& 1& 0\\  127& 135& 41& 0& 9& 0& 1& 0& 0\\  63& 64& 16& 0& 2& 0& 0& 0& 0  \end{bmatrix}

首次拜訪頂點:v_{3+9}=v_{12}
最短路徑長:d(1,12)=7
路徑總數:2
路徑:

\begin{aligned}  &v_1\to v_{15}\to v_2\to v_{16}\to v_3\to v_{14}\to v_5\to v_{12}\\  &v_1\to v_{17}\to v_2\to v_{16}\to v_3\to v_{14}\to v_5\to v_{12}  \end{aligned}

k=9

B^9=\begin{bmatrix}  0& \underline{2}& 22& 0& 118& 651& 432& 651& 317\\  2& 11& 49& 0& 168& 700& 494& 700& 334\\  22& 49& 86& 0& 139& 226& 210& 226& 98\\  0& 0& 0& 0& 0& 0& 0& 0& 0\\  118& 168& 139& 0& 128& 60& 97& 60& 20\\  651& 700& 226& 0& 60& 1& 11& 1& 0\\  432& 494& 210& 0& 97& 11& 38& 11& 2\\  651& 700& 226& 0& 60& 1& 11& 1& 0\\  317& 334& 98& 0& 20& 0& 2& 0& 0  \end{bmatrix}

首次拜訪頂點:v_{2+9}=v_{11}
最短路徑長:d(1,11)=9
路徑總數:2
路徑:

\begin{aligned}  &v_1\to v_{15}\to v_2\to v_{16}\to v_3\to v_{14}\to v_5\to v_{12}\to v_7\to v_{11}\\  &v_1\to v_{17}\to v_2\to v_{16}\to v_3\to v_{14}\to v_5\to v_{12}\to v_7\to v_{11}  \end{aligned}

k=11

B^{11}=\begin{bmatrix}  \underline{4}&28&164&0&690&3353&2284&3353&1619\\  28&86&277&0&879&3628&2556&3628&1734\\  164&277&360&0&574&1212&1011&1212&550\\  0&0&0&0&0&0&0&0&0\\  690&879&574&0&492&357&442&357&140\\  3353&3628&1212&0&357&15&84&15&2\\  2284&2556&1011&0&442&84&195&84&24\\  3353&3628&1212&0&357&15&84&15&2\\  1619&1734&550&0&140&2&24&2&0  \end{bmatrix}

首次拜訪頂點:v_{1+9}=v_{10}
最短路徑長:d(1,10)=11
路徑總數:4
路徑:

\begin{aligned}  &v_1\to v_{15}\to v_2\to v_{16}\to v_3\to v_{14}\to v_5\to v_{12}\to v_7\to v_{11}\to v_6\to v_{10}\\  &v_1\to v_{17}\to v_2\to v_{16}\to v_3\to v_{14}\to v_5\to v_{12}\to v_7\to v_{11}\to v_6\to v_{10}\\  &v_1\to v_{15}\to v_2\to v_{16}\to v_3\to v_{14}\to v_5\to v_{12}\to v_7\to v_{11}\to v_8\to v_{10}\\  &v_1\to v_{17}\to v_2\to v_{16}\to v_3\to v_{14}\to v_5\to v_{12}\to v_7\to v_{11}\to v_8\to v_{10}  \end{aligned}

 
渡河問題尚有多種變形,如最短時間旅程問題,請見下列網站例題 Family Crisis:
http://www.plastelina.net/examples/games/game3.html
詳細解法見
http://page.mi.fu-berlin.de/rote/Papers/pdf/Crossing+the+bridge+at+night.pdf

Advertisements
本篇發表於 線性代數專欄, 圖論, 應用之道 並標籤為 , , 。將永久鏈結加入書籤。

7 則回應給 渡河問題

  1. Chenlogy 說道:

    假如現在要設計一個有限階數位濾波器 在給定的條件下 是否可以利用矩陣計算找出最佳化數位濾波器?

  2. ccjou 說道:

    我知道有一個領域叫Optimal Filter,最佳化指的是這個嗎?

  3. Chenlogy 說道:

    是的,就是它,可是把戲人人會變,但是巧妙各不相同.如果從convex optimization problemx的角度來看的話?

    • ccjou 說道:

      convex optimization 包含相當大的範疇,linear programming 也是其中之一。我再找時間寫一篇簡介好了。

  4. kid50901 說道:

    為什麼要刪掉(2,1,e)傳教士2個比土人多耶?

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s