基于商人過河游戲的數(shù)學(xué)建模

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

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

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

1 提出問題

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

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

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

2 問題分析

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

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

3 模型構(gòu)成

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

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

當(dāng) 時(shí)， ；當(dāng) 時(shí)， 。

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

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

4 模型求解

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

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

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

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

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

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

5 模型的評(píng)價(jià)

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

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

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

6 附件

用C程序進(jìn)行游戲編程，源代碼如下：

#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（“請(qǐng)分別輸入商人人數(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”）；

}

參考文獻(xiàn)

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

通訊作者

尹哲，延邊大學(xué)。