动态规划课件[精].ppt

第五章动态规划

动态规划算法的设计要素
动态规划算法的典型应用
投资问题;
0-1背包问题;
最优二叉搜索树问题
引例: 多段图的最短路径问题
设图G=(V, E)是一个带权有向连通图,如果把顶点集合V划分成k个互不相交的子集Vi(2≤k≤n, 1≤i≤k),使得E中的任何一条边(u, v),必有u∈Vi,v∈Vi+m(1≤i<k, 1<i+m≤k),则称图G为多段图,称s∈V1为源点,t∈Vk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。
2
1
2
0
3
4
5
6
7
8
9
4
9
3
8
7
6
8
4
7
5
6
8
6
6
5
3
7
一个多段图
由于多段图将顶点划分为k个互不相交的子集,所以,多段图划分为k段,每一段包含顶点的一个子集。不失一般性,将多段图的顶点按照段的顺序进行编号,同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n,则源点s的编号为0,终点t的编号为n-1,并且,对图中的任何一条边(u, v),顶点u的编号小于顶点v的编号。
对多段图的边(u, v),用cuv表示边上的权值,将从源点s到终点t的最短路径记为d(s, t),则从源点0到终点9的最短路径d(0, 9)由下式确定:
d(0, 9)=min{c01+d(1, 9), c02+d(2, 9), c03+d(3, 9)}
这是最后一个阶段的决策,它依赖于d(1, 9)、d(2, 9)和d(3, 9)的计算结果,而
d(1, 9)=min{c14+d(4, 9), c15+d(5, 9)}
d(2, 9)=min{c24+d(4, 9), c25+d(5, 9), c26+d(6, 9)}
d(3, 9)=min{c35+d(5, 9), c36+d(6, 9)}
这一阶段的决策又依赖于d(4, 9)、d(5, 9)和d(6, 9)的计算结果:
下面考虑多段图的最短路径问题的填表形式。
用一个数组cost[n]作为存储子问题解的表格,cost[i]表示从顶点i到终点n-1的最短路径,数组path[n]存储状态,path[i]表示从顶点i到终点n-1的路径上顶点i的下一个顶点。则:
cost[i]=min{cij+cost[j]} (i≤j≤n且顶点j是顶点i的邻接点)
(式1)
path[i]=使cij+cost[j]最小的j (式2)
算法1——多段图的最短路径
:数组cost[n]初始化为最大值,数组path[n]初始化为-1;
(i=n-2; i>=0; i--)
对顶点i的每一个邻接点j,[i];
[i];
[0];
4. 输出最短路径经过的顶点:
i=0
循环直到path[i]=n-1
输出path[i];
i=path[i];
伪代码
算法1主要由三部分组成:第一部分是初始化部分,其时间性能为O(n);第二部分是依次计算各个顶点到终点的最短路径,由两层嵌套的循环组成,外层循环执行n-1次,内层循环对所有出边进行计算,并且在所有循环中,每条出边只计算一次。假定图的边数为m,则这部分的时间性能是O(m);第三部分是输出最短路径经过的顶点,其时间性能是O(n)。所以,算法1的时间复杂性为O(n+m)。
动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于,它可以把一个n 维决策问题变换为几个一维最优化问题,从而一个一个地去解决。
需指出:动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种算法。必须对具体问题进行具体分析,运用动态规划的原理和方法,建立相应的模型,然后再用动态规划方法去求解。
1 多阶段决策问题
动态规划的基本思想