第3章 动态规划(0-算法思想)

第3章动态规划

学习要点:

理解动态规划算法的概念。掌握动态规划算法的基本要素 (1)最优子结构性质 (2)重叠子问题性质掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。2

通过应用范例学习动态规划算法设计策略。 (1)矩阵连乘问题； (2)最长公共子序列； (3)最大子段和； (4)凸多边形最优三角剖分； (5)多边形游戏； (6)图像压缩； (7)0-1背包问题

先来看几个例子，引入“动态规划”思想数塔问题：有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。

9 12 10 2 19 7 18 10 6 9 4 15 8 5 16

自顶向下的分析，自底向上的计算最优解的结构(最优子结构性质)子问题重叠性质4

假设a[i, j]表示数塔中从上到下第i层，从左向右第j个数的数值，且设m[i, j]表示数塔从上到下第i层，从左向右第j个数所具有的最大路径和的值。那么就有如下递推的式子：

i n a[i, j] m[i, j] max{m[i 1, j], m[i 1, j 1]} a[i, j] 1 i n对于m数组填充时应该从底向上，从左向右，如下图。j n n-1

最优值

……

1 1 n-1 n i5

最短路径问题： (多阶段图)地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，我们想从城市A到达城市E,怎样走路程最短，最短路程的长度是多少？

A -> E

B1 -> E, B2 -> E

C1->E, C2->E, C3->E C2->E, C4->E

C2 -> E被计算2遍 D1 -> E被计算4遍……

……7

注意：任何一条最短路径的子路径都是相对于子路径的始点和终点的最短路径做一个表记录下每个点到E的最短路径，从末端往源端填充表。8

再看一例：

最优子结构：如果ABEG是 A到G的最短路径，那么 ABE也是A到 E的最短路径。

旅行售货员问题(货郎担问题)找出有向图中一条代价最小的周游回路 某推销员从城市1出发，要到若干城市推销商品,已知各城市之间的路程(或旅费). 他要选定一条从驻地1出发,经过每个城市一遍最后回到驻地的路线,要求使总花费最小.

1–2–4–3–1最小旅费： 10+10+9+6=35

分析：

假设从顶点1出发，下一个顶点t从V-{1}中选择若1 t … 1是最佳路线，那么，t … 1一定是从t到1的最佳路线

设g(i, S)是从顶点i出发，经过S集合中的每个顶点一次且仅一次，回到顶点1的

最佳路线的长度，则：

g (i, S ) min{ci, j g ( j, S { j})}j S ( i, j ) E

令：g (i, ) ci,114

|S|=0: g(2, )=c2,1=5 g(3, )=c3,1=6 g(4, )=c4,1=20 |S|=1: g(2,{3})=c2,3+g(3, )=15 g(2,{4})=c2,4+g(4, )=18 g(3,{2})=c3,2+g(2, )=18 g(3,{4})=c3,4+g(4, )=32 g(4,{2})=c4,2+g(2, )=13 g(4,{3})=c4,3+g(3, )=15 15

|S|=2 g(2,{3,4})=min{c2,3+g(3,{4}),c2,4+g(4,{3})}=25 g(3,{2,4})=min{c3,2+g(2,{4}),c3,4+g(4,{2})}=25 g(4,{2,3})=min{c4,2+g(2,{3}),c4,3+g(3,{2})}=23 |S|=3 g(1,{2,3,4})=min{c1,2+g(2,{3,4}),c1,3+g(3,{2,4}), c1,4+g(4,{2,3})}={35,40,43}=35

最佳线路：1 2 4 3 1