《算法优化策略》PPT课件.ppt

第第1010章章 算法优化策略算法优化策略1算法设计策略的比较与选择算法设计策略的比较与选择 2最大子段和问题最大子段和问题 给定由n个整数(可能为负整数)组成的序列a1,a2,an,求该序列形如 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为。依此定义，所求的最优值为:例如:A=(-2，11，-4，13，-5，-2)最大子段和为3简单算法简单算法public static int maxSum()int n=a.length-1;int sum=0;for(int i=1;i=n;i+)int thissum=0;for(int j=i;j=n;j+)for(int k=i;ksum)sum=thissum;besti=i;bestj=j;return sum;thissum+=aj;注意到 ，则可将算法中的最后一个for循环省去，避免重复计算只需要O(n2)的计算时间。4分治算法分治算法如果将所给的序列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)时的最优值。据此可设计出求最大子段和的分治算法。复杂度分析复杂度分析T(n)=O(nlogn)5动态规划算法动态规划算法记 ，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;6最大子矩阵和问题最大子矩阵和问题记 最大子矩阵和问题的最优值为由于其中，设 ，则给定一个m行n列的整数矩阵a，试求矩阵a的一个子矩阵，使其各元素之和为最大。由于解最大子段和问题的动态规划算法需要时间O(n)，故算法的双重for循环需要计算时间O(m2n)。7最大最大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 i m)。优化：注意到在上述算法中，计算bij时只用到数组b的第i-1行和第i行的值。因而算法中只要存储数组b的当前行，不必存储整个数组。另一方面，b(i-1，t)的值可以在计算第i-1行时预先计算并保存起来。计算第i行的值时不必重新计算，节省了计算时间和空间。8动态规划加速原理动态规划加速原理 四边形不等式9货物储运问题货物储运问题在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。设合并ai:j，1ijn，所需的最少费用为mi,j，则原问题的最优值为m1，n。由最优子结构性质可知，根据递归式，按通常方法可设计计算m(i,j)的O(n3)动态规划算法10四边形不等式四边形不等式货物储运问题的动态规划递归式是下面更一般的递归计算式的特殊情形。对于 ,当函数w(i,j)满足时称w满足四边形不等式。当函数w(i,j)满足 时称W关于区间包含关系单调 对于满足四边形不等式的单调函数w，可推知由递归式定义的函数m(i,j)也满足四边形不等式，即11四边形不等式四边形不等式定义由函数m(i,j)的四边形不等式性质可推出函数s(i,j)的单调性，即根据前面的讨论，当w是满足四边形不等式的单调函数时，函数s(i,j)单调，从而 s(i,j)s(i,j+1)s(i+1,j+1)，i j改进后算法speedDynamicProgramming所需的计算时间为 12问题的算法特征问题的算法特征13贪心策略贪心策略采用每次合并集装箱数最少的相邻2堆货物的贪心策略，并不能得到最优解。适当放松相邻性约束，引入相容结点对概念。如图，原始结点用方形结点表示，合并生成的结点用圆形结点表示。最小相容结点对ai和aj 是满足下面条件的结点对：（1）结点ai和aj 之间没有方形结点；（2）在所有满足条件（1）的结点中ai+aj的值最小；（3）在所有满足条件（1）和（2）的结点中下标 i 最小；（4）在所有满足条件（1）（2）和（3）的结点中下标 j 最小。相应的最小相容合并树，如图所示。14相同层序定理相同层序定理相同层序定理相同层序定理相同层序定理相同层序定理：存在货物储运问题的最优合并树，其各原始结：存在货物储运问题的最优合并树，其各原始结：存在货物储运问题的最优合并树，其各原始结：存在货物储运问题的最优合并树，其各原始结点在最优合并树中所处的层序与相应的原始结点在相容合并树点在最优合并树中所处的层序与相应的原始结点在相容合并树点在最优合并树中所处的层序与相应的原始结点在相容合并树点在最优合并树中所处的层序与相应的原始结点在相容合并树中所处的层序相同。中所处的层序相同。中所处的层序相同。中所处的层序相同。根据上述定理，容易从各原始结点在相容合并树中所处的层序构造出相应的最优合并树，如图所示。15算算 法法1.组合阶段:将给定的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)中的有效区间。18带权区间最短路问题带权区间最短路问题性质性质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(1)j(2)k），且dist(i,i)k且dist(i,i)1)不包含S(k-1)中任一有效区间I(j)的右端点b(j)，则对任意ik，I(k)是S(i)中的无效区间。19带权区间图的最短路算法带权区间图的最短路算法算法算法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(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)+)&(a(i)b(k);dist(i,n)=dist(j,n)+w(i);上述算法的关键是有效地实现步骤(2.1)和(2.2)20实现方案实现方案1 1用一棵平衡搜索树（2-3树）存储当前区间集S(i)中的有效区间。以区间的右端点的值为序。如图所示。(2.1)的实现对应于平衡搜索树从根到叶的一条路径上的搜索，在最坏情况下需要时间O(logn)。(2.2)的实现对应于反复检查并删除平衡搜索树中最右叶结点的前驱结点。在最坏情况下，每删除一个结点需要时间O(logn)。综上，算法shortestIntervalPaths用平衡搜索树的实现方案，在最坏情况下的计算时间复杂性为O(nlogn)。21实现方案实现方案2 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)的所有有效区间并的右侧。(3)用一个栈AS存放当前有效区间I(i(1)，I(i(2)，I(i(k)。I(i(k)是栈顶元素。该栈称为当前有效区间栈。(4)对于1kn，记prev(I(k)=minj|a(k)ai由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的一条加法链，则以状态空间树第i层结点ai为根的子树中，可在第d层找到一条加法链的必要条件是2d-iain。当 时，状态空间树中以结点ai为根的子树中不可能在第d层之前找到最短加法链。设在求正整数n的最短加法链的逐步深化迭代搜索算法中，当前搜索深度为d。且正整数可表示为n=2t(2k+1)，k0，则在状态空间树的第i层结点ai处的一个剪枝条件是27最短加法链长的上界最短加法链长的上界与加法链问题密切相关的幂树给出了l(n)的更精确的上界。假设已定义了幂树T的第k层结点，则T的第k+1层结点可定义如下。依从左到右顺序取第k层结点ak，定义其按从左到右顺序排列的儿子结点为ak+aj，0jk。其中a0,a1,ak，是从T的根到结点ak的路径。且ak+aj在T中未出现过。含正整数n的部分幂树T容易在线性时间内用迭代搜索方式构造出来。28优化算法优化算法 综合前面的讨论，对构造最短加法链的标准回溯法作如下改进。(1)采用逐步深化迭代搜索策略；(2)利用l(n)的下界lb(n)对迭代深度作精确估计；(3)采用剪枝函数对问题的状态空间树进行剪枝搜索，加速搜索进程；(4)用幂树构造l(n)的精确上界ub(n)。当lb(n)=ub(n)时，幂树给出的加法链已是最短加法链。当lb(n)ub(n)时，用改进后的逐步深化迭代搜索算法，从深度d=lb(n)开始搜索。29