算法与设计：动态规划法.ppt

算法设计与分析
广东白云学院 计算机科学系
2010-2011学年 第2学期
第3章 动态规划法
2021/3/11
1
本 章 目 录
返回
概 述
图问题中的动态规划法
组合问题中的动态规划法
查找问题中的动态规划法
2021/3/11
2
概 述
最优化问题
最优性原理
动态规划法的设计思想
返回
动态规划法简介
2021/3/11
3
动态规划法与分治法类似，其基本思想也是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
动态规划法简介
2021/3/11
4
与分治法不同的是，适合用动态规划求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法解这类问题，则分解得到的子问题太多，以致于最后解决原问题需要耗费指数时间。在用分治求解时，有些子问题被重复计算了多次。如果能够保存已解决的子问题的答案。在需要的时候再找出已求的答案，就可以避免大量的重复计算，从而简化了算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题答案。不管该子问题以后是否被用到，只要他被计算过，就将其结果填入表中。这就是动态规划法的基本思想。
2021/3/11
5
图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少?
多阶段决策过程最优化问题
2021/3/11
6
最短路径的特性:最短路径的第k阶段通过Xk 点，则这一最短路径在由Xk 出发到终点的那一部分路径，对于起始点为Xk 到终点的所有可能的路径来说必定也是路径最短的.
2021/3/11
7
利用倒推方法求解A到E的最短距离。把从A到E的全过程分成四个阶段，用k表示阶段变量，第1阶段有一个初始状态A，两条可供选择的支路ABl、AB2；第2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路……。用dk( xk，xk+1 )表示在第k阶段由初始状态xk 到下阶段的初始状态xk+1的路径距离，Fk(xk)表示从第k阶段的xk 到终点E的最短距离。
2021/3/11
8
求从A到E的最短路问题Fk(A) ，可以转化为两个性质完全相同，但规模较小的问题，即分别从B1、B2到E的最短路问题Fk(B1)和Fk(B2)，这时有：
Fk(A)=min{d1(A,B1)+ Fk(B1),d1(A,B2)+ Fk(B2)}
同样， 计算Fk(B1) ，又可以转化为性质完全相同，但规模更小的问题，即分别从C1、C2、C3到E的最短路问题Fk(C1)、 Fk(C2)和 Fk(C3)，……，最后，归结为Fk(D1)、 Fk(D2)两个子问题。由于Fk(D1)、 Fk(D2)是已知的，因此，可以从这两个值开始，逆向递归计算出Fk(A)的值。最终，可以得到从A到E的最短路径。
动态规划法就是根据最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。（逆向递归的方法）
2021/3/11
9
S1：K=4，有：
F4(D1)=3，F4(D2)=4，F4(D3)=3
S2: K=3，有：
F3(C1)=min{d3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2)}
=min{8,10}=8
F3(C2)=d3(C2,D1)+F4(D1)=5+3=8
F3(C3)=d3(C3,D3)+F4(D3)=8+3=11
F3(C4)=d3(C4,D3)+F4(D3)=3+3=6
S2: K=2，有：
F2(B1)=min{d2(B1,C1)+F3(C1),d2(B1,C2)+F3(C2),d2(B1,C3)
+F3(C3)}=min{9,14,14}=9
F2(B2)=min{d2(B2,c2)+F3(C2),d2(B2,C4)+F3(C4)}
=min{16,10}=10
S4：k=1，有：
F1( A)=min{d1(A,B1)+F2(B1),d1(A,B2)+F2(B2)}
=min{14,13}=13
因此由A到E的全过程的最短路径为 A—>B2一>C4—>D3—>E,
最短路程长度为13。
2021/3/11
10