《数据结构-动态规划》由会员分享，可在线阅读，更多相关《数据结构-动态规划（80页珍藏版）》请在金锄头文库上搜索。
1、第15章 动态规划,学习内容,算法思想 应用 背包问题 图像压缩 矩阵乘法链 最短路径 无交叉子集 元件折叠,15.1 算法思想,最短路径问题：第一步，可选择2、3、4 选择3，问题变为求35的最短路径：因为，如果35不是最短路径，135也不可能是最短路径 最优化问题一系列最优决策 考虑多种可能决策序列,0/1背包问题,按i=1, 2, ., n的次序确定xi的值 对i = 1，有两种选择 xi=0物品2n，背包容量不变的背包问题 xi=1物品2n，背包容量c-w1的背包问题 两个结果选优即可 2n的背包问题怎么解决？递归,动态规划解0/1背包问题例,n=3, w=100, 14, 10, p
2、=20, 18, 15, c=116 xi=1剩余容量16，剩余物品2、3， 一种解x2, x3=1, 0，但x2, x3=1, 0更优 x1, x2, x3最优解必然包含x2, x3的最优解 最优解1, 1, 0，价值38 xi=0剩余容量116，x2, x3=1, 1最优 最优解0, 1, 1，价值33 考虑两个决策序列，1, 1, 0最优,航行费用问题,航线价格 亚特兰大纽约/芝加哥，洛杉机亚特兰大：$100 芝加哥纽约：$20 从亚特兰大转机芝加哥：$20 求洛杉机纽约最小费用航线 (洛杉机, 纽约)洛杉机亚特兰大(亚特兰大, 芝加哥)：最优$140,建立动态规划递归方程,背包问题：f
3、(i, y)背包剩余容量y，剩余物品i, i+1, ., n的最优解,递归计算或迭代计算 f(n, *)f(i, *)f(1, c),例,n=3, w=100, 14, 10, p=20, 18, 15, c=116 0y10，f(3, y)=0；y10，f(3, y)=15 0y10，f(2, y)=f(3, y)=0 10y14，f(2, y)=f(3, y)=15 14y24，f(2, y)=maxf(3, y), f(3, y-14)+18=18 24y，f(2, y)=maxf(3, y), f(3, y-14)+18=33 f(1, 116)=maxf(2, 116), f(2,
4、16)+20=38 上述计算过程已经隐含地得到了xi,x1=1,x2=1,x3=0,小结：动态规划思想,最优原则：principle of optimality 问题C可以分解为子问题A和子问题B 局部最优特性：无论A的决策如何，C的最优决策必然包含B的最优决策B不是最优，C也不可能最优！ 建立递归式计算最优解回溯构造最优解 避免递归实现迭代计算,15.2 应用,15.2.1 0/1背包问题 递归实现 int F(int i, int y) / Return f(i,y).if (i = n) return (y wn) ? 0 : pn;if (y wi) return F(i+1,y);
5、return max(F(i+1,y), F(i+1,y-wi) + pi); t(1)=a, t(n)2t(n-1)+bt(n)=O(2n),例,n=5，p=6,3,5,4,6，w=2,2,6,5,4，c=10,改进,权为整数数组fiy保存f(i, y) template void Knapsack(T p, int w, int c, int n, T* f) / Compute fiy for all i and y./ initialize fnint yMax = min(wn-1,c);for (int y = 0; y = yMax; y+)fny = 0;for (y = wn
6、; y 1; i-) yMax = min(wi-1,c);for (int y = 0; y = w1)f1c = max(f1c, f2c-w1 + p1); ,Q(cn),改进（续）,template void Traceback(T *f, int w, int c, int n, int x) / Compute x for optimal filling.for (int i = 1; i 2n，W(n2n) 三元组方法改进 (i, y, f(i,y)保存于hash表 计算f(i, y)前先检索hash表，若有，直接使用；若没有，进行计算，计算完毕插入hash表 二元组列表方法改进
7、 每个i一个列表P(i)：(y, f(i, y)按y递增顺序（也是f(i, y)递增顺序）保存,例,n=5，p=6,3,5,4,6，w=2,2,6,5,4，c=10 P(5)=(0,0),(4,6) P(4)= (0,0),(4,6),(9,10) P(3)= (0,0)(4,6),(9,10),(10,11) P(2)=(0,0)(2,3)(4,6)(6,9)(9,10)(10,11),P(i)的迭代计算,P(i)中：(a, b)、(c, d)，若ac，bd，则(a, b)被(c, d)支配，不加入P(i) 若wnc，则P(n)=(0, 0), (wn, pn) 由P(i+1)计算P(i)
8、计算Qxi=1的情况：(s, t)P(i+1)，若s+wic，则(s+wi, t+pi)Q P(i+1)：xi=0的情况 P(i+1)Q，除去受支配者和重复P(i),例,n=5，p=6,3,5,4,6，w=2,2,6,5,4，c=10 P(5)=(0,0),(4,6) Q=(5,4),(9,10)P(4)=(0,0),(4,6),(9,10) Q=(6,5),(10,11)P(3)=(0,0),(4,6),(9,10),(10,11) Q=(2,3),(6,9) P(2)=(0,0), (2,3), (4,6), (6,9), (9,10), (10,11) O(minnc, 2n),15.2
9、.2 图像压缩,图像：mm像素矩阵 像素值：0255，8位 压缩，变长模式，variable bit scheme 像素值0、11位，2、32位，. 压缩步骤 二维一维 分段段中像素占用位数相同 创建文件：SegmentLength，BitsPerSegment，Pixels 压缩文件,例,像素所需位数：4,4,4,6,6,6,4,4,4,4,4,4,4,8,8和8 分段:10,9,12、40,50,35、15,12,8,10,9,15,11、130,160,240,例（续）,文件SegmentLength内容：为2，2，6，2 BitsPerSegment内容为3，5，3，7 文件Pixel
10、s：前3个像素各4位，接下来3个各6位，下面7个各4位，最后3个各8位，前30位存储了前六个像素： 1010 1001 1100 111000 110010 100011 三个文件长度为：SegmentLength 32位；BitsPerSegment 12位；Pixels 82位，共126位 每个像素都用8位存储，128位，节省2位,改进,段标题：长度li、像素位数bi，11位 文件总长： 相邻段合并：Pixels可能变长，但减少一个段标题 上例 段1、段2合并 SegmentLength：5，6，2；BitsPerSegment：5，3，7，共节省11位 Pixel增加6位节省5位，121
11、位,段合并算法,sq：前q段最优合并所需空间，s0=0 考虑第i段 最优合并C中，段i-r+l, ., i-1, i进行合并 C的空间： 段1i-r空间+lsum(i-r+1, i)*bmax(i-r+1, i)+11 si=si-r+lsum(i-r+1, i)*bmax(i-r+1, i)+11 r应取值多少？kayi使si取最小值的k值,例,5个段，l=6, 3, 10, 2, 3, b=1, 2, 3, 2, 1 s0=0，s1=s0+l1*b1+11=17，kay1=1 s2=mins1+l2b2, s0+(l1+l2)*max(b1, b2)+11 =min17+6, 0+9*2+
12、11=29，kay2=2 s3=mins2+l3b3, s1+(l2+l3)*max(b2, b3), s0+(l1+ l2+l3)*max(b1, b2, b3)+11=min29+30, 17+13*3, 0+19*3+11=67，kay3=2 类似得s4=73, s5=82, kay4=3, kay5=4 由kay值可知，合并方法为：段1不变，25合并,递归实现,int S(int i) / Return S(i) and compute kayi.if (i = 0) return 0;/ compute min term of Eq. 15.3 for k = 1int lsum =
13、 li, bmax = bi;int s = S(i-1) + lsum * bmax;kayi = 1;,递归实现（续）,/ compute min term for remaining k and find minfor (int k = 2; k t + lsum * bmax) s = t + lsum * bmax;kayi = k;return s + header; ,O(2n),输出合并方案,void Traceback(int kay, int n) / Decompose into segments.if (n = 0) return;Traceback(kay, n-ka
14、yn);cout “New segment begins at “ (n - kayn + 1) 0) return si; / already computed/ compute si/ first compute min term of Eq. 15.3 for k = 1int lsum = li, bmax = bi;si = S(i-1) + lsum * bmax;kayi = 1;,避免重复计算（续）,/ compute min term for remaining k and updatefor (int k = 2; k t + lsum * bmax) si = t + lsum * bmax;kayi = k;si += header;return si; ,复杂性分析摊还分析,上面非递归实现也可看作函数S多次运行 调用S(i)计算si所执行的操作包括 对S(i-1)的一次调用 对每个k=2i，S(i-k)的一次调用，但注意，循环次数还受到L（常量256）的限制，因此调用总次数不是与i呈线性，考虑最坏情况，可以认为是一个常量K 同理，循环内其他操作的总时间也可认为是常量，循环外操作时间显然为常量 t(i)为S(i)所需时间,
