商人过河
一、问题重述和分析
随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货。

现有4名商人各带一个随从一起渡河一只船只能容纳两个人，但如何乘船渡河的大权掌握在商人的手里，商人怎样安排才能在有限步内安全渡河？
二、模型假设
1、在商人人数多于随从时乘船渡河的大权掌握在商人的手里；
2、商人和随从都会划船；
三．符号说明
x表示商人人数；
y表示随从人数；
z表示划船到河的此岸与彼岸。

四、模型的建立与求解
本题为多步决策模型，每一次过河都是状态量的转移过程。

此岸四个商人用x=0、1、2、3、4表示，此岸四个随从用y=0、1、2、3、4表示，z=0时表示划船到河的此岸时，z=1时表示划船到河的彼岸时，用有序数对（x，y，z）表示每次转移的状态量。

解决此问题就是状态量（4,4,0）转移至（0,0,1），以下就是状态量转移的全部情况（其中“！”表示不能再转移下去或与前面步骤重复）：
（4,4，0）→（3,3,1）
↓↓
（4,2,1）→（4,3,0）→（4,1,1）→（4,2,0）→（4,0,1）→（4,1,0）→！
↓
（2,2,1）
↓
！
由以上关系可知，一只船只能容纳两个人的情况下，四名商人各带一个随从无法过河。

此外，如果船的容量增加到3人，那么商人就能以几种方式安全过河，以下
是其中一种方案：
（4,4,0）→（4,2,1）→（4,3,0）→（4,1,1,）→（4,2,0）→（2,2,1）
↓
（0,1,1）←（0,3,0）←（0,2,1）←（0,4,0）←（0,3,1）←（3,3,0）↓
（0,2,0）→（0,0,1）
五、模型推广
通过以上模型的建立，若商人和随从人数增加或小船容量加大，考虑n名商人各带一随从的情况。