2.3 商人安全渡河問題

三名商人各帶一個隨從乘船從河的此岸渡向彼岸，一只小船最多能載兩人，由他們自行劃行。隨從秘密約定，在河的任一岸，一旦隨從的人數比商人多，就殺人越貨，但是如何乘船渡河的大權掌握在商人們手里。問：商人怎樣安排才能安全渡河？

解題思路

對于此類古老的趣味數學問題，經過一番邏輯思索可以找出解決辦法，且有多種解法。這里介紹一種將問題轉化為狀態轉移問題的計算機求解方法。由于這個虛擬的問題已經非常理想化，所以不必再做過多的假設。安全渡河問題可以視為一個多步決策過程。每一步，即船由此岸駛向彼岸或從彼岸駛回此岸，都要對船上的人員（商人、隨從各幾人）做出決策，在有限步內使人員全部過河。用狀態（變量）表示某一岸的人員狀況，決策（變量）表示船上的人員狀況，可以找出狀態隨決策變化的規律。因此，問題轉化為在狀態允許變化的范圍內（即安全渡河條件），確定每一步的決策，以達到渡河的目的。

在一行6人由河的此岸向彼岸渡河時，用向量（x, y）表示有x個商人、y個隨從在此岸，這里x∈{0,1,2,3}, y∈{0,1,2,3}。稱向量（x, y）為狀態向量。由問題的實際含義知，有些狀態是允許的，而有些狀態是不允許的。例如狀態（2,1）是允許的，而狀態（2,3）是不允許的。易知允許狀態集合為：S={（x, y）|（0,0）, （0,1）, （0,2）, （0,3）, （1,1）, （1,0）, （2,2）, （2,1）, （2,0）, （3,0）, （3,1）, （3,2）, （3,3）}。當渡河時，用向量（u, v）表示有u個商人，v個隨從在小船上，由小船的容量易知此時允許決策集合為：D={（u, v）|（0,1）, （0,2）, （1,1）, （2,0）, （1,0）}。

現在考察相鄰兩次渡河之間狀態s=（x, y）隨決策d=（u, v）變化的規律。為此，記狀態sk=（xk, yk），其中xk, yk分別表示第k次渡河前此岸的商人數、隨從數；決策dk=（uk, vk），其中uk, vk分別表示第k次渡河時小船上的商人數、隨從數。

若規定二維向量按普通向量加法運算進行，則有sk+1=sk+（-1）kdk。當k為奇數時，小船從河的此岸駛向彼岸；當k為偶數時，小船從河的彼岸駛回此岸。在上述規定下，問題就歸結為這樣的形式：從初始狀態s1=（3,3）出發，求一系列決策dk∈D，使得sk∈S，最后經過n步轉化為狀態sn+1=（0, 0）。注意到本問題中商人數和隨從數不多，情況比較簡單，決策的步數肯定也不多，可以用圖解法進行求解。為此，在平面坐標系上畫出方格如圖2-2所示，方格點表示狀態s=（x, y），允許狀態集S是用圓點標出的13個格子點。允許決策dk是沿方格線移動1格或者2格，當k為奇數時，向左、下移動用實線表示；當k為偶數時，向右、上移動用虛線表示。要確定一系列的dk使由s1=（3,3）經過那些圓點最終移到原點sn+1=（0,0）。圖2-2給出了一種安全渡河的移動方案，經過一系列決策d1, …, d11，最終有s12=（0,0）。即：

s1=（3,3）→s2=（3,1）→s3=（3,2）→s4=（3,0）→s5=（3,1）→s6=（1,1）→s7=（2,2）→s8=（0,2）→s9=（0,3）→s10=（0,1）→s11=（0,2）→s12=（0,0）

圖2-2 安全渡河問題的解法圖

【思考題】 當商人數、隨從數和小船容量發生變化時，安全渡河問題將會變得更加復雜。請大家嘗試建立數學模型求解商人數N1、隨從數N2和小船容量N3的安全渡河問題。