渡河問題的圖解分析

溫鴻航，溫鴻翔，任曉莉

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

“渡河問題”作為人們熟知的經(jīng)典趣味性智力題目之一，在各種智能訓練、測試和數(shù)學建模比賽中常會遇到［1］。而對其進行較為深入的一般性系統(tǒng)討論尚不多見。文獻［2］雖對此作了較詳細的討論，給出了應用計算機進行智能求解的方法;但該方法對數(shù)學要求較高，不利于教學普及。見于此，文中在文獻［1］的啟發(fā)下，應用簡單直觀的圖解法對渡河問題作初步探討，以期為編擬該類智能題目提供參考依據(jù)以及求解的思路。

1 渡河問題兩種常見的描述

為利于今后討論的一致性，先將渡河問題簡述如下(括號內(nèi)的“或m”、”或n”用于作一般性討論時來替代前面的具體數(shù)字):

問題1 傳教士與食人族渡河問題。

在河流的左岸現(xiàn)有3位(或m位)傳教士和3個(或m個)食人族，他們欲利用左岸邊最多可乘坐2人(或n人)的小舟渡到河右岸去。假設(shè)每個人都會劃船;其限制是:無論是在左岸、船上還是右岸的場合下，都不得出現(xiàn)食人族人數(shù)多于傳教士數(shù)目的不安全情況，因這樣可能發(fā)生食人族攻擊傳教士的危險。

問題2 阿拉伯夫婦渡河問題。

即有3對阿拉伯夫婦欲利用能載客2人的小船從河左岸過渡到右岸去，已知每個人都會劃船。其限制是:按照習俗任一位妻子都不得在其丈夫不在場陪伴的場合下與別的男子碰面。

上述表述中各有兩個限制(約束條件):

(1)小船的載運能力n(運能約束)，即在往返擺渡過程中船上乘員最多不超過n;(2)兩岸三處人員組成的限制(組合約束)。下面就約束條件進行討論。

前述對渡河問題的兩種表述，其約束條件(1)相同;而從字面看似乎兩種表述的約束條件(2)不同;但實際上，問題2的限制與問題1并無較大差異，對于2中的人員組合的限制，可以理解為:在各種場合下都不能出現(xiàn)女子人數(shù)多于男子數(shù)的情況。假如在某一側(cè)岸邊出現(xiàn)了女多于男的情形，則必然有一位女性的丈夫是不在現(xiàn)場、而現(xiàn)場又是有別的男性在場的，這當然是不合禮俗規(guī)定的。對渡河問題的以上兩種表述其唯一差異點在于:問題1中的2 m個兩類元素傳教士與食人族之間不存在任何對應關(guān)系，若設(shè)過渡過程中某個時刻在兩岸中任一場合的人員組合狀態(tài)是由x個傳教士與y個食人族組成的，那么只要在人數(shù)上符合人員組合約束條件(2)，即

則不論是哪位(或哪幾位)傳教士與哪(幾)位食人族在一起都是合法的，即其組合對于兩種元素成分沒有選擇匹配的要求，在同一類成員中的各個元素是沒有區(qū)別而平等存在的;這樣在構(gòu)成某種狀態(tài)組合時只需注意滿足組成人員數(shù)目上的限制即可，而無需對同類元素的個體進行選擇，故約束條件是較為寬松的。而問題2的約束(2)顯然要更為嚴苛一些，因為男子集合中每一個個體與女性集合中的某個指定個體有著對偶匹配關(guān)系，故在渡河過程的每個狀態(tài)下除了需滿足前述對于任一組合中兩類人員人數(shù)的約束(2)之外，還須在兩岸三處的人員組合中進行指定性的選擇安排，即考慮兩類成員男女之間的配偶對應關(guān)系。不過這種禮俗上的約束符合人之常情，在具體實施中稍加注意即可滿足;為簡單起見，文中略去了問題2中兩類元素集合中個體的差異性，將問題2合并于問題1一起進行討論。此后的論述中若無特別說明時將只就問題1展開，并認為其中亦包括了對問題2的討論與求解。

2 狀態(tài)坐標點及其遷移

