溫鴻航，任曉莉，溫鴻翔

(1.西安電子科技大學通信工程學院，陜西 西安 710071;2.西安交通大學城市學院，陜西 西安 710018;3.陜西廣電網(wǎng)絡(luò)(集團)有限公司，陜西 西安 710075)

渡河問題的一般性描述是:有m個傳教士與m個食人族欲利用最多載客n人的小船從河左岸過渡到右岸去，設(shè)每個人都會劃船，要求其過程中在河兩岸及船上均不得出現(xiàn)食人族人數(shù)多于傳教士數(shù)目的情況，以免發(fā)生傳教士受到攻擊的危險。這類題目在數(shù)值較小時因其解路徑較短，常常經(jīng)邏輯推理及簡單計算即可解得［1］。但考慮到將來可能應(yīng)用于規(guī)劃、管理等領(lǐng)域時，處理的數(shù)值較大，解路徑變長，求解過程將趨于復雜化，且其中亦常含有智能搜索，需要借助于計算機來處理［2］。為此就有必要構(gòu)建適當?shù)臄?shù)學表達方式及算法?；诖?，提出了用岸態(tài)矩陣來表示求解過程中河岸上的人員組合狀態(tài)，并引入表征船上人員的擺渡算子，采用迭代法來探尋由初始岸態(tài)逐步導向目標岸態(tài)的解路徑。從而為應(yīng)用計算機處理此類問題提供一種思路。

1 岸態(tài)矩陣及其構(gòu)成

提出的岸態(tài)矩陣，是用于表征問題求解過程中任一時刻處于河流兩岸的人員組合狀態(tài)的。設(shè):某一時刻滯留于河左岸的傳教士和食人族的人數(shù)分別為x和y，同一時刻位于河右岸的傳教士和食人族人數(shù)分別為x′和 y′;顯然這里的 x、y 和 x′、y′都應(yīng)為大等于零的整數(shù)。于是可以構(gòu)造如下的岸態(tài)矩陣Sk

式(1)中第一行為河流左岸的人員組合狀態(tài)向量(x，y)，第二行為同一時刻河右岸的人員組合狀態(tài)向量(x′，y′);而矩陣的第一列為傳教士在河流左右兩岸的分布情況，第二列是此時食人族在左右兩岸的分布。K為從初始狀態(tài)S0達到目標狀態(tài)G=SK所需的總迭代次數(shù)，亦即小船的擺渡次數(shù)，且K必為奇數(shù)。為滿足人員組合的約束條件，即任一時刻在任何場所都不得出現(xiàn)食人族多于傳教士人數(shù)的危險情況，則對于第一行有

同樣地，對于第二行的右岸人員組合也應(yīng)符合這一約束

岸態(tài)矩陣的列向量則應(yīng)滿足

那么，開始擺渡之前的初始岸態(tài)矩陣就是

完成擺渡任務(wù)時的目標岸態(tài)矩陣應(yīng)為

在此前的討論中曾經(jīng)用二維坐標系中的點來表示河流左岸或者右岸的人員組合狀態(tài)［2］，即只能反映某一時刻單側(cè)河岸的狀態(tài)，這樣在采用圖解法求解時由于已經(jīng)預先劃出了非可行點的“禁區(qū)”，一般不會發(fā)生在此岸滿足約束而在彼岸不滿足約束的錯誤。但是在采用迭代計算法求解時，就要考慮在構(gòu)成狀態(tài)矩陣時絕對避免這類顧此失彼的錯誤。為此，文中將任一時刻左右兩岸的人員組合狀態(tài)合并于一個岸態(tài)矩陣之中;這樣只要在每經(jīng)過一次迭代(亦即一次擺渡)來構(gòu)成新的岸態(tài)矩陣時，通過組合約束式(2)、式(3)的檢驗即可。通過此項檢驗的即為合法操作，就可轉(zhuǎn)入下一輪迭代;否則即為非法操作，需要回到本次迭代的出發(fā)點，并尋求新的擺渡算子，直到獲得合法的迭代結(jié)果，即新的岸態(tài)矩陣，才算完成了此次迭代，再繼續(xù)轉(zhuǎn)入下一次迭代，……，經(jīng)過K次后獲得整個解路徑。

2 迭代式與擺渡算子

設(shè)第k次迭代的公式為

這里定義擺渡算子為

式(8)中，第一行的u和v分別為某次擺渡中小船上的傳教士和食人族的人數(shù);于是關(guān)于小船運載能力n的約束條件即可表示為

算子的第二行之所以設(shè)置為(－u －v)，正是為了保證在每次擺渡中，該次迭代所導致的在此岸增加的人數(shù)，始終與彼岸減少的人數(shù)是對應(yīng)相等的，也就使得迭代計算具有自檢錯功能，以保證求解過程的正確進展，這在算法上是易于實現(xiàn)的。

