算法设计与分析

贪心算法

1.贪心算法基本原理

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。在多阶段决策过程中,贪心算法以当前状态为基础,根据特定贪心准则(也称优化测度)进行局部最优决策,而不考虑各种可能的整体情况。

贪心法自顶向下,以迭代的方法做出相继的贪心选择,它每做一次贪心选择就将所求问题简化为一个规模更小的子问题。把上述连续的局部最优决策组合起来,我们就可以得到原问题的一个全局解。需要特别注意的是,如果贪心准则设计不合理,贪心法得到的全局解不一定是最优解。

虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解,如单源最短路径问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,但其最终结果也是最优解的很好近似。正因为此,贪心算法在对NP完全问题的求解中发挥着越来越重要的作用。

2.贪心算法设计步骤

贪心算法类似于分治算法和动态规划,也是一种基于子问题思想的策略。一般地,贪心算法的求解过程通常包括如下三个步骤:

(1)分解,将原问题求解过程划分为连续的若干个决策阶段。
(2)决策,在每一个阶段依据贪心策略进行贪心决策,得到局部的最优解,并缩小待求解问题的规模。
(3)合并,将各个阶段的局部解合并为原问题的一个全局可行解。

3.典型例题

1) 哈夫曼编码

2) 最短路径

3) 最大连续子序列和

4) 最少拦截系统


4.课件下载

Algorithm-6-Greedy Algorithm.pptx


5.扩展阅读

在马尔科夫随机场(Markov Random Field, MRF)是图像处理的常用模型,求解该模型的常用方法包括Markov-chain Monte Carlo, Graph Cut, 和Iterated conditional modes(ICM)等,其中ICM就是一种贪心算法,虽然ICM不能得到最优解,但是能快速得到近似最优解。

Ref 5-1. Besag, J. E. (1986), "On the Statistical Analysis of Dirty Pictures", Journal of the Royal Statistical Society, Series B 48 (3): 259–302