基于商人过河游戏的数学建模

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

摘 要：本文将文献[1]中的商人过河的智力游戏推广到n个商人各带一个仆人，对船载人数进行合理更改并加以限制，建立多步决策模型，利用计算机对商人安全渡河的具体方案进行求解。最后对船载人数在2，3时，商人如果想要安全渡河，商人和仆人的对数应当不超过多少进行了一一分析，以避免情况遗漏。本文对上述建立的模型的优缺点作出了相应的评价，通过检验可以得出，所建模型可信度大，方法合理。本文的亮点在于，分析商人与仆人对数对能否安全过河的影响，分类讨论，分析深入合理，并且本文所建模型有很大的灵活性、变动性、实用性。

关键词：商人过河；智力游戏；多步决策

1 提出问题

文献[1]给出一个智力游戏：“三名商人各带一个随从渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船的大权掌握在商人们手中。商人怎样才能安全渡河呢？”此类智力问题当然可以通过一番思考，拼凑出一个可行的方案来。文献[1]中通过图解法给出了解答，但是当商人数与随从数发生变化，船能容纳的人数不是二人时，图解法就会变得复杂而难以解决问题。

因此，将上述游戏改为n名商人各带一个随从过河，船每次至多运p个人，至少要有一个人划船，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船的大权掌握在商人们手中。商人怎样才能安全渡河的问题。

除此之外，考虑了随着船载人数的增多，以及商人与仆人的对数增多到多少时，会影响商人的安全渡河的问题。

2 问题分析

由于这个虚拟的游戏已经理想化了，所以不必再作假设。我们希望能找出这类问题的规律性，建立数学模型，并通过计算机编程进行求解。安全渡河游戏可以看做是一个多步决策过程，分步优化，船由此岸驶向彼岸或由彼岸驶回此岸的每一步，都要对船上的商人和随从做出决策，在保证商人安全的前提下，在有限步内使全部人员过河。用状态表示某一岸的人员状况，决策表示船上的人员情况，可以找出状态随决策变化的规律。问题转化为在状态的允许范围内，确定每一步的决策，最后获取一个全局最优方案的决策方案，达到渡河的目标。

除此以外，我们还要找出，随着船载人数的增加，商人与仆人对数达到多少时，会影响到商人不能安全过河。这里要对船载人数进行限制，因为船载人数过多时，此智力游戏会变得相当复杂，就会失去作为游戏的本来意义。

3 模型构成

记第k次渡河前此岸的商人数为 ，随从数为 ， ， ， 。将二维向量 定义为过程的状态。

安全渡河条件下的状态集合称为允许状态集合，记作S。

当 时， ；当 时， 。

记第k次渡船上的商人数为uk，随从数为vk，将二维向量 定义为决策。允许决策集合记为D，由小船容量知 。

因为k为奇数时，船从此岸驶向彼岸，k为偶数时，船从彼岸驶向此岸，所以状态sk随决策dk变化的规律是 ，此式为状态转移率。制订安全渡河方案归结为如下的多步决策模型：求 ，使状态 按照状态转移率，由初始状态 经有限步r到达状态 。

4 模型求解

用C语言编写一段程序，利用计算机求解上述多步决策问题，程序代码见附件。其算法主要是根据所输入的商人数m，随从数n，小船能载人数p，从s1出发去构造下一个状态s2，再以s2为出发点构造下一个状态，构造过程中避开已构造过的点，如此下去，直到 。若中途受阻不能达到 点，就原路退回，去寻找最近被构造的点的其它可行的临近点，如此以往，如果问题有解，算法会在有限步骤内结束，并给出全部路径，否则，算法给出不能安全渡河的结果。

当船载人数为2时，商人与仆人对数增加至4，可得如下两种方案。

方案一：（4，4）-（3，3）-（4，3）-（4，1）-（4，2）-（2，2）-（3，3），接下來会重复第二步，导致无限循环，商人无法安全过河。

方案二：（4，4）-（4，2）-（4，3）-（4，2），接下来会重复方案一中的第五步，导致无限循环，商人无法安全过河。

在船载人数为2保持不变时，商人与仆人对数的大于3时，在渡河过程中总会出现循环，均无法安全渡河。

通过计算机程序求解，当船载人数为3时，商人与仆人对数的大于5时，在渡河过程中总会出现循环，均无法安全渡河。

5 模型的评价

该多步决策模型简单，切合实际，易于理解，建立了科学合理的状态转移模型，结合实际情况对模型进行求解，使得模型具有很好的通用性和推广性。多步决策不会出现遗漏可能的过河方法，使解题过程更加清晰明了。

由于该算法遍历计算的节点很多，所以求解程序复杂繁琐，效率比较低。

随着船载人数的增多，要想安全过河，能容纳的商人人数也增多，但是这在智力游戏中就会显得相当繁琐，失去了本来的意义，所以我们在这里就不予以讨论了。

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（“请分别输入商人人數（n>=1），船上可坐人数（p>=2）：”）；

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

m=n；

printf（“＼n”）；

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

if（z==0）

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

}

参考文献

[1]姜启源，数学模型，高等教育出版社

通讯作者

尹哲，延边大学。