由常識可知，在總共K次的擺渡中，凡次序k為奇數(shù)的迭代都對應(yīng)著從左岸向右岸執(zhí)行人員輸送任務(wù)的正行程，即算子前面的符號(－1)k=－1;而次序k為偶數(shù)的算子的符號對應(yīng)于由右岸返回左岸的回程，即(－1)k=1。迭代式的運算規(guī)則與普通的矩陣加減運算法則是相同的，其差異僅僅是:為簡化書寫格式而將K次迭代運算連式寫出，于是把迭代式(7)中的等號“=”改用箭頭“→”，用于僅表示此次運算的結(jié)果。亦即將前后相鄰的兩次迭代計算Sk－1+( －1)kΔSk→Sk和 Sk+( －1)k+1ΔSk+1→Sk+1連寫成 Sk－1+( －1)kΔSk→Sk+( －1)k+1ΔSk+1→Sk+1的形式，以此類推。于是，全部迭代過程就可表示為

3 運載能力n的取值范圍

在前篇《渡河問題的圖解分析》中，曾就運載能力n的影響及取值作了初步說明;本文給出的矩陣表示和算法，為對n作較深入的討論提供了方便。

3.1 n值上限(nmax)

首先，在m(實際渡河任務(wù)為2m)不變的條件下，顯然運載能力n越大，則任務(wù)就越是簡單，完成擺渡所需的總次數(shù)K就越小。故n不能過大，亦即K不能太小，例如K=3就意味著小船在一個往返航行后即已趨于完成擺渡任務(wù)，否則就失去了智力訓練或測試的意義，故在編擬此類題目時n應(yīng)有一個上限。易于推證:當n=m時，不論m為何值，總能夠在K=5步內(nèi)完成擺渡任務(wù)，求解路徑如式(12);為此文中建議取n的上限為nmax=m。

圖1～圖4分別給出了 m=n=3、m=n=4、m=n=5及m=n=6時的解路徑。圖中，實線箭頭表示從左岸駛向右岸的正行程，虛線箭頭表示由右岸返回左岸的回程;S0為擺渡開始前的初始河岸狀態(tài)，G為完成擺渡任務(wù)的最終目標岸態(tài);對角線上下的三角形網(wǎng)格部分是非可行點區(qū)域，是為狀態(tài)坐標遷移時不得停留的“禁區(qū)”即違反題目約束條件的情況。

圖4 m=n=6，K=5的一個解路徑

具體地，可將圖1(a)的解路徑記為

而圖1(b)則為相同情況下的另一解路徑

圖2(a)與圖2(b)也是一題多解的例子，即在相同情況下的不同的解路徑，圖2(a)可用數(shù)式表示為

圖2(b)可表示為

3.2 n值的下限

其次，再來討論n值的下限nmin。由常識可知:(1)小船運載能力n越小，在同樣的擺渡任務(wù)m的場合，所需的擺渡次數(shù)K就越多，問題求解就愈加復雜，反之亦然;(2)小船的運載能力至少應(yīng)有 n≥2，才可能使得小船在首次從左岸擺渡到右岸后返回到左岸來，以使擺渡能夠有效地繼續(xù)進行下去;當n＜2時每個往返航程的實際渡河人數(shù)為零，即渡河任務(wù)永遠不可能完成，則題目無解;在編擬題目時應(yīng)對此加以注意。

應(yīng)用圖解法進行試探，可以得到如表1的若干使問題有解的nmin值。

表1 運載能力nmin

對表1作如下解釋，如圖5～圖13所示:

(1)對于m=2，如圖5所示和m=3，如圖6所示，有nmin=2，這是符合n≥2的常識的。

(2)對于m=4，假定也取n=2、并應(yīng)用圖解法求解，如圖7所示。當在第6步到達了點(3，3)以后，則不論怎樣選擇路徑，都會落到禁區(qū)內(nèi)的點上;故初步確定對應(yīng)于m=4的最小n值為3;再由圖8所示m=4、n=3的一個解路徑，即可確定:m=4時=3。

圖7 m=4、n=2，無解

圖8 m=4、n=3，K=9

(3)對于m=5，先初步推斷nmin≥3，進而用圖解法，如圖9所示的解路徑確認了nmin=3。

圖9 m=5、n=3，K=11

類似于圖7所示，在圖10中表示了m=6、n=3時題目無解的情況，因其在第6步(k=6)之后，無論怎樣選擇求解路線，都不能跨越禁區(qū);故與m=6對應(yīng)的最小n可暫取為4;再用圖解法，如圖11所示可對m=6、nmin=4的推斷予以確認。