仿照整數(shù)(二元)規(guī)劃的圖示方法，因構(gòu)成渡河問題的元素只有兩種——傳教士與食人族，即在問題求解過程中某一時刻河岸上的人員組合狀態(tài)Sk，包含初始狀態(tài)S0與最終狀態(tài)SK=G，都可以用二維坐標點Sk(x，y)來表示;這里x和y分別為河岸某一側(cè)傳教士和食人族的人數(shù)。顯然x、y均為整數(shù)且有0≤x，y≤m;具體在m=3，n=2的問題中應是0≤x，y≤3。下標k=0，1，2，…，K，表示經(jīng)過K次擺渡后問題獲得解決，亦即實現(xiàn)了“始點S0→目標G(=SK)”的狀態(tài)遷移。擺渡次序k的計算是按照每個單趟運載算作一次，即小船往返一個來回按兩次計。對于同一題目，在有多種解法時，當然總步數(shù)K應為所有可行路徑中的最短路徑，且K必為奇數(shù)。

2.1 滯留左岸的人員組合狀態(tài)

滯留左岸的人員組合狀態(tài)，如圖1(a)所示，設(shè)置直角坐標系O—xy;在m=3時共有(m+1)2=42=16個交點:(0，0)，(0，1)，(0，2)，(0，3)，(1，0)，(1，1)，…，(3，3)，亦即16個可能狀態(tài)點。若著眼于用左岸(即出發(fā)一側(cè))滯留人員的組合來表征問題求解過程中人員變動的態(tài)勢時，那么渡河問題的解決就是使得滯留于左岸的人員組合——(傳教士人數(shù)x，食人族人數(shù)y)=Sk(x，y)，由始點 S0=(3，3)出發(fā)，在約束條件下經(jīng)K次擺渡后遷移至目標點SK=(0，0)=G(與坐標原點O重合)。其求解過程如圖1(a)所示。顯然，凡是使得Sk(x，y)的坐標值下降的坐標點遷移，即表示由左岸的初始狀態(tài) S0(3，3)向著最終的目標點G(xK，yK)=O(0，0)前進，亦即代表從左岸向右岸渡去的行程;文中把這種使問題趨于解決的行程(左岸→右岸)稱之為“正行程”，包括使x減小、或使y減小、或者x和y同時減小的坐標遷移。而在每次正行程之后(除最后一次正行程已經(jīng)達到目標狀態(tài))，緊接著必然有一次使小船返回左岸的“回程”(使x增大、或使y增大、或者使x和y同時增大的坐標遷移，圖中用虛線箭頭表示)，以便繼續(xù)實施下一次“左岸→右岸”的正行程擺渡，直到K=11時完成全部擺渡任務。圖1(a)的解路徑可簡單表示為(實線箭頭表示正行程，虛線表示回程)

左岸 S0=(3，3)→(3，1)﹍(3，2)→(3，0)﹍(3，1)→(1，1)﹍(2，2)→(0，2)﹍(0，3)→(0，1)﹍(0，2)→(0，0)=G

