《它建立在最优原则的基础上,和贪婪算法一样,在动态规划》由会员分享，可在线阅读，更多相关《它建立在最优原则的基础上,和贪婪算法一样,在动态规划（29页珍藏版）》请在金锄头文库上搜索。
1、它建立在最优原则的基础上,和贪婪算法一样，在动态规划中，可将一个问题的解决方案视 为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤 回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。 也就是说，可以把某个问题分成若干个阶段，而每个阶段都可以从若干个以前的阶段通过 一个最优策略转移过来，而当前阶段的最优解就是从这些转移的过程中选出最好的那个， 由于每一个前面考虑过的阶段的状态都是最优的，所以当前的阶段所处的状态也是最优的。如果，还有问题可以加我 QQ491727826，我有资料。多阶段决策过程（multistep decision proc
2、ess）是指这样一类特殊的活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每一个阶段都需要做出决策，全部过程的决策是一个决策序列。动态规划（dynamic programming）算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的
3、解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。 ; Al!n 嶋 动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质：最优子结构性质和子问题重叠性质。 ? ) 刀 1、最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理） 。最优子结构性质为动态规划算法解决问题提供了重要线索。 墆蟗抚戔堶 2、子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解
4、时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率。:?A 銎 O? 当我们已经确定待解决的问题需要用动态规划算法求解时，通常可以按照以下步骤设计动态规划算法： 觊估z 窈/ 1、分析问题的最优解，找出最优解的性质，并刻画其结构特征； T? m 煹 2、递归地定义最优值； 輨瀀甋茝 3 3、采用自底向上的方式计算问题的最优值； ?F 銕潤腒? 4、根据计算最优值时得到的信息，构造最优解。
5、! 挃 S 荁鱶 13 步是动态规划算法解决问题的基本步骤，在只需要计算最优值的问题中，完成这三个基本步骤就可以了。如果问题需要构造最优解，还要执行第 4 步；此时，在第 3 步通常需要记录更多的信息，以便在步骤 4 中，有足够的信息快速地构造出最优解。 絙帢繇 挾 下面通过对具体实例的分析，帮助大家领会可用动态规划算法求解的问题应具有的两个性质以及动态规划算法的设计思想。 fB 琬 蟾觹? 例：拦截导弹（问题来源：1999 年全国青少年信息学（计算机）奥林匹克分区联赛高中组复赛试题第一题） 茜鯡 a48 薗 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：
6、虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 67 ?q 输入导弹依次飞来的高度（雷达给出的高度数据是不大于 30000 的正整数） ，计算这套系统最多能拦截多少导弹，并依次输出被拦截的导弹飞来时候的高度。 狜 4*?榜 样例： next i ?纝乩=诳? for i=n-1 to 1 step -1 屏A 巖 K=? for j=i+1 to n ?磷 贴哳? if x(j)dmax then !k 屠憀遢 W/ dmax=D(i) ?觔 kf 誛? x
7、h=i ? 憋%傯 endif I ? next i 閩篙_譧 N? 我们在计算最优值时保存了被拦截的第一枚导弹的顺序号 xh。接下来通过这个信息构造问题的最优解（由所有被拦截的导弹的高度组成的非递增序列） 。算法代码如下： 壊%c? j=xh 諨 4 胔 tW? print x(j) a?c i 煟? for i=j+1 to n Cy 榜*鹱 if x(i)void Knapsack(T p, int w, int c, int n, T* f)/ 对于所有 i 和 y 计算 f i y / 初始化 f n for (int y = 0; y 1; i-) for (int y = 0;
8、y = w1)f1c = max(f1c, f2c-w1 + p1);templatevoid Traceback(T *f, int w, int c, int n, int x)/ 计算 xfor (int i = 1; i t + lsum * bmax) s = t + lsum * bmax;kayi = k;return s + header;void Traceback(int kay, int n)/ 合并段if (n = 0) return;Tr a c e b a c k ( k a y, n-kayn);cout 0) return si; /已计算完/ /计算 s i
9、/ /首先根据公式（1 5 - 3）计算 k = 1 时最小值int lsum = li, bmax = bi;si =S(i-1) + lsum * bmax;kayi = 1;/ /对其余的 k 计算最小值并更新for (int k = 2; k t + lsum * bmax) si = t + lsum * bmax;kayi = k;si += header;return si;为了确定程序 1 5 - 4 的时间复杂性，我们将使用分期计算模式（ amortization scheme）。在该模式中，总时间被分解为若干个不同项，通过计算各项的时间然后求和来获得总时间。当计算 si 时
10、，若 sj 还未算出，则把调用 S(j) 的消耗计入 sj ；若 sj 已算出，则把 S(j) 的消耗计入 si (这里 sj 依次把计算新 sq 的消耗转移至每个 sq )。程序 1 5 - 4 的其他消耗也被计入 si。因为L 是 2 5 6 之内的常数且每个 li 至少为 1，所以程序 1 5 - 4 的其他消耗为( 1 )，即计入每个 si 的量是一个常数，且 si 数目为n，因而总工作量为(n)。3. 迭代方法倘若用式（1 5 - 3）依序计算 s1 , ., sn，便可得到一个复杂性为(n)的迭代方法。在该方法中，在 si 计算之前， sj 必须已计算好。该方法的代码见程序 1 5
11、 - 5，其中仍利用函数 Tr a c e b a c k（见程序 1 5 - 3）来获得最优合并。程序 15-5 迭代计算 s 和 k a yvoid Vbits (int l, int b, int n, int s, int kay) / /计算 s i 和 k a y i int L = 256, header = 11 ;s0 = 0;/ /根据式（1 5 - 3）计算 s i for (int i = 1; i si-k + lsum * bmax)si = si-k + lsum * bmax;kayi = k; si += header;3.2.3 矩阵乘法链mn 矩阵 A 与
12、 np 矩阵 B 相乘需耗费(m n p)的时间（见第 2 章练习 1 6）。我们把 m n p 作为两个矩阵相乘所需时间的测量值。现假定要计算三个矩阵 A、B 和 C 的乘积，有两种方式计算此乘积。在第一种方式中，先用 A 乘以 B 得到矩阵 D，然后D 乘以 C 得到最终结果，这种乘法的顺序可写为(A*B) *C。第二种方式写为 A* (B*C) ,道理同上。尽管这两种不同的计算顺序所得的结果相同，但时间消耗会有很大的差距。例 3-12 假定 A 为 1 0 01 矩阵，B 为 11 0 0 矩阵，C 为 1 0 01 矩阵，则 A*B 的时间耗费为 10 0 0 0，得到的结果 D 为
13、1 0 01 0 0 矩阵，再与 C 相乘所需的时间耗费为 1 000 000，因此计算(A*B) *C 的总时间为 1 010 000。B*C 的时间耗费为 10 000，得到的中间矩阵为 11 矩阵，再与 A 相乘的时间消耗为 1 0 0，因而计算 A*（B*C）的时间耗费竟只有 10 100！而且，计算（ A*B）*C 时，还需 10 000 个单元来存储 A*B，而 A*（B*C）计算过程中，只需用 1 个单元来存储 B*C。下面举一个得益于选择合适秩序计算 A*B*C 矩阵的实例：考虑两个 3 维图像的匹配。图像匹配问题的要求是，确定一个图像需旋转、平移和缩放多少次才能逼近另一个图像
14、。实现匹配的方法之一便是执行约 1 0 0 次迭代计算，每次迭代需计算 1 21个向量 T：T=?A(x, y, z) *B(x, y, z)*C(x, y, z )其中 A，B 和 C 分别为 1 23，33 和 31 矩阵。(x , y, z) 为矩阵中向量的坐标。设 t 表示计算 A(x , y, z) *B(x , y, z) *C(x , y, z)的计算量。假定此图像含 2 5 62 5 62 5 6 个向量，在此条件中，这 1 0 0 个迭代所需的总计算量近似为 1 0 0 * 2 5 63 * t1 . 7 * 1 09 t。若三个矩阵是按由左向右的顺序相乘的，则 t = 1
15、2 * 3 * 3 + 1 2 * 3 *1= 1 4 4；但如果从右向左相乘， t = 3 * 3 * 1 + 1 2 * 3 * 1 = 4 5。由左至右计算约需 2 . 4 * 1 011 个操作，而由右至左计算大概只需 7 . 5 * 1 01 0 个操作。假如使用一个每秒可执行 1 亿次操作的计算机，由左至右需 4 0 分钟，而由右至左只需 1 2 . 5 分钟。在计算矩阵运算 A*B*C 时，仅有两种乘法顺序（由左至右或由右至左），所以可以很容易算出每种顺序所需要的操作数，并选择操作数比较少的那种乘法顺序。但对于更多矩阵相乘来说，情况要复杂得多。如计算矩阵乘积 M1M2.Mq，其中
16、 Mi 是一个 riri + 1 矩阵( 1iq)。不妨考虑 q=4 的情况，此时矩阵运算 A*B*C*D 可按以下方式（顺序）计算：A* ( (B*C) *D) A* (B* (C*D) (A*B) * (C*D) (A* (B*C) ) *D不难看出计算的方法数会随 q 以指数级增加。因此，对于很大的 q 来说，考虑每一种计算顺序并选择最优者已是不切实际的。现在要介绍一种采用动态规划方法获得矩阵乘法次序的最优策略。这种方法可将算法的时间消耗降为(q3 )。用 Mi j 表示链Mi.Mj （ij）的乘积。设 c(i,j) 为用最优法计算 Mi j 的消耗，k a y(i, j) 为用最优法计算 Mi j 的最后
