王婷慧+金伶+宋佳欣+尹哲

摘 要：本文將文獻[1]中的商人過河的智力游戲推廣到n個商人各帶一個仆人，對船載人數(shù)進行合理更改并加以限制，建立多步?jīng)Q策模型，利用計算機對商人安全渡河的具體方案進行求解。最后對船載人數(shù)在2，3時，商人如果想要安全渡河，商人和仆人的對數(shù)應當不超過多少進行了一一分析，以避免情況遺漏。本文對上述建立的模型的優(yōu)缺點作出了相應的評價，通過檢驗可以得出，所建模型可信度大，方法合理。本文的亮點在于，分析商人與仆人對數(shù)對能否安全過河的影響，分類討論，分析深入合理，并且本文所建模型有很大的靈活性、變動性、實用性。

關(guān)鍵詞：商人過河；智力游戲；多步?jīng)Q策

1 提出問題

文獻[1]給出一個智力游戲：“三名商人各帶一個隨從渡河，一只小船只能容納二人，由他們自己劃行。隨從們密約，在河的任一岸，一旦隨從的人數(shù)比商人多，就殺人越貨。但是如何乘船的大權(quán)掌握在商人們手中。商人怎樣才能安全渡河呢？”此類智力問題當然可以通過一番思考，拼湊出一個可行的方案來。文獻[1]中通過圖解法給出了解答，但是當商人數(shù)與隨從數(shù)發(fā)生變化，船能容納的人數(shù)不是二人時，圖解法就會變得復雜而難以解決問題。

因此，將上述游戲改為n名商人各帶一個隨從過河，船每次至多運p個人，至少要有一個人劃船，由他們自己劃行。隨從們密約，在河的任一岸，一旦隨從的人數(shù)比商人多，就殺人越貨。但是如何乘船的大權(quán)掌握在商人們手中。商人怎樣才能安全渡河的問題。

除此之外，考慮了隨著船載人數(shù)的增多，以及商人與仆人的對數(shù)增多到多少時，會影響商人的安全渡河的問題。

2 問題分析

由于這個虛擬的游戲已經(jīng)理想化了，所以不必再作假設。我們希望能找出這類問題的規(guī)律性，建立數(shù)學模型，并通過計算機編程進行求解。安全渡河游戲可以看做是一個多步?jīng)Q策過程，分步優(yōu)化，船由此岸駛向彼岸或由彼岸駛回此岸的每一步，都要對船上的商人和隨從做出決策，在保證商人安全的前提下，在有限步內(nèi)使全部人員過河。用狀態(tài)表示某一岸的人員狀況，決策表示船上的人員情況，可以找出狀態(tài)隨決策變化的規(guī)律。問題轉(zhuǎn)化為在狀態(tài)的允許范圍內(nèi)，確定每一步的決策，最后獲取一個全局最優(yōu)方案的決策方案，達到渡河的目標。

除此以外，我們還要找出，隨著船載人數(shù)的增加，商人與仆人對數(shù)達到多少時，會影響到商人不能安全過河。這里要對船載人數(shù)進行限制，因為船載人數(shù)過多時，此智力游戲會變得相當復雜，就會失去作為游戲的本來意義。

3 模型構(gòu)成

記第k次渡河前此岸的商人數(shù)為 ，隨從數(shù)為 ， ， ， 。將二維向量 定義為過程的狀態(tài)。

安全渡河條件下的狀態(tài)集合稱為允許狀態(tài)集合，記作S。

當 時， ；當 時， 。

記第k次渡船上的商人數(shù)為uk，隨從數(shù)為vk，將二維向量 定義為決策。允許決策集合記為D，由小船容量知 。

因為k為奇數(shù)時，船從此岸駛向彼岸，k為偶數(shù)時，船從彼岸駛向此岸，所以狀態(tài)sk隨決策dk變化的規(guī)律是 ，此式為狀態(tài)轉(zhuǎn)移率。制訂安全渡河方案歸結(jié)為如下的多步?jīng)Q策模型：求 ，使狀態(tài) 按照狀態(tài)轉(zhuǎn)移率，由初始狀態(tài) 經(jīng)有限步r到達狀態(tài) 。

4 模型求解