若從提高完成任務的運載效率考慮，由常識可以定性地認為:在每一次正行程中應盡量增大乘船人數(shù)，充分利用運載能力n，以圖用盡量少的擺渡次數(shù)K達成目標;而在回程則應盡量減少船上的乘員數(shù)目，以減小無謂的消耗。特別是在運載成本極其重要的情況下，或是在一題多解(即對于相同的m和n，有一個以上總擺渡次數(shù)同為K而路徑不同的解決方案，如圖3所示，時需要對不同的解路徑作出評價比較的場合下，當然就需要對運載效率或者解路徑的經(jīng)濟性作定量的分析計算。

圖1 坐標遷移解路徑

2.2 右岸的人員組合狀態(tài)

圖1(a)是以滯留于左岸的人員組合狀態(tài)Sk(x，y)為對象來進行求解的;當然也可以以到達右岸的人員組合狀態(tài)為對象進行求解。為與左岸相區(qū)別，這時將坐標系設(shè)為O'—x'y'，右岸的初始狀態(tài)為S'0(0，0)，目標狀態(tài)為S'K'(x'，y')=G'(3，3)。由于此時的始點S'0與坐標原點O'重合，而目標點G'則在距離原點最遠處;故與前述左岸的情形恰好相反，這時的“正行程”應為坐標值增大的方向，“回程”則在向坐標原點收縮靠攏的方向上。為方便后面對坐標點的分類分析中與圖1(a)相對照，這里將O'—x'y'坐標系作了逆時針180°旋轉(zhuǎn)，這并不影響問題的求解過程。由圖1(b)可知，經(jīng)過K'=11次的坐標遷移后，右岸將達到目標狀態(tài)G'(3，3);這一結(jié)果與前述關(guān)注左岸滯留人員組合狀態(tài)(圖1(a))時的結(jié)果K=11相一致，這是預料之中的，因為二者僅僅是對河岸上人員狀態(tài)的著眼點由左岸變換為右岸而已，并未對其路徑或過程作任何變化。同樣可將關(guān)注右岸人員組合時的解路徑(圖1(b))簡記為

右岸 S0'=(0，0)→(0，2)﹍(0，1)→(0，3)﹍(0，2)→(2，2)﹍(1，1)→(3，1)﹍(3，0)→(3，2)﹍(3，1)→(3，3)=G

3 狀態(tài)坐標點的分類

在圖1(a)中，當從始點S0(3，3)出發(fā)，在探尋逐步趨向目標點G(0，0)的最短路徑的過程中，必須對每一個正行程的落腳點和隨后的回程落腳點其坐標是否滿足組合約束條件(2)進行判斷。為此，這里試圖在搜索求解之前就對所有的(m+1)2個可能狀態(tài)點進行分析歸類，標出那些不符合約束條件的狀態(tài)點——稱作“非可行點”，從而使得搜索求解中能夠避免誤入這些違反約束的“禁區(qū)”。

由圖1(a)可知，點(1，2)、(1，3)、(2，3)顯然是非可行點(用⊙表示)，因為這些點所表示的左岸滯留人員組合都是x(傳教士人數(shù))＜y(食人族人數(shù))的狀態(tài)，是不符合約束條件(2)的。

為便于解釋另外3個非可行點(圖1(a)中用*標示)——(2，1)、(2，0)、(1，0)，需要與圖 1(b)相對照;因為這3個點表面上似乎是滿足組合約束條件(2)的，即符合0＜x≤3且x≥y;但是實際上它們是非可行點。因為組合約束條件(2)是要求在兩岸三處都得到滿足。而此3個狀態(tài)點雖然在左岸滿足了組合約束，但在對應的右岸卻是不滿足組合約束的。這一點只要對照圖1(a)和圖1(b)即可知道。圖1(b)所示的右岸狀態(tài)遷移過程中，在點 S'(x'，y')=(1，2)、(1，3)、(2，3)處顯然不滿足x'≥y'，即為非可行點(同樣用⊙表示)。假想圖1(b)是繪制在透明膠片上的，就可以將其移動到與圖1(a)相重疊的位置，使得兩個圖上左右兩岸的始點 S0(3，3)→S0'(0，0)、目標點 G(0，0)→G'(3，3)分別對準，成為相互影射關(guān)系;則易于發(fā)現(xiàn)圖1(a)與圖1(b)上的求解路徑確是相互重合的。這意味著不論關(guān)注的是左岸還是右岸現(xiàn)有人員的組合態(tài)勢，這時其求解路徑是相同的(這是就此實例所作的推斷，而在一題多解的場合則不能這么簡單地推斷。為說明這一點，對于m=3、n=2給出了不同于圖1(a)，圖1(b)的另一條解路徑如圖3所示，其求解步數(shù)則與圖1相同，仍為K=11)。那么與右岸的3個非可行點(x'，y')=(1，2)、(1，3)、(2，3)相對應的左圖 1(a)中的影射點(x，y)=(2，1)、(2，0)(1，0)也應是非可行點。同樣地可以判定，與圖1(a)中3個非可行點(x，y)=(1，2)、(1，3)、(2，3)相對應的圖 1(b)中 3 個影射點(x'，y')=(2，1)、(2，0)、(1，0)也是非可行點。據(jù)此可知，無論是著眼于左岸狀態(tài)還是右岸狀態(tài)，都有著6個非可行點;現(xiàn)將這6個非可行點合并表示于圖2中。為給后續(xù)求解過程中的圖搜索提供導引信息，文中將對角線以上的非可行點所構(gòu)成的三角形區(qū)域稱作“上禁區(qū)”(圖中網(wǎng)格部分，下同)，對角線以下的非可行點三角形區(qū)域稱作“下禁區(qū)”，即在坐標遷移(或圖搜索)過程中應避免在該區(qū)域停留，但可以飛越。

在剔除了上述非可行點之后，當然余下的就是可行點。具體來說，這里共有10個可行點:

(1)直線 x=m=3 上的(3，0)、(3，1)(3，2)及S0(3，3)，共4 個點;

(2)直線 x=0(即 y軸)上的 G(0，0)、(0，1)、(0，2)、(0，3)，共4 個點;

(3)過原點的 45°對角線上的點(1，1)、(2，2)，共2個點;始點S0(3，3)和目標點G(0，0)已包括在上兩項中，故不再重復計入;以上3項總計10個可行點。

若進一步細分，還可以在這些可行點的集合中把對角線上的點特別地稱作“平衡點”，因為在這些點上始終滿足x=y(或者x'=y')，亦即兩類構(gòu)成元素——傳教士與食人族是勢均力敵的，這種場合下便不會發(fā)生在此岸可行而在彼岸不可行的矛盾。平衡點的引入對于應用計算機圖搜索技術(shù)將是有益的。

以上是就m=3、n=2的具體事例的分析。推廣到一般情況下(即:有m個傳教士與m個食人族利用最多能載n個人的小船欲從河流左岸過渡到右岸去)，這時可以在求解問題之前由如下各式對圖搜索的范圍做到心中有數(shù)。

(1)可能狀態(tài)點數(shù)

(2)可行點數(shù):直線x=0和x=m上各有(m+1)個，對角線上有［(m+1)－2］個，故可行點總數(shù)為

(3)非可行點數(shù)

依據(jù)上述各式，表1中列舉出一些簡單m時的各類對應點數(shù)，以及使問題得以成立而所需nmin、對應的K值，以供參考。

表1 可行點數(shù)、不可行點數(shù)以及最小運能nmin

以上各式中均未出現(xiàn)小船運載能力參數(shù)n，即表明可行點數(shù)(或非可行點數(shù))僅僅取決于欲渡人員數(shù)m(雙)而與n無關(guān)。但n的大小顯然會影響到完成任務的擺渡總次數(shù)K，亦即問題求解的難易程度;對于相同的m值，若n越大則所需的擺渡次數(shù)K越小(例如對于m=3而言，當n=2時K=11，當n=3時K=5)，問題求解就愈簡單;反之亦然。本文認為，一般在編擬此類智力題目時應有限制nmax=m，因為這種情況下總有K=5的最短求解路徑存在，問題求解已經(jīng)變得很簡單了，進一步的簡單化(即繼續(xù)增大運能n)也就失去了智力訓練和測試的意義了。至于運載能力的下限nmin的存在是顯而易見的，至少也應有n≥2，才有可能使得往返擺渡(即正行程+回程+正行程+…)能夠連續(xù)進展下去，否則將無解(若運載能力n=1，則正行程與隨后的回程在小船上最多和最少都只有一人，一個往返航程的實際擺渡效果為0人，即不可能完成渡河任務);但由于nmin是與m值有關(guān)的，要比nmax復雜些，故此處僅作提示而留待后續(xù)再作進一步討論。

4 結(jié)束語

作為趣味智力訓練和測試的經(jīng)典題目，在以往的求解中多是用腦體操的邏輯推理方式來解決的，系統(tǒng)深入的探討較少。這在所處理的數(shù)值較小、問題較簡單時是能解決問題的。但考慮到此類問題在規(guī)劃、管理等領(lǐng)域可能存在的潛在應用及在較大數(shù)值條件下求解的復雜性，文中嘗試用圖解法來表示問題求解路徑中狀態(tài)點的變遷，并對狀態(tài)坐標點作了分類分析，對此類題目的編擬給出了一些初步建議;以期為探尋此類問題的簡便求解思路創(chuàng)造條件。

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

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

［3］ 鄧興無.滑動摩擦平衡問題的圖解分析法［J］.電子科技大學學報，1997(S1):281－284.

［4］ 田社平，陳洪亮.含運算放大器電路的圖解分析［J］.電氣電子教學學報，2012(2):92－94，106.