《数据结构算法综述》由会员分享，可在线阅读，更多相关《数据结构算法综述（26页珍藏版）》请在金锄头文库上搜索。
1、算法设计技巧论述摘要：本文对几种经典算法设计进行了分析和论述。主要介绍了贪婪算法、分治算法、动态规划、随机化算法以及回溯算法，详细介绍了他们的原理、特点和算法设计的步骤，并用例子、流程图等来直观表达它们的运作方式，最后做了一下对算法的总结以及对算法设计在未来的展望。关键词：贪婪算法；分治算法；动态规划；随机化算法；回溯算法；展望Abstract:This paperanalyzes and discussesseveralof the classic algorithmdesign.Mainly introduces thegreedy algorithms,divide and conque
2、r algorithm,dynamic programming,the randomizedalgorithm andbacktracking algorithm,introducedtheirprinciple,characteristics and algorithmsdesign steps,and use examples,such as flow charttodirectly expresstheirmode of operation,finally madeasummaryon thealgorithmandthe algorithm design inthe futureto.
3、Keywords:greedy algorithm;partition algorithm;dynamic programming;randomized algorithm;backtracking algorithm;Prospect 前言随着计算机的发展,软件的强大与否越来越重要。特别是计算机技术的广泛应用，更促进了算法设计相关理论的研究与发展。其中算法是计算机学科中最具有方法论性质的核心概念，被誉为计算机学科的灵魂。算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的
4、指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。算法的基本特征包括又穷性，确定性，可行性。本文只是稍稍介绍一下相关的算法流程原理，望大家共勉。1、 贪婪算法1、 基本概念贪婪算法（又称贪心算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。最优化问题是指每个最优化问题都包含一组限制条件和一个优化函数，符合限制条件的问题求解方案称为可行解，使优化函数取得最佳值的可行解称为
5、最优解。2、 具体实现 贪婪算法的关键：每步贪婪；不回溯；选择的规则非常重要，不正确的规则可能得不到结果、不优化或者不能作为贪婪的求解对象；必定有解，但是可能不会得到最优解。可以从下面四个步骤解决问题： （1）从问题的某一初始解出发； （2）while 能朝给定总目标前进一步 do （3）求出可行解的一个解元素； （4）由所有解元素组合成问题的一个可行解； 贪婪算法的基本性质有两个，分别是贪心选择性质和最优子结构性质。下面分别介绍这两个性质： 1、所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法
6、的主要区别。动态规划算法通常以自底向上的方式解决子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。2、最优子结构性质是指当一个问题的最优解包含其子问题的最优解时，就称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。3、 举例例子1:找零钱 一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分
7、、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。假设需要找给小孩6 7美分，首先入选的是两枚2 5美分的硬币，第三枚入选的不能是2 5美分的硬币，否则硬币的选择将不可行（零钱总数超过6 7美分），第三枚应选择1 0美分的硬币，然后是5美分的，最后加入两个1美分的硬币。贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）。可以证明采用上述贪婪算法找零钱时所用
8、的硬币数目的确最少。例子2:纸牌问题 有N对纸牌，编号分别为1,2，.，n。每堆上有若干张，但纸牌总数必为n的倍数，可以在任一堆上取若干张纸牌，然后移动。纸牌的规则为：在编号为1上取纸牌，只能移动到编号为2的堆上；在编号为n的堆上取得纸牌，只能移动到编号为n-1的堆上；其他堆上取得纸牌，可以移动到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如：n=4,4堆纸牌分别为： 9 8 17 6 移动三次可以达到目的：从取4张牌放到 ，再从取三张放到，取一张放到。算法分析：设ai为第I堆纸牌的张数（0=Iv，则将ai-v张从第I堆移动到第I+1堆；2、若ai
9、v，则将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张到第一堆后，第一堆有10张，第二堆剩下-7张，在从第三堆移动17张到第二堆，刚好三堆纸牌都是10，最后结果是对的，我们在移
10、动过程中，只是改变了移动的顺序，而移动次数不便，因此此题使用贪心法可行的。4、 优势和不足一：贪婪算法的不足 1、 不能保证求得的最后解是最佳的； 2、 不能用来求最大或最小解问题； 3、 只能求满足某些约束条件的可行解的范围。二：贪婪算法的优势贪婪算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪婪算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪婪算法应该是最好的选择之一。2、 分治算法1、 基本概念我们为了解决一个大的问题，可以把它分成两个或多个更小的问题；分别解决每个小问题；把各小问题的解答组合起来，即可得到原问题的
11、解答。所以分治算法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。2、 具体实现基本算法思想：如果原问题可分割成k个子问题（1kn），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治算法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。分治法解题的一般步骤如下：1、分解，
12、将要解决的问题划分成若干规模较小的同类问题；2、求解，当子问题划分得足够小时，用较简单的方法解决；3、合并，按原问题的要求，将子问题的解逐层合并构成原问题的解一般的算法设计模式如下：Divide-and-conquer(P)1、 if |P|n02、 then return(ADHOc(P)3、 将P分解为较小的子问题 P1 ,P2 ,.,Pk4、 for i1 to k5、 do yi Divide-and-conquer(Pi) 递归解决Pi6、 T MERGE(y1,y2,.,yk) 合并子问题7、 return(T)其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0
13、时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时，直接用算法ADHOc(P)求解。算法MERGE(y1,y2,.,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,.,Pk的相应的解y1,y2,.,yk合并为P的解。3、 例子例子1：循环赛日程表 问题描述：设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1in，1jn-1。按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。12345671234567821436785341278561234321856712345678143212143658721431234127856321421432187654321（1）