用C語言編寫一段程序，利用計算機求解上述多步?jīng)Q策問題，程序代碼見附件。其算法主要是根據(jù)所輸入的商人數(shù)m，隨從數(shù)n，小船能載人數(shù)p，從s1出發(fā)去構(gòu)造下一個狀態(tài)s2，再以s2為出發(fā)點構(gòu)造下一個狀態(tài)，構(gòu)造過程中避開已構(gòu)造過的點，如此下去，直到 。若中途受阻不能達到 點，就原路退回，去尋找最近被構(gòu)造的點的其它可行的臨近點，如此以往，如果問題有解，算法會在有限步驟內(nèi)結(jié)束，并給出全部路徑，否則，算法給出不能安全渡河的結(jié)果。

當船載人數(shù)為2時，商人與仆人對數(shù)增加至4，可得如下兩種方案。

方案一：（4，4）-（3，3）-（4，3）-（4，1）-（4，2）-（2，2）-（3，3），接下來會重復第二步，導致無限循環(huán)，商人無法安全過河。

方案二：（4，4）-（4，2）-（4，3）-（4，2），接下來會重復方案一中的第五步，導致無限循環(huán)，商人無法安全過河。

在船載人數(shù)為2保持不變時，商人與仆人對數(shù)的大于3時，在渡河過程中總會出現(xiàn)循環(huán)，均無法安全渡河。

通過計算機程序求解，當船載人數(shù)為3時，商人與仆人對數(shù)的大于5時，在渡河過程中總會出現(xiàn)循環(huán)，均無法安全渡河。

5 模型的評價

該多步?jīng)Q策模型簡單，切合實際，易于理解，建立了科學合理的狀態(tài)轉(zhuǎn)移模型，結(jié)合實際情況對模型進行求解，使得模型具有很好的通用性和推廣性。多步?jīng)Q策不會出現(xiàn)遺漏可能的過河方法，使解題過程更加清晰明了。

由于該算法遍歷計算的節(jié)點很多，所以求解程序復雜繁瑣，效率比較低。

隨著船載人數(shù)的增多，要想安全過河，能容納的商人人數(shù)也增多，但是這在智力游戲中就會顯得相當繁瑣，失去了本來的意義，所以我們在這里就不予以討論了。

6 附件

用C程序進行游戲編程，源代碼如下：

#include

int a[800][2]，z；

int m，n，p；

int ifok1（int x1，int y1，int x2，int y2）

{

if（x1>=y1 && x2>=y2） return 1；

else if（x2==0） return 1；

else if（x1==0） return 1；

return 0；

}

int ifok2（int n，int x，int y）

{

if（n%2==0）

for（int i=0；i

if（x==a[i][0] && y==a[i][1]）

return 0；

if（n%2==1）

for（int i=1；i

if（x==a[i][0] && y==a[i][1]）

return 0；

return 1；

}

void fun（int x1，int y1，int x2，int y2，int time）

{

int i，j；

if（ifok1（x1，y1，x2，y2） && ifok2（time，x1，y1））

{

a[time][0]=x1；

a[time][1]=y1；

}

else return；

if（x1==0 && y1==0）

{

printf（“第%d種方法：＼n”，z+1）；

printf（“（%d，%d）＼n”，m，n）；

for（i=1；i<=time；i++）

printf（“（%d，%d）＼n”，a[i][0]，a[i][1]）；

printf（“＼n”）；

z++；

return；

}

else if（time%2==0）

{

for（i=p；i>=1；i--）

for（j=0；j<=i；j++）

{

if（x2+j<=n && y2+（i-j）<=m）

fun（x1-j，y1-（i-j），x2+j，y2+（i-j），time+1）；

}

}

else if（time%2==1）

{

for（i=1；i<=p；i++）

for（j=0；j<=i；j++）

{

if（x1+j<=n && y1+（i-j）<=m）

fun（x1+j，y1+（i-j），x2-j，y2-（i-j），time+1）；

}

}

a[time][0]=0；

a[time][1]=0；

return；

}

int main（）

{

printf（“請分別輸入商人人數(shù)（n>=1），船上可坐人數(shù)（p>=2）：”）；

scanf（“%d，%d”，&n，&p）；

m=n；

printf（“＼n”）；

fun（m，n，0，0，0）；

if（z==0）

printf（“不能安全渡河＼n”）；

}

參考文獻

[1]姜啟源，數(shù)學模型，高等教育出版社

通訊作者

尹哲，延邊大學。