算法优化策略.ppt

《算法优化策略.ppt》由会员分享，可在线阅读，更多相关《算法优化策略.ppt（29页珍藏版）》请在三一文库上搜索。

1、1,第10章 算法优化策略,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; ,thissum+=aj;,注意到 ，则可将算

2、法中的最后一个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中计算出 。则s1s2即为出现情形(3)时的最优值。据此可设计出求最大子

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,最大m子段和问题,给定由n个整数(可能为负整数)组成的序列a1,a2,an,以及一个正整数m，要求确定序列的m个不相交子段，使这m个子段的总和达到最大。,设b(i，j)表示数组a的前j项中i个子段和的最大值，且第i个子段含aj(1 i m，i j n)。则所求的最优值显然为 与最大子段和问题类似地，计算b(i，j)的递归式为 初始时，b(0，j)=0，(1 j n);b(i，0)=0，(1

5、 i m)。,优化：注意到在上述算法中，计算bij时只用到数组b的第i-1行和第i行的值。因而算法中只要存储数组b的当前行，不必存储整个数组。另一方面，b(i-1，t)的值可以在计算第i-1行时预先计算并保存起来。计算第i行的值时不必重新计算，节省了计算时间和空间。,9,动态规划加速原理,四边形不等式,10,货物储运问题,在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。 给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。,设合并ai:j，1ijn，所需的最少费

6、用为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)的四边形不等式性质可推出函数s(i,j)的单调性，即 根据前面的讨论，当w是满足四边形不等式的单调函数时，函数s(i,j)单调，从

7、而,s(i,j) s(i,j+1) s(i+1,j+1)，i j,改进后算法speedDynamicProgramming所需的计算时间为,13,问题的算法特征,14,贪心策略,采用每次合并集装箱数最少的相邻2堆货物的贪心策略，并不能得到最优解。 适当放松相邻性约束，引入相容结点对概念。如图，原始结点用方形结点表示，合并生成的结点用圆形结点表示。 最小相容结点对ai和aj 是满足下面条件的结点对： （1）结点ai和aj 之间没有方形结点； （2）在所有满足条件（1）的结点中ai+aj的值最小； （3）在所有满足条件（1）和（2）的结点中下标 i 最小； （4）在所有满足条件（1）（2）和（3）

8、的结点中下标 j 最小。 相应的最小相容合并树，如图所示。,15,相同层序定理,相同层序定理：存在货物储运问题的最优合并树，其各原始结点在最优合并树中所处的层序与相应的原始结点在相容合并树中所处的层序相同。,根据上述定理，容易从各原始结点在相容合并树中所处的层序构造出相应的最优合并树，如图所示。,16,算 法,1. 组合阶段: 将给定的n个数作为方形结点依序从左到右排列，a1，a2，an。反复删除序列中最小相容结点对ai和aj，(ij)，并在位置i处插入值为ai+aj的圆形结点，直至序列中只剩下1个结点。O(nlogn) 2. 标记层序阶段: 将第一阶段结束后留下的惟一结点标记为第0层结点。然

9、后以与第一阶段相反的组合顺序标记其余结点的层序。O(n) 3. 重组阶段: 根据标记层序阶段计算出的各结点的层序，按下述规则重组。O(n) 结点ai和aj重组为新结点应满足： （1）ai和aj在当前序列中相邻； （2）ai和aj均为当前序列中最大层序结点； （3）在所有满足条件（1）和（2）的结点中，下标 i 最小。,17,优化数据结构,18,带权区间最短路问题,S是直线上n个带权区间的集合。从区间IS到区间JS的一条路是S的一个区间序列 J(1)，J(2)，J(k)，其中 J(1) = I，J(k) = J，且对所有1 i k-1, J(i)与J(i+1)相交。这条路的长度定义为路上各区间权

