|
摘 要 为商人过河问题建立数学模型，归结为路径搜索问题，并给出一个通用的Jav程序来解决此类问题。
关键词 商人过河，二元组，链表，集合
一、描述
商人过河问题是一个传统的智力问题。其描述如下：三名商人各带一名随从乘船渡河，—只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中，商人们怎样才能安全渡河呢？
商人过河问题可以看作一个多步决策过程，通过一系列决策步骤逼近决策目标，并最终达到决策目标。对于该问题的每一步决策，就是要对船由此岸驶向彼岸或由彼岸驶回此岸的人员（包括商人和随从）作出规划，在保证商人安全的前提下，通过有限的步骤，实现人员全部过河的目标。
二、分析
针对这一具体问题，可以经过一番精心安排，找到一个解决方案。不过，本文希望对这一问题进行发展和延伸，建立起数学模型，发现其中蕴含的规律，并借助计算机的运算能力，找到一个通用的一般解法。
在商人过河问题中，用一个二元组来表示岸上商人和随从的组成(m，s)，其中m表示商人人数，s表示随从人数，每个组合可以视为一种状态。所有可能的状态可以表示为集合：
S0={(m, s)| 0≤m≤3; 0≤s≤3}
安全状态要求商人人数为0，或者大于等于随从人数，因此，所有的安全状态可以表示为集合：
S1={(m, s)| m=0, s=0,1,2,3; m=3, s=0,1,2,3; m=s=1,2}
二元组(m，s)也可以表示一次渡河方案，其中m表示船载的商人人数，s表示船载的随从人数。则所有的渡河方案可以表示为集合：
S2={(m , s)|0≤m；0≤s；0≤m+s≤2 }
一次渡河决策可以表示为：
(m, s)K+1 = (m , s)K - (-1)K (u, v)K K = 0,1,2,3…
(m , s)K为第K次渡河时，岸上的商人和随从的组成，(u, v)K为第K次渡河方案，K从0开始。
整个决策方案就是要找到有限步渡河决策，使商人和随从的人数组成从原始状态（3，3），经由一系列中间的安全状态，迁移到最终状态（0，0）的过程。
三、编程
建立前面的数学模型后，即找到一条从状态（3，3）到（0，0）的路径，可以编写程序，利用计算机的计算能力，通过穷举法找到一条状态迁移路径。
1．类二元组
类Dual实现问题分析中提到的二元组，其主要代码如下：
class Dual {
int m, s;
public Dual(int m, int s) {
this.m = m; this.s = s;
}
// 加法
Dual add(Dual e) {
return new Dual(this.m + e.m, this.s + e.s );
}
// 减法
Dual minus(Dual e) {
return new Dual(this.m - e.m, this.s - e.s );
}
…
}
|
