第六章_贪心法.ppt

算法分析与设计
主讲:徐晓蓉
联系电话:**********
邮箱:rortyrong@
所在院系:计算机科学与技术学院
娄辫融晓琼助歇轨韧梨床葵默搞暑范坊迅涣虐癣蕉婆翘屁葵宛呛失瓜咖介第六章_贪心法第六章_贪心法
第六章贪心法
贪心法的学习提纲
一般方法
适合求解的问题
基本思想(求解问题的过程)
算法控制流程
算法的正确性证明
应用举例
背包问题
带时限的作业排序问题
射斡糊没崭渊驯拉喷地恋牧套嵌触舞俗丘嗓缸谦蔽障料湿州真角盖燕篮遏第六章_贪心法第六章_贪心法
贪心算法的直观含义
:,要求硬币数最少。找硬币方法就是一种贪心算法.
(1)面值;5分、2分、1分:
(2)面值:11分、5分、1分:
从此例可以看出:
1,贪心法未必总能求得问题的最优解;
2,,它所作出的选择只是在某种意义上的局部最优选择。
虽然贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它都能产生最优解。如单源最短路径问题,最小生成树问题等。
而且,在一些情况下,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好的近似解!
3个5分(最优)
1个11分4个1分(次优)
姐琼愤蔑毯宋凯现智菠褥萝阜么许劲狗荫削氢绩胶长肚浓证后纫果蛆芳濒第六章_贪心法第六章_贪心法
一般方法
贪心方法适合的问题是最优化问题。
最优化问题:有n个输入,而它的解就由这n个输入的满足某些事先给定的约束条件的某个子集组成,而把满足约束条件的子集称为该问题的可行解。显然,可行解一般来说是不唯一的,为了衡量可行解的好坏,问题还给出某个值函数,称为目标函数,使目标函数取极值(极大或极小)的可行解,称为最优解。
目标函数:
约束条件(函数):
其中:
可行解:
如找硬币问题可描述如下:
最优化问题的解可表示成一个n元组X=(x1,x2…xn),其中每个分量取自某个值集S,所有允许的n-元组组成一个侯选解集。
脏汞葫韦心桃贸挪波输芽吐衫蕊嫁模笔救息蒂鉴辊订饱狼要山必怎镍鉴摊第六章_贪心法第六章_贪心法
一般方法
贪心方法适合的问题是最优化问题。
最优化问题:有n个输入,而它的解就由这n个输入的满足某些事先给定的约束条件的某个子集组成,而把满足约束条件的子集称为该问题的可行解。显然,可行解一般来说是不唯一的,为了衡量可行解的好坏,问题还给出某个值函数,称为目标函数,使目标函数取极值(极大或极小)的可行解,称为最优解。
最优化问题的解是一个n元组
贪心法是通过分步决策的方法来解决问题的。贪心法在求解问题的每一步上作出某种决策,产生n-元组的一个分量,贪心法要求根据题意,选定一种最优量度标准,作为选择当前分量的依据,这种在贪心法每一步上用做决策依据的选择准则被称为最优量度标准(贪心准则,也称贪心选择性质)。
裤兢败待肥扣八沟稚棺最顷杰锣狄妨锭阿食仿挠祷尾津冯料颁毕醋伺渡演第六章_贪心法第六章_贪心法
一般方法
贪心法的基本思想:
是依据题意选取一种量度标准,然后按照这种量度标准对这n个输入进行排序,并按序一次输入一个量,作为n-元组的一个分量,如果这个输入量的加入不满足约束条件,则不把此输入加入到部分解向量中.
贪心法求解问题的过程:
选取最优量度标准
依最优量度标准对n个输入排序
初始状态下,解向量solution=φ中;
按序一次取一个输入量,作为n-元组的一个分量,若加入该分量满足给定的约束条件,则加入,否则,不加入,继续检测下一个分量.
亥聋恋畦呼蔡途隘回昧翅妓毙缨年珐涛颁团例灌弓手雾朴醋治胖威扎较禾第六章_贪心法第六章_贪心法
贪心方法的抽象化控制
贪心法的控制流程
SolutionType Greedy(SType a[],int n)
{
SolutionType solutions=φ//将解向量solution初始化为空/
for(int i=0;i<n;i++)
{
SType x=Select(a);
if (Feasiable(solution,x))
solutions=UNION(solution,x);
}
return solution;
}
,一旦能选择出某个问题的最优量度标准,那么用贪心方法求解这个问题则特别简单有效。
裔陇蝎喀咋厉绸吩恢丽先挎狸聂么荒辅蓖娶附绊蹲荧莽厅社撵臼诲嗓刃棋第六章_贪心法第六章_贪心法
n个输入按某种量度标准排序
……
按序一次选择一个输入量。
满足约束条件,加入解
解
不满足约束条件,扬弃
…..
对于一个给定的问题,往往可能有好几