第八章讲 贪心算法.ppt

第三部分最先割技术

第八章贪心算法
第九章图的遍历
本章采用知识发明的第三条线,即“方法——应用”为主线安排内容。
第八章贪心算法
引言(背包问题和钱币问题)
拟阵论
几个数据结构中学过的贪心算法
最短路径问题(Dijkstra算法)
最小耗费生成树(Kruskal算法)
最小耗费生成树(Prim算法)
文件压缩(Huffman)
几类区间覆盖问题
基因组重排(反序排序)问题
“贪心法”是解决最优化问题的一种快速算法,也是在遇到问题时我们最先会想到的方法,但是此方法又是一种不稳定的方法。
贪心法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。换言之,贪心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。
引言
贪心算法通常包含一个用以寻找局部最优解的迭代过程。在某些实例中,这些局部最优解转变成了全局最优解,而在另外一些情况下,则无法找到最优解。
Greedy Algorithms
● Algorithms for optimization problems typically go through a sequence of steps, with a set of choices at each step.
● Greedy algorithm always makes the choice that looks best at the moment.
● Greedy algorithm makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution.
对于一个具体的问题,怎么知道是否可用贪心算法解此问题,以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。
但是,从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质:贪心选择性质和最优子结构性质。
贪心法求解问题的特征:
(1) 贪心选择性质
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。
(2) 最优子结构性质
当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
0-1背包问题:
给定n种物品和一个背包。物品i的体积是si,其价值为vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。