文档介绍：该【《算法设计与分析》第5章贪心法课件 】是由【yuzonghong1】上传分享，文档一共【96】页，该文档可以免费在线阅读，需要了解更多关于【《算法设计与分析》第5章贪心法课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第2部分算法设计策略
2022/12/1
1
第5章贪心法
*
2
成都学院计算机系
Date
3
成都学院计算机系
讨论
找零问题:用当地面额为d1>d2>……>dn的最少数量的硬币找出金额为n的零钱。
例如我国d1=1元,d2=5角,d3=2角,d5=1角,d5=5分,d6=2分,d7=1分,。
答案:1个1元,1个5角,1个5分,1个2分,1个1分
Date
5
成都学院计算机系
若硬币面值改为:一角一分、五分和一分,而要找给顾客一角五分钱。
用贪心算法将找给1个一角一分和4个一分的硬币。然而,3个五分硬币是最好的找法。
此时,贪心算法没有得到整体最优解。但通常可得到最优解的很好近似。
Date
6
成都学院计算机系
*
7
成都学院计算机系
问题有n个输入,问题的解是由这n个输入的某个子集组成,这个子集必须满足某些事先给定的条件。
约束条件:子集必须满足的条件;
可行解:满足约束条件的子集;可行解可能不唯一;
目标函数:用来衡量可行解优劣的标准,一般以函数的形式给出;
最优解:能够使目标函数取极值(极大或极小)的可行解。
分类:根据描述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同,可分为:线性规划、整数规划、非线性规划、动态规划等。
贪心方法:一种改进的分级的处理方法,可对满足上述特征的某些问题方便地求解。
Date
8
成都学院计算机系
一般来讲,如果一个问题可以用贪心法求解,则问题的解可表示成:
(x0,x1,……,xn-1)
其中每个分量xi取自某个值集S,所有允许的n元组组成一个候选解集。
Date
10
成都学院计算机系
贪心法是通过分步决策(stepwisedecision)的方法来求解问题的。
贪心法每一步上用作决策依据的选择准则被称为最优量度标准(optimizationcriterion)或贪心准则,也称贪心选择性质等。
在根据最优量度标准选择分量的过程中,还需要使用一个可行解判定函数。
贪心策略并不是从整体上加以考虑的,它所做出的选择只是当前看似最佳选择,必须进一步证明该算法最终导致问题的一个整体最优解。
Date
12
成都学院计算机系
贪心算法的一般框架
GreedyAlgorithm(parameters)
{
初始化;
重复执行以下的操作:
选择当前可以选择的最优解;
将所选择的当前解加入到问题的解中去;
直至满足问题求解的结束条件。
}
Date
14
成都学院计算机系