动态规划1.ppt

文档介绍：最优化方法
动态规划
商人们怎样安全过河
问题(智力游戏)
 3名商人
 3名随从
随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就***越货.
?
问题分析
多步决策过程
决策~ 每一步(此岸到彼岸或彼岸到此岸)船上的人员
要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.
河
小船(至多2人)
他们自己划船
彼岸
此岸
模型构成
xk~第k次渡河前此岸的商人数
yk~第k次渡河前此岸的随从数
xk, yk=0,1,2,3;
k=1,2,
sk=(xk , yk)~过程的状态
S={(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2}
S ~ 允许状态集合
uk~第k次渡船上的商人数
vk~第k次渡船上的随从数
dk=(uk , vk)~决策
D={(u , v) u+v=1, 2} ~允许决策集合
uk, vk=0,1,2;
k=1,2,
sk+1=sk dk
+(-1)k
~状态转移律
求dkD(k=1,2, n), 使skS, 并按转移律由 s1=(3,3)到达 sn+1=(0,0).
多步决策问题
模型求解
x
y
3
3
2
2
1
1
0
穷举法
图解法
状态s=(x,y) ~ 16个格点
~ 10个点
允许决策~ 移动1或2格; k奇,左下移; k偶,右上移.
s1
sn+1
d1, ,d11给出安全渡河方案
评注和思考
规格化方法,易于推广
考虑4名商人各带一随从的情况
d1
d11
允许状态
S={(x , y) x=0, y=0,1,2,3;
x=3, y=0,1,2,3; x=y=1,2}
人带猫、鸡、米过河
人带着猫、鸡、米、过河,船除需要人
划外,至多能载猫、鸡、米三者之一,而
当人不在场时猫要吃鸡、鸡要吃米,试设
计一个安全的过河方案,并使渡河次数尽
量地少。