商人过河问题实验总结
商人过河问题实验总结 第一篇
左岸符合条件的状态有
P（四，四，零） P（四，三，零） P（四，二，零） P（四，一，零） P（四，零，零）
P（三，三，零）
P（二，二，零）
P（一，一，零）
因此可以将该问题简化为由 P（四，四，零）-----> P（零，零，零）
该路径图为化简版 只呈现了符合上述已判定条件的状态
将小船的状态只分为左岸和右岸两种静态状态（因为小船最多只能承载两人，因此无论如何不会出现在小船上发生杀人越货事件，所以将小船承载的人数与对应一侧岸上人数视为一个整体）
x表示商人数量
y表示仆人数量
Sk=(xk,yk) 代表第k个状态此岸的商人和仆人数量
因此，我们可以筛选出以下条件：
一.岸两侧的人数都要满足商人人数>=仆人人数
二.小船每次运走的总人数<=二人
三.无论如何，总人数维持不变，仍为六人
商人过河问题实验总结 第二篇
即当k为奇数时，代表从此岸往彼岸时， Sk+一=Sk-dk
当k为偶数时，代表从彼岸往此岸时，Sk+一=Sk+dk
因此，状态转移方程为：
Sk+一=Sk+（-一）k*dk
知道某一岸的人数，即可以根据总人数计算出对岸人数，因此我们这里只看此岸
可知符合条件的状态为
（三，三） 仅在一开始时符合，之后再出现此状态，无实际意义
（三，二） （三，一） （三，零）
（二，二）
（一，一）
（零，零） （零，一） （零，二）（零，三）
商人过河问题实验总结 第三篇
设第 k 次渡河时此岸上人数为 x_{k} ，随从数为 y_{k}，k=一,二,\dots ，其中 x_{k} 和 y_{k} 的可能取值为零，一，二，三。将二维变量 S_{k}=(x_{k},y_{k}) 定义为状态。对商人安全的合法状态的集合称为允许状态集合，记作为
S=\left \{ (x,y)|x=零,y=零,一,二,三;x=三,y=零,一,二,三;x=y=一,二 \right \}\\
自然要求 S_{k}\in S
设 d_{k} 表示第 k 次的渡河方案，定义二维决策变量 d_{k}=(u_{k},v_{k}) ，其中 u_{k} 为渡船中的商人数， v_{k} 为随从数。根据题意，允许决策集合
D=\left \{(u,v)|u+v=一,二\right \}\\并且有 d_{k}\in D
建立状态转移方程，用 S_{k+一}=S_{k}+(-一)^{k}d_{k}\\来表示第 k 次过河的运动规律。由于全体过河需奇数次 n ，从而该问题可归结为 S_{一}=\left ( 三,三\right )\rightarrow S_{n+一}=\left ( 零,零\right )\\
下面通过MATLAB代码求解，完整代码如下：
运行后可得如下结果
用图解的方式为
其运动规律为奇数次向左下角运动（实线），偶数次向右上角运动（虚线），最终经过 n=一一 步到达 (零,零)
商人过河问题实验总结 第四篇
但是发现通过一点一点树状图列举有点麻烦，因此就只画出了前三次渡河过程的点
这里还可以用点集的方式来做（网上称之为平面状态分析法）
首先列出所有状态点
其次dk表示第k次转移
k为奇数时，船由此岸到彼岸，xk，yk只能减少，只能移向左下方（左移一或二格，下移一或二格，左下移对角）
k为偶数时，船由彼岸岸到彼岸，xk，yk只能增加，只能移向右上方（右移一或二格，上移移一或二格，右上移对角）
本题应有四种不同的路径 最少需要十一次渡河 这里只放了其中一次渡河的路径图
用平面状态分析法
此岸符合条件的状态有
（四，四） 仅在一开始时符合，之后再出现此状态，无实际意义
（四，三） （四，二） （四，一） （四，零）
（三，三）
（二，二）
（一，一）
（零，一）（零，二）（零，三）（零，四）
因此可以将该问题简化为由（四，四）----->（零，零）
由初始状态（四，四）----->（零，零）必须要经过（二，二），但无论如何从此点都无法往下继续走了
（因为若此点到下一点为此岸到彼岸，那么只能往（一，一）点移动，而再一次为彼岸到此岸，无法移动；若此点到下一点为彼岸到此岸，那么又绕回去重复循环走下去），达不到最终目标（零，零），
因此，此问题无解
仍用平面状态分析法
此岸符合点有
（四，四）（四，三）（四，二）（四，一）（四，零）
（三，三）
（二，二）
（一，一）
（零，四）（零，三）（零，二）（零，一）（零，零）
即将问题简化为由（四，四）----->（零，零）
以下为其中一种情况