第六章贪心法.ppt

第六章贪心法
第一页，共48页
第六章 贪心法
贪心法的学习提纲
一般方法
适合求解的问题
基本思想(求解问题的过程 )
算法控制流程
算法的正确性证明
应用举例
背包问题
带时限的作业排序问题
第二页，共48页
贪心算法的直观含义
：，要求硬币数最少。找硬币方法就是一种贪心算法.
（1）面值；5分、2分、1分：
（2）面值：11分、5分、1分：
从此例可以看出：
1，贪心法未必总能求得问题的最优解；
2，,它所作出的选择只是在某种意义上的局部最优选择。
虽然贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它都能产生最优解。如单源最短路径问题，最小生成树问题等。
而且,在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解！
3个5分 (最优)
1个11分4个1分 (次优)
第三页，共48页
一般方法
贪心方法适合的问题是最优化问题。
最优化问题：有n个输入，而它的解就由这n个输入的满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显然，可行解一般来说是不唯一的，为了衡量可行解的好坏，问题还给出某个值函数，称为目标函数，使目标函数取极值(极大或极小)的可行解，称为最优解。
目标函数：
约束条件（函数）：
其中：
可行解：
如找硬币问题可描述如下：
最优化问题的解可表示成一个n元组X=（x1,x2…xn），其中每个分量取自某个值集S，所有允许的n-元组组成一个侯选解集。
第四页，共48页
一般方法
贪心方法适合的问题是最优化问题。
最优化问题：有n个输入，而它的解就由这n个输入的满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显然，可行解一般来说是不唯一的，为了衡量可行解的好坏，问题还给出某个值函数，称为目标函数，使目标函数取极值(极大或极小)的可行解，称为最优解。
最优化问题的解是一个n元组
贪心法是通过分步决策的方法来解决问题的。贪心法在求解问题的每一步上作出某种决策，产生n-元组的一个分量，贪心法要求根据题意，选定一种最优量度标准，作为选择当前分量的依据，这种在贪心法每一步上用做决策依据的选择准则被称为最优量度标准（贪心准则，也称贪心选择性质）。
第五页，共48页
一般方法
贪心法的基本思想:
是依据题意选取一种量度标准，然后按照这种量度标准对这n个输入进行排序，并按序一次输入一个量，作为n-元组的一个分量，如果这个输入量的加入不满足约束条件,则不把此输入加入到部分解向量中.
贪心法求解问题的过程:
选取最优量度标准
依最优量度标准对n个输入排序
初始状态下,解向量solution=φ中;
按序一次取一个输入量，作为n-元组的一个分量，若加入该分量满足给定的约束条件，则加入，否则，不加入，继续检测下一个分量.
第六页，共48页
贪心方法的抽象化控制
贪心法的控制流程
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;
}
，一旦能选择出某个问题的最优量度标准，那么用贪心方法求解这个问题则特别简单有效。
第七页，共48页
n个输入按某种量度标准排序
……
按序一次选择一个输入量。
满足约束条件，加入解
解
不满足约束条件，扬弃
…..
对于一个给定的问题，往往可能有好几种量度标准。用其中的大多数量度标准作贪心处理所得到该量度意义下的最优解并不是问题的最优解，而是次优。
选择能产生问题最优解的最优量度标准是使用贪心法设计求解的核心问题。
第八页，共48页
一般方法
贪心法小结:
适合求解的问题:解为n-元组的最优化问题;
贪心法是分步决策,每一步决策产