文档介绍：商人过河问题
三名商人各带一个随从乘船渡河。现此岸有一小船只能容纳两人,由他们自己划行。若在河的任一岸随从人数比商人多,他们就可能抢劫财物。不过如何乘船渡河的大权由商人们掌握。商人们怎样才能安全过河呢?
问题的提出
1
此类智力问题当然可以通过一番思考,拼凑出一个可行方案来。     但是,我们现在希望能找到求解这类问题的规律性、建立数学模型,用以解决更为广泛的问题。
分析
2
此问题可视为一个多步决策问题,每一步就是一
次渡河,每次渡河就是一次状态转移。    用三维变量(x,y,z)表示状态:    x ------商人数, y ------随从数
x,y的取值范围:{0,1,2,3}    z ------船
z的取值范围:{0,1}    那么安全状态可表示为
x=0,3, y=0,1,2,3 或
x=1,2, y=x   
这就是此问题的数学模型。
(3,3,1)
(3,2,1)
(3,1,1)
(2,2,1)
(3,0,1)
(0,3,1)
(0,2,1)
(1,1,1)
(0,1,1)
(3,2,0)
(3,1,0)
(2,2,0)
(3,0,0)
(0,3,0)
(0,2,0)
(1,1,0)
(0,1,0)
(0,0,0)
模型建立
3
这样问题要求由(3,3,1)变到(0,0,0)的一条道路。  根据题意,状态转移时要满足一定的规则:  1. Z从1变为0与从0变为1交替进行;  2. 当Z从1变为0时,即船从此岸到对岸,此岸人数减
少1或2个;     即(x,y,1)→(u,v,0)时, u≤x, v≤y, u+v=x+y-1 or
u+v=x+y-2  3. 当Z从0变为1时,即船从对岸到此岸,此岸人数增
加1或2个;     即(x,y,0)→(u,v,1)时, u≥x, v≥y,u+v=x+y+1 or
u+v=x+y+2  4. 不重复已出现过的状态,如
(3,3,1)→(3,1,0)→(3,3,1);
模型求解
4
按照以上规则,求解过程如下:
从(3,2,0)只能到达(3,3,1)/*不必考虑*/
从(3,3,1)出发
(3,2,0)
(3,1,0)如右图
(2,2,0)
(3,3,1)
(3,2,0)
(3,1,0)
(2,2,0)
从(3,1,0)出发
(3,3,1) /*不必考虑*/
(3,2,1)/*可取*/
从(2,2,0)出发
(3,3,1) /*不必考虑*/
(3,2,1)/*可取*/
5
如下图所示:
这样可得到所有答案:
6
例如:     d1:(3,3)-----(2,2) 1个商人1个随从过对岸     d1:(3,3)-----(3,1)2个随从过对岸
如图所示:
9
(1) 若船的情况不变,则2名商人2个随从
如何安全渡河?
(2) m名商人m个随从(m≥4)能否安全渡
河?
思考
10