10、之和。在所有从I到J的路中，路长最短的路称为从I到J的最短路。带权区间图的单源最短路问题要求计算从S中一个特定的源区间到S中所有其他区间之间的最短路。 区间集S(i)的扩展定义为：S(i)T，其中T是满足下面条件的另一区间集。T中任意区间I=a,b均有bb(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,带

11、权区间最短路问题,性质1：区间I(k)是S(i)中的有效区间，则对任意kji，区间I(k)是S(j)中的有效区间。另一方面，若区间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)dist(k,i)时，I(k)是S(i)中的无效区间。 性质5：设I(j(1)，I(j(2)，I(j(k)是S(i)中的有效区间，且j

12、(1)j(2)j(k)i，则dist(j(1),i) dist(j(2),i) dist(j(k),i)。,性质6：如果区间I(i)包含区间I(k)（因此ik），且dist(i,i)k且dist(i,i)1)不包含S(k-1)中任一有效区间I(j)的右端点b(j)，则对任意ik，I(k)是S(i)中的无效区间。,20,带权区间图的最短路算法,算法shortestIntervalPaths 步骤1：dist(1,1)w(1)； 步骤2： for (i=2;i=n;i+) (2.1): j=min k | a(i)b(k);1ki ; if (j不存在) dist(i,i)+; else dist

13、(i,i)dist(j,i-1)+w(i); (2.2): for (ki) if (dist(i,i)dist(k,i-1) dist(k,i)+; else dist(k,i)dist(k,i-1); ,步骤3： for (i=2;i=n;i+) if (dist(i,n)=+) j=min k | (dist(k,n)+) ,上述算法的关键是有效地实现步骤(2.1)和(2.2),21,实现方案1,用一棵平衡搜索树（2-3树）存储当前区间集S(i)中的有效区间。以区间的右端点的值为序。如图所示。,(2.1)的实现对应于平衡搜索树从根到叶的一条路径上的搜索，在最坏情况下需要时间O(logn)

14、。 (2.2)的实现对应于反复检查并删除平衡搜索树中最右叶结点的前驱结点。在最坏情况下，每删除一个结点需要时间O(logn)。 综上，算法shortestIntervalPaths用平衡搜索树的实现方案，在最坏情况下的计算时间复杂性为O(nlogn)。,22,实现方案2,采用并查集结构。用整数k表示区间I(k),1kn。初始时每个元素k构成一个单元素集，即集合k是k，1kn。 (1)每个当前有效区间I(k)在集合k中。 (2)对每个集合S(i)，设 L(S(i)=I(k)|I(k)是S(i)的无效区间，且I(k)与S(i)的任一有效区间均不相交 , L(S(i)中所有区间均位于S(i)的所有有

15、效区间并的右侧。 (3)用一个栈AS存放当前有效区间I(i(1)，I(i(2)，I(i(k)。I(i(k)是栈顶元素。该栈称为当前有效区间栈。 (4)对于1kn，记prev(I(k)=minj|a(k)b(j)。对给定的区间序列做一次线性扫描确定prev(I(k)的值。 (5)对于当前区间集S(i)，用一维数组dist记录dist(j,i)的值。 (6)用distk=-1标记区间I(k)为无效区间。,在最坏情况下，算法需要 计算时间, 其中 是单变量Ackerman函数的逆函数,23,优化搜索策略,24,最短加法链问题,给定一个正整数和一个实数，如何用最少的乘法次数计算出xn。例如，可以用6次

16、乘法逐步计算x23如下：x,x2,x3,x5,x10,x20,x23 可以证明计算最少需要6次乘法。计算的幂序列中各幂次1，2，3，5，10，20，23组成了一个关于整数23的加法链。在一般情况下，计算xn的幂序列中各幂次组成正整数的一个加法链 上述最优求幂问题相应于正整数的最短加法链问题，即求n的一个加法链使其长度达到最小。正整数的最短加法链长度记为l(n)。,25,回溯法,问题的状态空间树如图所示。其中第i层结点ai的儿子结点ai+1ai由aj+ak, kji所构成。,private static void backtrack(int step) / 解最短加法链问题的标准回溯法 int

17、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) ,由于加法链问题的状态空间树的每一个第k层结点至少有k+1个儿子结点，因此从根结点到第k层的任一结点的路径数至少是k!。用标准的回溯法只能对较小的构造出最短加法链。,26,迭代搜索法,深度优先搜索: 算法所搜索到的第一个加法链不一定是最短加法链。 广度优先搜索: 算法找到的第一个加法链就是最短加法链，但这种方法的空间开销太大。 迭代搜索算法: 既能保证算法找到的第一个加法链就是最

18、短加法链，又不需要太大的空间开销。其基本思想是控制回溯法的搜索深度d，从d=1开始搜索，每次搜索后使d增1，加深搜索深度，直到找到一条加法链为止。,private static void iterativeDeepening() / 逐步深化的迭代搜索算法 best=n+1; found=false; lb=2; / 初始迭代搜索深度 while (!found) a1=1; backtrack(1); lb+; / 加深搜索深度 ,对于正整数，记(n)=logn，v(n)=n的2进制表示中1的个数。迄今为止所知道的l(n)的最好下界是l(n)lb(n)= (n)+logv(n)。利用这个下界

19、，可以从深度lb(n)开始搜索，大大加快了算法的搜索进程。,27,剪枝函数,设ai和aj是加法链中的两个元素，且ai2maj。由于加倍是加法链中元素增大的最快的方式，即ai2ai-1，所以从aj到ai至少需要m+1步。如果预期在状态空间树T的第d层找到关于n的一条加法链，则以状态空间树第i层结点ai为根的子树中，可在第d层找到一条加法链的必要条件是2d-iain。 当 时，状态空间树中以结点ai为根的子树中不可能在第d层之前找到最短加法链。 设在求正整数n的最短加法链的逐步深化迭代搜索算法中，当前搜索深度为d。且正整数可表示为n=2t(2k+1)，k0，则在状态空间树的第i层结点ai处的一个剪

20、枝条件是,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)开始搜索。,