动态规划初步.pptx

动态规划初步
JSOI2011夏令营B层次()
江苏省扬州中学倪震祥
最短路径问题---求A到E的最短路的长度
2011 信息学夏令营倪震祥
穷举?贪心?搜索?
2011 信息学夏令营倪震祥
思考: 仔细观察本图路径的特殊性,可以分成4个阶段:
第一阶段:A经过A-B1或A-B2到B
第二阶段:B1有三条路通……;B2有两条通路……
阶段1
阶段2
阶段3
阶段4
2011 信息学夏令营倪震祥
思考:倒着推;设F(x)表示x到E的最短路径的长度
阶段4:F(D1)=3;F(D2)=4;F(D3)=3
阶段3:F(C1)=min{F(D1)+C1到D1的路径长度, F(D2)+C1到D2的路径长度}
F(C2)……
阶段1
阶段2
阶段3
阶段4
2011 信息学夏令营倪震祥
2011 信息学夏令营倪震祥
我们把F(x) 称为当前x的状态;
在这个例子中每个阶段的选择依赖当前的状态,又随即引起状态的转移,一个决策序列(E –D3-C4-B2-A)就是在变化的状态中产生的,故有“动态”的含义。
阶段1
阶段2
阶段3
阶段4
基本概念
2011 信息学夏令营倪震祥
阶段:
问题的过程被分成若干相互联系的部分,我们成为阶段,以便按一定的次序求解。
状态:
某一阶段的出发位置称为状态,通常一个阶段包含若干状态。
决策:
对问题的处理中作出的每种选择的行动就是决策。即从该阶段的每个状态出发,通过一次选择性的行动移至下一个阶段的相应状态。
2011 信息学夏令营倪震祥
数字三角形
一个由非负数组成的三角形,第一行只有一个数,除了最下行之外每个数的左下方和右下方各有个数,从第一行的数开始,每次可以选择向左下或是向右下走一格,一直走到最下行,把沿途经过的数全部加起来。如何走才能使得这个和尽量大?。
数字三角形
格子编号
穷举?贪心?搜索?
数组存储
深搜(递归实现)
程序清单:
var a:array[1..4,1..4] of integer;
i,j,s,max:integer;
procedure f(i,j:integer);
begin
s:=s+a[i,j];
if i=4 then
begin
if s>max then max:=s;
end
else begin
f(i+1,j);
s:=s-a[i+1,j];
f(i+1,j+1);
s:=s-a[i+1,j+1];
end;
end;
2011 信息学夏令营倪震祥
格子编号
begin
for i:=1 to 4 do
for j:=1 to i do
read(a[i,j]);
f(1,1);
write(max);
end.
2011 信息学夏令营倪震祥
分析:考察
我们关心的是从某处出发到底部的最大和,如果把从开始出发的最大和记做d(1,1);
从(2,1)点出发的最大和记做d(2,1);
从(2,2)点出发的最大和记做d(2,2);
从(1,1)出发有两种选择(2,1)或(2,2)
在已知d(2,1)和d(2,2)的情况下,应选择较大的一个。