算法设计与分析_第4章_贪心算法1.pdf

算法设计与分析 第4章贪心算法 (1) 1 学习要点  理解贪心算法的概念  掌握贪心算法的基本要素 （1 ）最优子结构性质 （2 ）贪心选择性质  理解贪心算法不动态规划算法的差异  理解贪心算法的一般理论 2 学习要点  通过应用范例学习贪心设计策略 （1 ）活动安排问题； （2 ）最优装载问题； （3 ）哈夫曼编码； （4 ）单源最短路徂； （5 ）最小生成树； 3 引言  Similar to dynamic programming. Used for optimization problems.  Optimization problems typically go through a sequence of steps, with a set of choices at each step.  For many optimization problems, using dynamic programming to determine the best choices is overkill (过度的杀伤威力).  贪心算法: Simpler, more efficient 4 4 引言  应用  找钱  四种硬币：1分，5分，1角，2角5分  找六角3分，怎么给？  排队时出现拥挤情况，如何做才能节省用户 时间？ 5 引言  研究  朱为鹏,高成英,罗笑南.全局各向异性四边形主导网 格重建方法.软件学报,2012,23(5):1305-1314  叶齐祥,焦建彬,蒋树强.基于多尺度方向特征的快速 鲁棒人体检测算法.软件学报,2011,22(12):3004-3014  程卫芳,廖湘科,沈昌祥.有向传感器网络最大覆盖调 度算法.软件学报,2009,20(4):975-984  刘勇,高宏,李建中.基于联合意义度量的Top-K图模 式挖掘.计算机学报,2010,2期:215-230  张海英,温玄,张田文.低信噪比多目标检测的贪心算 法. 计算机学报,2008,1期:142-150  崔鹏,刘红静.测试集问题的集合覆盖贪心算法的深 入近似.软件学报,2006,17(7):1494-1500 6 引言-实例  0-1背包问题  n 个物品, 物品i 价值vi ，重wi  背包的最大负载量为W ，如何选取物品，使 得背包装的物品价值最大  每个物品是一个整体，丌能分割，因此，要 么选取该物品，要么丌选取  (分数)背包问题  Like the 0-1 knapsack problem, 但是可以取 走物品的一部分. 7 引言-实例  实例