商人过河
问题分析
商人过河问题可以看做一个多布决策过程。每一步由此岸到彼岸或彼岸到此岸船上的人员在安全的前提下(两岸的随从数不比商人多), 经有限步使全体人员过河。用状态变量表示某一岸的人员状况，决策变量表示船上的人员情况，可以找出状态随决策变化的规律。问题就转换为在状态的允许变化范围内（即安全渡河条件），确定每一步的决策，达到安全渡河的目标。
模型构成
记第k 次渡河前此岸的商人数为x k, , 随从数位y k ,k=1,2,3,4……，x k ,y k =0,1,2,3,4.将二维向量s k =( xk ,y k ) 定义为状态. 安全渡河条件下的状态集合称为允许状态集合，记为S S={(x , y) | x=0, y=0,1,2,3,4; x=4, y=0,1,2,3,4; x=y=1,2,3}
此时，S 对此岸和彼岸都是安全的.
记第k 次渡船上的商人数位u k ，随从数为v k , 将二维向量d k =(uk , v k ) 定义为决策, 允许决策集合记作D 由小船的容量可知 D={(u , v) u+v=1, 2}
因为k 为奇数是船从此案驶向彼岸，k 为偶数时船从彼案驶向此岸，所以 状态sk 因决策dk 而变化的规律为：
s k+1=sk +(-1)k d k ;
这就是本题的状态转移方程。也表明了本问题的状态递归关系。这样，制定安全渡河方案可归结为如下的问题：
求dk 在D 是范围内，使得sk 在S 的范围内按照状态转移方程，有初始状态s1=（4，4）经有限步n 到达状态s n+1=（0，0）
模型求解
在xoy 坐标轴中画出如下图，图中每个坐标点表示状态s k =( x k ,y k ) ，允许是状态集合在图中表示如下
Y
X
允许决策d k 是沿方格线移动1格或2格，k 为奇数时向左. 下方移动，k 为偶数时向右. 上方 移动，要确定一系列的d k ，使初始状态（4，4）最终变为（0，0），无论怎样走都必须经过中间点（2，2）, 然后奇数次到达Y 轴, 而无论怎么变化人数都也只能到达此点后不能继续走下去，只能循环走，达不到最终的目标（0，0）.
S6=(4,1)
S5=(2,2) S6=(3,3)
由流程图看出，最后陷入循环，达不到(0,0).
电气工程学院自动化卓越——佟玲