《计算机基础课件 第10章 算法优化策略1》由会员分享，可在线阅读，更多相关《计算机基础课件 第10章 算法优化策略1（29页珍藏版）》请在金锄头文库上搜索。
1、1第第1010章章 算法优化策略算法优化策略2算法设计策略的比较与选择算法设计策略的比较与选择 3最大子段和问题最大子段和问题 给定由n个整数(可能为负整数)组成的序列a1,a2,an, 求该序列形如 的子段和的最大值。当所有整数均为 负整数时定义其最大子段和为。依此定义，所求的 最优值为:例如:A=(-2，11，-4，13，-5，-2)最大子段和为4简单算法简单算法public static int maxSum()int n=a.length-1;int sum=0;for (int i=1;isum) sum=thissum;besti=i;bestj=j;return sum;this
2、sum+=aj; 注意到 ，则可将算法 中的最后一个for循环省去，避 免重复计算只需要O(n2)的计算 时间。5分治算法分治算法 如果将所给的序列a1:n分为长度相等的2段a1:n/2和 an/2+1:n，分别求出这2段的最大子段和，则a1:n的 最大子段和有3种情况。 (1)a1:n的最大子段和与a1:n/2最大子段和相同； (2)a1:n的最大子段和与an/2+1:n最大子段和相同； (3)a1:n的最大子段和为 ，且1in/2，n/2+1jn 。 对于情形(3)。容易看出，an/2与an/2+1在最优子序 列中。因此，可以在a1:n/2中计算出 ，并在 an/2+1:n中计算出 。则s
3、1s2即为出现 情形(3)时的最优值。据此可设计出求最大子段和的分 治算法。复杂度分析T(n)=O(nlogn)6动态规划算法动态规划算法 记 ，1 j n，则所求的最大子段和为当bj-10时bj=bj-1+aj，否则bj=aj。由此可得计算bj的 动态规划递归式 bj=maxbj-1+aj，aj， 1 j n算法显然需要O(n)计算时间和O(n)空间。public static int maxSum()int n=a.length-1;int sum=0,b=0;for (int i=1;i0) b+=ai;else b=ai;if (bsum)sum=b;return sum;7最大子矩阵
4、和问题最大子矩阵和问题记 最大子矩阵和问题的最优值为由于其中， 设 ，则给定一个m行n列的整数矩阵a，试求矩阵a的一个子矩阵，使其 各元素之和为最大。 由于解最大子段和问题的动态规划算法需要时间O(n)，故算 法的双重for循环需要计算时间O(m2n)。8最大最大mm子段和问题子段和问题 给定由n个整数(可能为负整数)组成的序列a1,a2,an,以及一 个正整数m，要求确定序列的m个不相交子段，使这m个子段的总 和达到最大。 设b(i，j)表示数组a的前j项中i个子段和的最大值，且第i个子段 含aj(1 i m，i j n)。则所求的最优值显然为与最大子段和问题类似地，计算b(i，j)的递归式
5、为初始时，b(0，j)=0，(1 j n);b(i，0)=0，(1 i m)。 优化：注意到在上述算法中，计算bij时只用到数组b的第i-1 行和第i行的值。因而算法中只要存储数组b的当前行，不必存 储整个数组。另一方面，b(i-1，t)的值可以在计算第i-1行时预 先计算并保存起来。计算第i行的值时不必重新计算，节省了计 算时间和空间。 9动态规划加速原理动态规划加速原理 四边形不等式四边形不等式10货物储运问题货物储运问题 在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运 公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的 2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集
6、装箱数成正比。 给定各堆的集装箱数，试制定一个运输方案 ，使总运输费用最少。设合并ai:j，1ijn，所需的最少费用为mi,j，则原问题的最 优值为m1，n。由最优子结构性质可知，根据递归式，按通常方法可设计计算m(i,j)的O(n3)动态规划算法11四边形不等式四边形不等式 货物储运问题的动态规划递归式是下面更一般的递归计算式的 特殊情形。对于 ,当函数w(i,j)满足时称w满足四边形不等式。当函数w(i,j)满足 时称W关于区间包含关系单调 对于满足四边形不等式的单调函数w，可推知由递归式定义的 函数m(i,j)也满足四边形不等式，即12四边形不等式四边形不等式定义 由函数m(i,j)的四
7、边形不等式性质可推出函数s(i,j)的单调性，即根据前面的讨论，当w是满足四边形不等式的单调函数时，函 数s(i,j)单调，从而 s(i,j) s(i,j+1) s(i+1,j+1)，i j改进后算法speedDynamicProgramming所需的计算时间为 13问题的算法特征问题的算法特征14贪心策略贪心策略 采用每次合并集装箱数最少的相邻2堆货物的贪心策略，并不能 得到最优解。 适当放松相邻性约束，引入相容结点对概念。如图，原始结点用 方形结点表示，合并生成的结点用圆形结点表示。 最小相容结点对ai和aj 是满足下面条件的结点对： （1）结点ai和aj 之间没有方形结点； （2）在所有
8、满足条件（1）的结点中ai+aj的值最小； （3）在所有满足条件（1）和（2）的结点中下标 i 最小； （4）在所有满足条件（1）（2）和（3）的结点中下标 j 最小。 相应的最小相容合并树，如图所示。15相同层序定理相同层序定理 相同层序定理相同层序定理：存在货物储运问题的最优合并树，其各原始结：存在货物储运问题的最优合并树，其各原始结 点在最优合并树中所处的层序与相应的原始结点在相容合并树点在最优合并树中所处的层序与相应的原始结点在相容合并树 中所处的层序相同。中所处的层序相同。 根据上述定理，容易从各原始结点在相容合并树中所处的层序 构造出相应的最优合并树，如图所示。16算算 法法 1.
9、 组合阶段: 将给定的n个数作为方形结点依序从左到右排列， a1，a2，an。反复删除序列中最小相容结点对ai和aj ，(ib(i)。 设区间I(k)( ki )是区间集S(i)中的一个区间，1 i n。如果对于 S(i)的任意扩展S(i)T，当区间JT且在S(i)T中有从I(1)到J的 路时，在S(i)T中从I(1)到J的任一最短路都不含区间I(k)，则称 区间I(k)是S(i)中的无效区间。若S(i)中的区间I(k)不是无效区间则 称其为S(i)中的有效区间。19带权区间最短路问题带权区间最短路问题性质1：区间I(k)是S(i)中的有效区间，则对任意kji，区间I(k) 是S(j)中的有效
10、区间。另一方面，若区间I(k)是S(i)中的无效区间 ，则对任意ji，区间I(k)是S(j)中的无效区间。 性质2：集合S(i)中所有有效区间的并覆盖从a(1)到b(j)的线段， 其中b(j)是S(i)的最右有效区间的右端点。 性质3：区间I(i)是集合S(i)中的有效区间当且仅当在S(i)中有一 条从I(1)到I(i)的路。 性质4：当ik且dist(i,i)k），且 dist(i,i)k且dist(i,i)1)不包含S(k-1)中任一有效区间I(j)的右 端点b(j)，则对任意ik，I(k)是S(i)中的无效区间。 20带权区间图的最短路算法带权区间图的最短路算法算法shortestInt
11、ervalPaths 步骤1：dist(1,1)w(1)； 步骤2： for (i=2;iai 由aj+ak, kji所构成。 private static void backtrack(int step)/ 解最短加法链问题的标准回溯法int i,j,k;if (astep=n) / 找到一条加法链if (step=1;i-)if (2*aiastep)for (j=i;j=1;j-)k=ai+aj;astep+1=k;if (kastep)&(k2maj。由于加倍是加法 链中元素增大的最快的方式，即ai2ai-1，所以从aj到ai至少需要 m+1步。如果预期在状态空间树T的第d层找到关于n
12、的一条加法 链，则以状态空间树第i层结点ai为根的子树中，可在第d层找到 一条加法链的必要条件是2d-iain。 当 时，状态空间树中以结点ai为根的子树中不可能 在第d层之前找到最短加法链。 设在求正整数n的最短加法链的逐步深化迭代搜索算法中，当 前搜索深度为d。且正整数可表示为n=2t(2k+1)，k0，则在状 态空间树的第i层结点ai处的一个剪枝条件是28最短加法链长的上界最短加法链长的上界 与加法链问题密切相关的幂树给出了l(n)的更精确的上界。 假设已定义了幂树T的第k层结点，则T的第k+1层结点可定义 如下。依从左到右顺序取第k层结点ak，定义其按从左到右顺 序排列的儿子结点为ak+aj，0jk。其中a0,a1,ak，是从T 的根到结点ak的路径。且ak+aj在T中未出现过。 含正整数n的部分幂树T容易在线性时间内用迭代搜索方式构 造出来。29优化算法优化算法综合前面的讨论，对构造最短加法链的标准回溯法作如 下改进。(1)采用逐步深化迭代搜索策略；(2)利用l(n)的下界lb(n)对迭代深度作精确估计；(3)采用剪枝函数对问题的状态空间树进行剪枝搜索，加速搜 索进程；(4)用幂树构造l(n)的精确上界ub(n)。当lb(n)=ub(n)时，幂树给出的加法链已是最短加法链。当lb(n)ub(n)时，用改进后的逐步深化迭代搜索算法，从深 度d=lb(n)开始搜索。
