商人过河问题（一）

问题描述：

如果有n名商人，有n名随从，如何建模？设计求解算法？是否n为任意值均有解？

问题解答：

假设第k次渡河前， x_k表示此岸的商人数， y_k为随从数。

S表示安全渡河条件下的状态集合：

S={(X,Y)|X=0，Y=0,1,2,3...N:X=N，Y=0,1,2,3...N;X=Y=1,2,3...N-1}       （1）

允许决策集合记为D

                                          D={(U,V)|1≤U+V≤2，U,V=0,1,2}               （2）

表示渡河状态

       S_k+1 =S_k+(-1)^kd_k（3）

求解上述（1）、（2）、（3），使得状态 从初始状态(n,n)到达状态(0,0)。

使用图解法进行求解：

当n=2时，状态转移如下图所示，即(2,2)→(1,1) Or (2,0)→(2,1)→(0,1) → (1,1)→(0,0) 

当 时无法安全渡河，如n=4时如下图，d7无法作不重复的转移。