溫鴻航，溫鴻翔，任曉莉

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

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

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

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

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

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

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

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

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

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

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

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

2 狀態(tài)坐標(biāo)點(diǎn)及其遷移

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

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

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

左岸 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

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

圖1 坐標(biāo)遷移解路徑

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

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

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

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

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

在剔除了上述非可行點(diǎn)之后，當(dāng)然余下的就是可行點(diǎn)。具體來說，這里共有10個(gè)可行點(diǎn):

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

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

(3)過原點(diǎn)的 45°對(duì)角線上的點(diǎn)(1，1)、(2，2)，共2個(gè)點(diǎn);始點(diǎn)S0(3，3)和目標(biāo)點(diǎn)G(0，0)已包括在上兩項(xiàng)中，故不再重復(fù)計(jì)入;以上3項(xiàng)總計(jì)10個(gè)可行點(diǎn)。

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

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

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

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

(3)非可行點(diǎn)數(shù)

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

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

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

4 結(jié)束語

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

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

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

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

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