渡河問題

本文的閱讀等級：初級

傳教士與食人族問題 (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,3$ 且 $c=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_1$ 和 $v_{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_4$ 和 $v_{13}$ 並未與任何頂點鄰接，意思是不可能發生三個傳教士與小船在此岸且三個土人在彼岸的情況。

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

為便於後續分析計算，我們用 $18\times 18$ 階鄰接矩陣 $A=[a_{ij}]$ 來表示無向圖：若 $v_i$ 和 $v_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_1$ 和 $v_{6+9}=v_{15}$ 鄰接。定義旅程 (journey) 為由 $v_i$ 至 $v_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_i$ 和 $v_j$ 且長度等於 $k$ 的旅程總數 (證明見“線性代數在圖論的應用 (一)：鄰接矩陣”)。連接頂點 $v_i$ 和 $v_j$ 的最短旅程稱為 $v_i$ 與 $v_j$ 的距離，記作 $d(i,j)$ 。如果 $d(i,j)=d$ ，則 $(A^d)_{ij}>0$ ，且對於 $k< d$ , 定有 $(A^k)_{ij}=0$ 。此性質提供了一個尋找最短路徑的簡易方法：連續計算 $A^k$ ， $k=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

8 Responses to 渡河問題

Chenlogy says:

08/13/2012 at 7:10 am

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

ccjou says:

08/13/2012 at 8:29 am

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

Chenlogy says:

08/13/2012 at 9:57 am

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

- ccjou says:
  
  08/13/2012 at 12:41 pm
  
  convex optimization 包含相當大的範疇，linear programming 也是其中之一。我再找時間寫一篇簡介好了。
  
kid50901 says:

08/19/2016 at 9:03 pm

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

- ccjou says:
  
  08/20/2016 at 7:15 am
  
  這是東岸的情況，西岸呢？
  
  - kid50901 says:
    
    08/20/2016 at 11:10 pm
    
    了解感謝
    
张博 says:

02/18/2019 at 6:10 pm

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

从这个矩阵中，应该可以找出4中解了，横向搜索是从east 到 west，纵向搜索是west 到 east，搜索1就行了。

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨

8 Responses to 渡河問題

Leave a Reply Cancel reply

搜尋(繁體中文或英文)

訊息看板

近期文章

線性代數專欄

其他主題專欄

每週問題

數據充分性問題

其他分類

Recent Comments

近期最多人點閱

分類

Archives

標籤雲

線代線上影音課程

線代學習網站

線代電子書

矩陣計算器

LaTeX

Blogroll

訂閱

閱讀導引

學習資源

專題探究

急救查詢

其他分頁

Meta

網路狀態

Blog Stats

渡河問題

Share this:

Like this:

8 Responses to 渡河問題

Leave a Reply Cancel reply

搜尋(繁體中文或英文)

訊息看板

近期文章

線性代數專欄

其他主題專欄

每週問題

數據充分性問題

其他分類

Recent Comments

近期最多人點閱

分類

Archives

標籤雲

線代線上影音課程

線代學習網站

線代電子書

矩陣計算器

LaTeX

Blogroll

訂閱