第七次(动态规划).ppt

1
第三章动态规划
算法设计与分析>目录
2
算法设计与分析>动态规划
16000, 10500, 36000, 87500, 34500
设有四个矩阵 A,B,C,D ,它们的维数分别是:
总共有五种计算顺序
所需乘法的计算量
例
A*((B*C)*D), A*(B*(C*D)), (A*B)*(C*D),
((A*B)*C)*D, (A*(B*C))*D,
策略:只需计算 A(BCD) ,(AB)(CD) , (ABC)D
A(BCD) 计算量取决于 B(CD)还是(BC)D
(ABC)D 计算量取决于 A(BC) 还是(AB)C
3
(Dynamic Programming)
将问题的求解过程化为多步选择,在每一步选择上,列出各种可能的结果(各子问题的可行解),.
基本思想
用以求解最优化问题
算法设计与分析>动态规划
[与贪心算法比较]:
贪心法:每采用一次贪心策略便做出唯一决策,求解过程只产生一个决策序列;求解过程自顶向下,不一定有最优解.
动态规划:求解过程多为自底向上,求解过程产生多个选择序列, 下一步的选择依赖上一步的结果..总能得到最优解
4
[适用问题] 具备最优子结构性质和子问题重叠性的最优化问题.
问题的整体的最优解中包含着它的子问题的最优解
算法设计与分析>动态规划
第i+1步问题的求解中包含第i步子问题的最优解,形成递归求解.
1).分析最优解的结构.
2).给出计算局部最优解值的递归关系.
3).自底向上计算局部最优解的值.
4).根据最优解的值构造最优解.
[常见应用]
0-1背包问题,图像压缩,最短路径,矩阵连乘,作业调度等等.
[算法步骤]
5
算法设计与分析>动态规划
3-2 在带权有向连通图中找一条从s到t的路权最小路径.
[子问题重叠性]当作第i步选择时(计算第i层各点的最短路径),会用到上一步的选择结果(i+1层各点的最短路径) .
[算法思路]将问题化为多步决策,,边数为2的各点到t的最短路...
[最优子结构]设l=(s=v1,v2,...vk=t)是S到t的最短径,vi是l的任一途中点,则(vi,...vk)是vi到T的一条最短路径.
S
T
ci=min{ c(i, j )+c j }, c(i,j):边<vi,vj>的权,vj为vi下一步各终点
[递归公式]
计算i层点: 设ci: 从vi到t的最短距离,则
6
S
T
ci=min{ c(i, j )+c j }
C8=c(8, t )=8
,C9=c(9, t )=4
C5=min{c(5, 8 )+C8 ,c(5, 9 )+C9}
=min{4+8, 8+4}=12
C6=min {c(6, 8 )+c8, c(6, 9 )+c9} =min{9+8, 6+4}=10
C7=min {c(7, 8 )+c8, c(7, 9 )+c9} =min{5+8, 4+4}=8
C2=min {c(2, 5)+c5, c(2, 6 )+c6} =min{10+12, 9+10,}=19
C3=min {c(3, 5)+c5, c(3, 6 )+c6, c(3, 7 )+c7}
=min {6+12, 7+10, 10+8}=17
C4=min {c(4, 6)+c6, c(4, 7 )+c7} = min {3+10, 8+8}=13
C1=min {c(1, 2)+c2, c(1, 3 )+c3, c(1, 4 )+c4}
= min {4+19, 2+17,3+13}=16
[算法效率]16个加法,9次比较
7
算法设计与分析>动态规划
for (int i=1:i<=n;i++)
d(i)=0; //最短路径长
for( int j=n-1;j<=1;j- -)
{若顶点r使<j,r>E,且d( j,r)+d(r)最小
d(j)= d( j,r)+d(r)
c(j)=r}
p(1)=1;
p(k)=n;//k为段数
for(int j=2;j<=k-1;j++)
p(j)=c(p(j-1))
最短路径算法的伪代码
(n+|E|)
(k)
算法复杂性: (n+|E|)
8
算法设计与分析>动态规划
矩阵乘法链
例三个矩阵相乘,两种计算顺序(A*B)*C, A*(B*C).
设A为1001矩阵,B为1  100矩阵,C为100  1矩阵, 则 D=A*