基于商人过河游戏的数学建模
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=1；i--）for（j=0；j=1），船上可坐人数（p>=2）：”）；scanf（“%d，%d”，&n，&p）；
m=n；
printf（“＼n”）；
fun（m，n，0，0，0）；
if（z==0）
printf（“不能安全xx＼n”）；
}。