贪心算法设计优化-PerfectFuture.PPT

?教学要求 了解贪心算法的概念与贪心策略的选择 掌握应用贪心算法设计求解删数字问题、可拆背包问题与数列操作问题等最优化典型案例 ?本章重点 根据案例的实际选择与确定贪心策略 7.1 贪心算法概述 7.1.1 贪心算法的概念 (1) 贪心算法又称贪婪算法，是一种着眼局部的简单而适应范围有限的优化策略。 (2) 当一个问题具有最优子结构性质时，贪心算法有时比动态规划法求解更为简单有效。 (3) 贪心算法在求解最优化问题时，从初始阶段开始，每一个阶段总是做一个使局部最优的贪心选择，不断把将问题转化为规模更小的子问题。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是局部最优选择。这样处理，对大多数优化问题来说能得到最优解，但也并不总是这样。 （4）贪心策略的选择 贪心算法没有固定的算法框架，算法设计的关键在于贪心策略的选择与确定。 贪心算法的基本思想是通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。 应用贪心算法所做的每一步选择都必须满足： 1）可行的：必须满足问题的约束条件。 2）局部最优：当前所有可能的选择中选择使局部最优的决策。 3）不可取消：选择一旦做出，在后面的步骤中无法改变。 贪心算法是通过做一系列的选择来求出某一问题的最优解，对算法的每一个决策点，做一个当时（看起来）是最佳的选择，这种启发式策略并不总能产生出最优解。 7.1.2 贪心算法的理论基础 第7章 作业 习题7: 1, 2, 3, 4 第7章上机 （1） 上机通过本章删数字、埃及分数式、可拆背包与数列操作问题等典型案例； （2） 上机通过习题7-5,7-6； （3） 分组讨论：数列操作优化及其时间复杂度；哈夫曼树与哈夫曼编码实现。 * * * * 第 7 章 贪心算法 贪心算法的理论基础为拟阵，是组合优化与图论的重要内容。 　矩阵胚（matroid）又称为拟阵，是一个满足以下交换性质的特殊子集系统： 　判断一个子集系统是不是矩阵胚常应用以下性质： 定理1 一个子集系统是矩阵胚当且仅当所有极大独立子集具有相同的基数。 例如,若S是一个矩阵中行向量集合，I是S的线性独立子集族，则（S,I）是矩阵胚。 定理2 子集系统优化问题的贪心算法正确，当且仅当该子集系统是一个矩阵胚。 7.2 背包问题 7.2.1 可拆背包问题 // 已对n件物品按单位重量的效益降序排序 cw=c;s=0; // cw为背包还可装的重量 for(i=1;i=n;i++) {if(w[i]cw) break; x[i]=1.0; // 若w(i)=cw,整体装入 cw=cw?w[i]; s=s+p[i]; } x[i]=(float)(cw/w[i]); // 若w(i)cw,装入一部分) s=s+p[i]*x[i]; 3. 贪心算法描述 7.3 删数字问题 案例提出： 在给定的n个数字的数字串中，删除其中k(kn)个数字后，剩下的数字按原次序组成一个新的正整数。请确定删除方案，使得剩下的数字组成的新正整数最大。 例如在整数79502867154829179316中删除8个数字后，所得最大整数为多大？ 操作对象是一个可以超过有效数字位数的n位高精度数，存储在数组a中。 在整数的位数固定的前提下，让高位的数字尽量大，整数的值就大。这就是所要选取的贪心策略。 每次删除一个数字，选择一个使剩下的数最大的数字作为删除对象。选择这样“贪心”操作，是因为删k个数字的全局最优解包含了删一个数字的子问题的最优解。 当k=1时，在n位整数中删除哪一个数字能达到最大？从左到右每相邻的两个数字比较：若出现增，即左边数字小于右边数字，则删除左边的小数字。若不出现增，即所有数字全部降序或相等，则删除最右边的小数字。 1. 贪心算法设计要点 例如，在18位整数762191754639820463中，删除1个数字，使剩下的17位数最大，如何删？ 要使删除1个数字后的17位数最大，须首位数字最大。首先，首位数字“7”大于第2位数字“6”比较，首位数字“7”不能删！ 往后推，“6”与“2”比较，因62，为减，“6”不能删； 再往后推，“2”与“1”比较，因21,为减，“2”不能删 ； 继续往后推，“1”与“9”比较，因19，出现增，则删除左边的小数字“1”。 当k1（当然小于n），按上述操作,每一次操作从串首开始，每相邻的两个数字比较，出现“增”时，删除左边的小数字。每次操作删除一个数字后，后面的数字向前移位。 因此，只要从