商人过河
一?/p>
问题重述
问题一?/p>
4
个商人带着
4
个随从过河,过河的工具只有一艘小船,只能?/p>
时载两个人过河,
包括划船的人?/p>
随从们密?/p>
,
在河的任一?/p>
,
一旦随从的人数
比商人多
,
就杀人越货?/p>
乘船渡河的方案由商人决定?/p>
商人们怎样才能安全过河
?
问题二:
假如小船可以?/p>
3
人,
请问最多可以有几名商人各带一名随从安?/p>
过河?/p>
二、问题分?/p>
问题可以看做一个多步决策过程?/p>
每一步由此岸到彼岸或彼岸到此岸船上的
人员在安全的前提?/p>
(
两岸的随从数不比商人?/p>
),
经有限步使全体人员过河。用
状态变量表示某一岸的人员状况?/p>
决策变量表示船上的人员情况,
可以找出状?/p>
随决策变化的规律?/p>
问题就转换为在状态的允许变化范围?/p>
(即安全渡河条件?/p>
?/p>
确定每一步的决策,达到安全渡河的目标?/p>
三.问题假设
1.
过河途中不会出现不可抗力的自然因素?/p>
2.
当随从人数大于商人数时,随从们不会改变杀人的计划?/p>
3
.船的质量很好,在多次满载的情况下也能正常运作?/p>
4.
随从会听从商人的调度?/p>
四、模型构?/p>
x(k)~
?/p>
k
次渡河前此岸的商人数
x(k),y(k)=0,1,2,3,4;
y(k)~
?/p>
k
次渡河前此岸的随从数
k=1,2,
?/p>
..
s(k)=[ x(k), y(k)]~
过程的状?/p>
S~
允许状态集?/p>
S={(x,y)

x=0,y=0,1,2,3,4; x=4,y=0,1,2,3,4;x=y=1,2,3}
u(k)~
?/p>
k
次渡船上的商人数
u(k), v(k)=0,1,2;