第三讲-贪心法专题讲座.ppt

例3.1 已知n=3, M=20, p=(25, 24, 15), w=(18, 15, 10), 其中的四个可行解 例3.2 已知n=4, p=(100, 10, 15, 20), d=(2, 1, 2, 1), 其中的九个可行解： 算法与时间复杂度 FastGreedyJobScheduling(int *d, float *p, int *J, int n) { int k=min {n, max {d[i]}}, F[k+1]; ElemType set[k+1]; for (i=0; i=k; i++) {F[i]=i; set [i]. data=i; set [i]. tag=-1;} for (j=0; i=1; i=n; i++) { r = find ( min (n, d[i-1]) ); if (F[r]!=0){ J[j++]=i; m=find(F[r]-1); union (m, r); F[r]=F[m]; } } } 该算法的计算时间为O(nα(2n,n))≈O(n) 3.5 最优归并模式 已知两个已分类文件: (F1, L1), (F2, L2), 归并的时间复杂度为O(L1+L2). 确定将n个长度不同的已分类文件归并在一起的最优方法(时间复杂度最低). 60 F2+ F3+F1 90 30 F2+ F3 方案3 60 F1+ F3+F2 100 40 F1+ F3 方案2 60 F1+ F2+F3 110 50 F1+ F2 方案1 10 20 30 总次数 记录移 动次数 F3 F2 F1 文件 对于不同的归并方案, 其总的记录移动次数不同. 两两归并时, 每次都选择长度最短的两个文件, 以使文件移动总次数增量最小 struct NODE { unsigned char *file; unsigned int length; unsigned tag; struct NODE *parent1; struct NODE *parent2; } L[2n-1]; 数据结构 file= length= tag=0 parent1=NULL parent2=NULL 元素初值 * 算法设计与分析 第三讲 贪心法 算法设计与分析 第三讲 贪心法 目的 了解最优化基本概念； 掌握贪心法基本思想； 掌握贪心算法的设计方法。 重点 贪心算法的设计方法； 典型问题的贪心算法实例。 难点 确定贪心选择标准，正确性证明。 3.1 最优化（optimization） max(min) f(x), s.t. gi(x)≤0|1≤i≤m x : 目标变量, objective varible; f : 目标函数, objective function; gi : 约束条件, constrained condition; 可行解: feasible solution, 满足m个约束条件的x; 最优解: optimal solution, 满足约束条件的, 且使函数f(x)最大(最小)化的变量x. 一、最优化问题 例：某工厂生产A、B、C、D四种产品，生产单位数量的产品所消耗的工时和产值分别为 设四种产品的年产量分别为x1, x2, x3, x4, 此问题的数学模型可表示为: 要求全厂年产值在1000万元以上，且使消耗的总工时最少的生产方案。 二、最优化方法 穷举法：exhausted enumeration; 　数学规划：线性规划，非线性规划，整数规划； 　分级处理：贪心法，动态规划； 　确定性有哪些信誉好的足球投注网站：回溯法，分支限界法； 不确定性有哪些信誉好的足球投注网站：蒙特卡罗，随机逼近； 　现代启发式有哪些信誉好的足球投注网站：模拟退火，进化算法，粒子群算法。 3.2 贪心法 一、 适用的问题 有n个输入, 可行解是这n个输入中满足一定约束条件的子集 可分级求解，具有最优子结构性质 二、贪心法基本策略 分析问题性质，确定适当的贪心选择标准； 按贪心选择标准对n个输入进行排序，初始化部分解； 按序每次输入一个量，如果这个输入和当前已构成在这种选择标准下的部分解加在一起不能产生一个可行解，则此输入不能加入到部分解中，否则形成新的部分解； 继续处理下一输入，直至n个输入处理完毕，最终的部分解即为此问题的最优解。 三、贪心法抽象控制描述 SOLUTION Greedy (a, n) { SOLUTION S=Ф; for (i=0; i