问题描述：
如果有n名商人，有n名随从，如何建模？设计求解算法？是否n为任意值均有解？
问题解答：
假设第k次渡河前， xk表示此岸的商人数， yk为随从数。
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）
表示渡河状态
Sk+1 =Sk+(-1)kdk（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无法作不重复的转移。
支付宝扫一扫
微信扫一扫