(4)由表1可知，當m≥6時總有nmin=4，對此說明如下，如圖12，m=7、nmin=4:當應(yīng)用圖解法由距離原點最遠的始點S0(m，m)出發(fā)，假定始終沿著45°對角線方向向坐標原點O(0，0)——亦即目標狀態(tài)點G逼近，則每個正行程最多可渡過n=4人，而隨后的回程則向左岸返回2人，這就意味著每一個往返行程實際向右岸輸送了2人。若所需總的擺渡次數(shù)為K，則除去最后一次擺渡的單行程之外，此前共有(K－1)/2個往返行程，共可渡過2×(K－1)/2=(K－1)人;這時若左岸的滯留人數(shù)為:2m－(K－1)=4，亦即狀態(tài)坐標點為對角線上的點(2，2)，則可在最后的第K次完成任務(wù)。易于推知:與第K次緊鄰的第K－1次擺渡的回程只可能停留在狀態(tài)坐標點(2，2)上，若是返回在坐標點(1，1)上，則說明此前的第K－2次是落在了原點(0，0)上，那么就已經(jīng)完成了全部擺渡任務(wù)而無需返回了，這與總擺渡次數(shù)為K的假設(shè)相矛盾。

圖12 m=7、n=4，K=11

由此知，在m≥6、n=4的場合下所需的總擺渡次數(shù)K可由2m－(K－1)=4得到

在用圖解法來尋求由始點S0→目標G的解路徑時，特規(guī)定了搜索始終是沿著對角線方向作往返擺渡，這僅是為方便證明:當m≥6時若取nmin=4，則有K=2m－3，亦即總有一個有限的、非零正整數(shù)解K是存在的。但是這并不意味著在m≥6、n=4的場合，所有的解路徑必須是沿著對角線方向而往返的，圖13即為m=6、n=4且K=9，即已知條件m、n及解路徑步數(shù)K與圖11完全相同、而解路徑的方向卻并不沿著對角線方向的另一個解。如果從追求最高的運載效率的角度，來比較圖11與圖13的求解方案之優(yōu)劣，顯然圖13的方案要優(yōu)于圖11的方案。原因是:在圖13的回程中只有一次(k=4)是用2人把小船送回左岸的，即其中只包含了1人次的冗余;而圖11的求解方案則在共4次的回程中各有一人次的冗余，總的冗余為4人次，當然所包含的無效消耗必定大于圖13的求解方案。這種一題多解方案的比較，對于那些運載效率重要、而運載成本較高的工程問題是有著實際意義。

圖13 m=6、n=4，K=9

4 結(jié)束語

渡河問題在規(guī)模較小的情況下，求解較為簡單，一般無需編程計算。但若將其應(yīng)用于規(guī)劃、管理等工程領(lǐng)域，則隨著題目規(guī)模的增大其求解的難度便會增大;加之對于重大工程問題常需對多個方案進行比較選優(yōu)，則計算更為復雜，還可能涉及智能運算;故應(yīng)用計算機進行處理是必然選擇。這就需要構(gòu)建適合于這一潛在需求的數(shù)學表達形式及其算法。文中正是基于此，嘗試用岸態(tài)矩陣來表征渡河問題求解過程中同一時刻河流兩岸上人員的組合狀態(tài)，并以小船上的人員組合作為擺渡算子，通過K次迭代來尋求解路徑;這樣即可應(yīng)用Matlab求解數(shù)值較大的復雜的渡河問題。此外，還就小船運載能力n的取值范圍作了較深入的討論，并用圖解法給出了多個算例來加以驗證，以供編擬和審核此類智能問題時參考。對于擺渡算子ΔSk的選取，因涉及智能化圖搜索技術(shù);尚有待后續(xù)的研究進展。

［1］周義倉，赫孝良.數(shù)學建模實驗［M］.西安:西安交通大學出版社，1999.

［2］武藤佳恭，ニュ－ラル コンビュ－ティンゲ［M］.東京:コロナ社，1996.

［3］李天瑞.安全渡河問題的計算機求解和模擬［J］.工科數(shù)學，1999，15(1):119 －122.

［4］敖志剛.人工智能及專家系統(tǒng)［M］.北京:機械工業(yè)出版社，2010.

［5］陳汝棟，于延榮.數(shù)學模型與數(shù)學建模［M］.北京:國防工業(yè)出版社，2009.

［6］堵秀鳳，張劍，張宏民.數(shù)學建模［M］.北京:北京航空航天大學出版社，2011.

［7］王兵團.數(shù)學建模簡明教程［M］.北京:清華大學出版社，2012.