《算法设计技巧论述》由会员分享，可在线阅读，更多相关《算法设计技巧论述（28页珍藏版）》请在金锄头文库上搜索。
1、算法设计技巧论述摘要：本文对几种经典算法设计技巧进行了分析和论述。包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法，系统的介绍了他们的原理、特 点和算法设计的步骤，并对每一种算法进行了举例分析，对算法设计的发展趋势 进行了展望。关键词：贪婪算法；分治算法；动态规划；随机化算法；回溯算法1刖曰随着科学技术的不断发展，算法设计变得越来越复杂，算法设计的研究受到 人们越来越多的重视。特别是计算机技术的广泛应用，更促进了算法设计相关理 论的研究与发展。2贪婪算法2.1基本概念概念：贪婪算法（又称贪心算法）是指，在对问题求解时，总是做出在当 前看来是最好的选择。也就是说，不从整体最优上加以考虑，
2、他所做出的仅是在 某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对 范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。2.2算法思想及算法实现步?2.2.1算法思想从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好 的解。当达到某算法中的某一步不能再继续前进时，算法停止。2.2.2实现该算法的步骤：1、从问题的某一初始解出发；2、while能朝给定总目标前进一步do3、求出可行解的一个解元素；4、由所有解元素组合成问题的一个可行解;2.3贪婪算法的基本要素对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到 问题的最优解呢?这
3、个问题很难给予肯定的回答。但是，从许多可以用贪心算法 求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结 构性质。2.3.1贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的 选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法 与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解决子问题， 而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择， 每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题， 要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题 的整体最优解。2.
4、3.2最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性 质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特 征。2.4贪婪算法的不足及优势2.4.1贪婪算法的不足：1、不能保证求得的最后解是最佳的；2、不能用来求最大或最小解问题；3、只能求满足某些约束条件的可行解的范围。2.4.2贪婪算法的优势贪婪算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选 择，也不依赖于子问题的解，因此贪婪算法与其他算法相比具有一定的速度优势。 如果一个问题可以同时用几种方法解决，贪婪算法应该是最好的选择之一。2.5例题分析2.5.1背包问题题目要求：有
5、一个背包，背包容量是M=150.有7个物品，物品可以分割成 任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品 A B C D E F G重量 35 30 60 50 40 10 25价值 10 40 30 50 35 40 30算法分析：目标函数：pi最大约束条件是装入的物品总重量不超过背包容量，既，讷=M(M=150)1、根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否 最优？2、每次选取挑选所占重量最小的物品装入是否能得到最优解？3、每次选取单位重量价值最大的物品，成为解决本题的策略。贪心算法是很常见的算法之一，这是由于它简单易行，构造贪心策略简单。
6、但是，它需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明 围绕着整个问题的最优解一定是由在贪心策略中存在的子问题的最优解得来的。对于本例题中的3种贪心策略，都无法成立，即无法被证明，解释如下：1、贪心策略：选取价值最大者。反例：W=30物品A B C重量28 12 12价值30 20 20根据策略，首先选取物品A，接下来就无法选取了，可是，选取B、C则更 好。2、贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。3、贪心策略：选取单位重量价值最大的物品。反例：W=30物品：A B C重量：28 20 10价值：28 20 10根据策略，三种物品单位重量价值一样，程序无法依
7、据现有策略作出判断， 如果选择A，则答案错误。值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成 立后，它就是一种高效的算法。比如，求最小生成树的Prim算法和Krushal算 法都是漂亮的贪心算法。2.5.2均分纸牌问题题目要求：有N对纸牌，编号分别为1,2, .，n。每堆上有若干张，但 纸牌总数必为n的倍数，可以在任一堆上取若干张纸牌，然后移动。纸牌的规则 为：在编号为1上取纸牌，只能移动到编号为2的堆上；在编号为n的堆上取得 纸牌，只能移动到编号为n-1的堆上；其他堆上取得纸牌，可以移动到相邻左边或 右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都
8、一样多。例如：n=4,4堆纸牌分别为：98176移动三次可以达 到目的：从取4张牌放到，再从取三张放到，取一张放到。算法分析：设ai为第I堆纸牌的张数（0=Iv，则将ai-v张从第I堆移动到第I+1堆；2、若aiv，则将v-ai张从第I+1堆移动到第I堆。为了设计的方便，我们把这两种情况统一看作是将ai-v从第I堆移动到 第I+1堆，移动后有ai=v; aI+1=aI+1+ai-v在从第I+1堆取出纸牌补 充第I堆的过程中可能回出现第I+1堆的纸牌小于零的情况。贪婪算法均分纸牌流程图如n=3,三堆指派数为1 2 27，这时v=10,为了使第一堆为10,要从第二 堆移9张到第一堆，而第二堆只有2
9、张可以移，这是不是意味着刚才使用贪心法 是错误的呢?我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有 10张，第二堆剩下-7张，在从第三堆移动17张到第二堆，刚好三堆纸牌都是 10，最后结果是对的，我们在移动过程中，只是改变了移动的顺序，而移动次数 不便，因此此题使用贪心法可行的。3分治算法3.1基本概念概念：分治算法是指把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题即子问题的合并。3.2算法思想及算法实现步骤3.2.1分治算法的基本思想分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问 题，
10、这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问 题的解。3.2.2分治法解题的一般步骤分治法解题的一般步骤：1、分解，将要解决的问题划分成若干规模较小的同类问题；2、求解，当子问题划分得足够小时，用较简单的方法解决；3、合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。3.2.3算法设计模式它的一般的算法设计模式如下：Divide-and-conquer(P)1、if |P*02、then return(ADHOc(P)3、将P分解为较小的子问题P1 ,P2 ,.,Pk4、for i 1 to k5、do yi Divide-and-conquer(Pi) 递归解决
11、 Pi6、T - MERGE(y1,y2,.,yk) 合并子问题7、return(T)其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0 时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算 法，用于直接解小规模的问题P。因此，当P的规模不超过n0时，直接用算法 ADHOc(P)求解。算法MERGE(y1,y2,.,yk)是该分治法中的合并子算法，用于将 P的子问题P1 ,P2 ,.,Pk的相应的解y1,y2,.,yk合并为P的解。3.3分治算法的分治策略及复杂性分析3.3.1分治算法的分治策略当我们求解某些问题时，由于这些问题要处理的数据相当多，
12、或求解过程 相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类 问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再 找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难 以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解 为止。这就是分治策略的基本思想。根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问 题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践 中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将 一个问题分成大小相等的k个子问题的处理方法是行之有效的。
13、许多问题可以取 k=2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思 想，它几乎总是比子问题规模不等的做法要好。分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些 问题合并方法比较复杂，或者是有多种合并方案，或者是合并方案不明显，究竟 应该怎样合并，没有统一的模式，需要具体问题具体分析。3.3.2分治算法的复杂性分析从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过 程。因此，分治法的计算效率通常可以用递归方程来进行分析。为方便起见，设 分解阈值n0=1，且算法ADHOC解规模为1的问题耗费1个单位时间。又设分治 法将规模为n的问题
14、分成k个规模为n/m的子问题去解，而且，将原问题分解为 k个子问题以及用算法MERGE将k个子问题的解合并为原问题的解需用f(n)个单 位时间。如果用T(n)表示该分治法Divide-and-conquer(P)解规模为|P|=n的问 题P所需的计算时间，则有：1、T(1) = 1 T(n) = kT(n/m) + f(n)用算法的复杂性中递归方程解的渐进阶的解法介绍的解递归方程的迭代法， 可以求得(1)的解：logm(n-1)2、T(n) = n(logmK) + E (kj)*f(n/(mj) j=0注意，递归方程及其解只给出n等于m的方幕时T(n)的值，但是如 果认为T(n)足够平滑，那
15、么由等于m的方幕时T(n)的值可以估计T(n)的增长速 度。通常，我们可以假定T(n)是单调上升的，从而当minn0由于我们关心的一般是最坏情况下的计算时间复杂度的上界，所以用等于号 （=）还是小于或等于号（忍）是没有本质区别的分治法的几种变形。3.4例题分析3.4.1找出伪币题目要求：给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的， 并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为 了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台 仪器，可以知道两组硬币的重量是否相同。解决方案一：比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币 1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。 假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些， 则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币
