内容发布更新时间 : 2024/11/8 14:20:00星期一 下面是文章的全部内容请认真阅读。

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

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 模型的评价

该多步决策模型简单，切合实际，易于理解，建立了科学合理的状态转移模型，结合实际情况对模型进行求解，使得模型具