算法设计与分析-贪心算法.pdf

算法设计与分析 Design and Analysis of Algorithms 1 算法设计与分析 第 7 章 贪心法 主要内容 l 贪心算法的设计技术 l 用贪心法求问题的解 l 近似贪心问题 难点 Ø 正确性证明 HIT ● Research Center of Intelligent Computing 理解|区分|命名|表达 for Enterprise Service 2 2021/5/28 算法设计与分析 第 7 章 贪心法 主要内容 l 贪心算法的设计思想与技术 l 用贪心法求问题的解 l 近似贪心问题 HIT ● Research Center of Intelligent Computing 理解|区分|命名|表达 for Enterprise Service 3 2021/5/28 算法设计与分析 ==贪心算法的设计思想与技术== 贪婪，我找不到一个更好的词来描述它，它就是好！它就是好！它 贪婪，我找不到一个更好的词来描述它，它就是好！它就是好！它 就是有效！ 就是有效！ --美国演员迈克尔·道格拉斯， 影片《华尔街》中的台词 max{100,50,20,10, 5, 1}38 max{100,50,20,10, 5, 1}18 max{100,50,20,10, 5, 1}8 吃辣条， 学算法 max{100,50,20,10, 5, 1}3 Ø贪心算法设计技术：求最短哈密顿回路的问题 • 每一步的判断都是一个当前最优的抉择，这个抉择计算设 计的好坏，决定了算法的成败 • 多步判断过程，最终的判断序列对应于问题的最优解 • 适用于能够由局部最优达到全局最优的优化问题 局部最优达到全局最优 • 需要对具体的贪心算法的正确性进行必要的证明 HIT ● Research Center of Intelligent Computing 理解|区分|命名|表达 for Enterprise Service 4 算法设计与分析 第 7 章 贪心法 主要内容 l 贪心算法的设计思想与技术 l 用贪心法求问题的解 l 近似贪心问题 HIT ● Research Center of Intelligent Computing 理解|区分|命名|表达 for Enterprise Service 5 2021/5/28