数据结构-第五部分.ppt

第15章 算法设计技术 枚举法 贪婪法 分而治之法 动态规划 回溯法 随机算法 枚举法 枚举法适合于解的候选者是有限、可枚举的场合。 枚举法就是对可能是解的众多候选者按某种顺序进行逐一枚举和检验，从中找出符合要求的候选解作为问题的解。 基于枚举法的算法一般都比较直观，容易理解。但由于要检查所有的候选解，因此时间性能较差 枚举法实例 用50元钱买了三种水果：西瓜、苹果和桔子。各种水果加起来一共100个。假如，西瓜5元一个，苹果1元一个，桔子1元3个，设计一算法输出每种水果各买了几个。 约束条件 三种水果一共100个； 买三种水果一共花了50元。 如果西瓜有mellon个，苹果有apple个，桔子有orange个，那么： mellon + apple + orange 等于100 5 * mellon + 1 * apple + orange /3等于50。 直观的枚举 For (mellon = 1, mellon 99; ++ mellon) For (apple = 1, apple 99; ++apple) For (orange = 1; orange 99; orange) If （mellon + apple + orange 等于100 并且 5 * mellon + 1 * apple + orange /3等于50） 输出此方案； 改进的方案 int main() { int mellon, apple, orange; for (mellon=1; mellon10; ++mellon) for ( apple=1; apple 50 - 5 * mellon; ++apple) { orange = 3*(50-5*mellon-apple); if (mellon+apple+orange == 100){ cout mellon: mellon ; cout apple: apple ; cout orange: orange endl; } } return 0; } 执行结果 Mellon：1 apple：18 orange：81 Mellon：2 apple：11 orange：87 Mellon：3 apple：4 orange：93 第15章 算法设计技术 枚举法 贪婪法 分而治之法 动态规划 回溯法 随机算法 贪婪法 贪婪法适合于分阶段完成的工作。在每一阶段都选择当前最好的答案，而不管将来如何。 Dijkstra算法，prim算法和Kruskal算法都是贪婪算法 贪婪法不一定能得到最优解，但是一个可行的、较好的解。 最少背包问题 假设有许多盒子，每个盒子能保存的总重量为1.0。有N个项i1,i2,…,iN，它们的重量分别是w1,w2,…,wN。目的是用尽可能少的盒子放入所有的项，任何盒子的重量不能超过他的容量。 例如，如果项的重量为0.4, 0.4, 0.6和0.6，最佳的方案是用两个盒子。 但要得到最佳方案，必须尝试所有种组合情况。当n很大时，这是不可能的。 一种解决方案使用贪婪法 解决策略 按给定的次序扫描每一个项，把每一个项放入能够容纳他而不至于溢出的最满的盒子。 如果项的重量为0.4, 0.4, 0.6和0.6，贪婪法的方案是用三个盒子。其装载的重量分别为0.8,0.6,0.6 第15章 算法设计技术 枚举法 贪婪法 分而治之法 动态规划 回溯法 随机算法 分而治之法 分而治之法的思想 分：递归解决若干个较小的问题 治：从子问题的答案中形成原始问题的解 分治法的的算法至少有两个递归调用 已见过的分治法算法：快速排序，树的遍历 分治法实例 最长连续子序列问题 最近点问题 数学计算问题 最长连续子序列问题 假设输入是{4，－3，5，－2，－1，2，6，－2}。我们把这个输入划分成两部分，前四个和后四个。这样最大连续子序列的和可能出现在下面三种情况中。 情况1：整个位于前半部，可递归计算。 情况2：整个位于后半部，可递归计算。 情况3：从前半部开始但在后半部结束。 情况3的解决方法 从两半部分的边界开始，通过从右到左的扫描来找到左半段的最长序列。类似地，从左到右的扫描找到右半段的最长序列。把这两个子序列组合起来，形成跨越分割边界的最大连续子序列。 在这个实例中，结果序列是从第一部分的第一个元素到第二部分的其余元素。总和是两个子