三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中，商人们怎样才能安全渡河呢?

该问题是一个多步决策的问题，商人的下一步决定方案依赖于此时的状态，同时商人可以选择的方案有多种可能，因此，要想顺利将商人送达到对岸，需要对每一步进行决策和假设，通过一步步推理，分析出最后的结果

假设商人的人数是m，随从的人数是n，船的容量是k。

记第k次渡河前彼岸（和数学模型（第四版）姜启源 谢金星 叶俊的不一样）的商人数为x，随从数为y， k = 1 , 2 , … k=1,2,\dots k=1,2,…， x = 0 , 1 , 2 , … , m x=0,1,2,\dots,m x=0,1,2,…,m， y = 0 , 1 , 2 , … , n y=0,1,2,\dots,n y=0,1,2,…,n，将二维向量 s = ( x , y ) s=(x,y) s=(x,y)定义为人员状态，安全渡河条件下的状态集合称为允许人员状态集合，记作 S S S S = { ( x , y ) ∣ x > y ∧ m − x > n − y } S=\{(x,y)|x>y \land m-x>n-y\} S={(x,y)∣x>y∧m−x>n−y} 首先需要注意到，此岸的决策恰好与彼岸决策相反，因此，针对此岸和彼岸的状态，需要不同的决策策略。不妨令船在此岸的状态抽象成0，船在彼岸的状态抽象成1。记三元组x, y, d表示彼岸的商人人数、随从人数以及此事船所在的河岸。于是，该事件的起始状态是(0, 0, 0)，即彼岸没有商人和随从，所有人都在此岸，且船在此岸；事件的结束状态是(m, n, 1)，即次岸没有商人和随从，所有人都在彼岸，且船在彼岸。

假设第k次的状态是(x, y, d)，那么他的下一次的状态只能是在 ( S , d ′ ) (S, d') (S,d′)中，所以需要遍历所有可以到达的状态点即可。

参考 商人过河问题