算法设计与分析——贪婪法（贪心算法）

算法设计与分析——贪婪法（贪心算法）

目录

一、贪婪法设计思想

1、概念

2、适用

3、缺点

二、贪婪法例子——货郎担（旅行商）问题

三、贪婪法其他例子：

1、背包问题

2、单源最短路径问题

        最短路径的狄斯奎诺（Dijkstra）算法

3、最小花费生成树问题

        克鲁斯卡尔（Kruskal）算法和普利姆（Prim）算法

4、霍夫曼编码问题

四、参考文献

一、贪婪法设计思想

1、概念

        贪婪法通常用来解决具有最大值或最小值的优化问题。它就登山一样，一步步向前推进，从某一个初始状态出发，根据当前局部的（而不是全局的）最优策略，以满足约束方程为条件，以使得目标函数的值增加最快（最慢）为准则，选择一个能够最快地到达要求的要求的输入元素，以便尽快地构成问题的可行解。

2、适用

        适合用贪婪法求解的问题，一般具有下面两个重要性质：

        ①贪婪选择性质：指所求问题的全局最优解，可以通过一系列局部最优的选择来达到。每进行一次选择，就得到一个局部的解，并把所求解的问题简化为一个规模更小的类似子问题。

        ②最优子结构：指一个问题的最优解中包含其子问题的最优解。

3、缺点

        在一般情况下，贪婪法由一个迭代的循环组成，在每一轮循环中，通过少量的局部的计算，试图去寻求一个局部最优解，而不考虑将来如何。因为每一步都是由少量的工作基于少量的信息组成的，因此所产生的算法特别有效。但是正因为这样，在很多实例中，它所产生的局部的最优解可以转换为全局的最优解；但在某些实例中，却不能给出全局的最优解。因此，在设计贪婪算法时，困难在于证明所设计的算法就是真正解决这个问题的最优算法。

二、贪婪法例子——货郎担（旅行商）问题

1、以货郎担问题为例子，具体问题表述不做赘述，假定有5个城市，费用矩阵如表1-1所示。如果货郎从第一个城市出发，采用贪婪法求解，解法如下图1-2。

表1-1

        我们总是选择费用最少的路线前进，选择的路线是1→4→3→5→2→1，总费用是14。容易看到，采用贪婪法求解时，只选择一个城市作为出发城市，所需要的运行时间是O(n²)。如果n个城市都可以作为出发城市，就可以得到n条路线，再从n条路径中选择最短的路线，则所需要的运行时间是O(n³)。

图1-2

        如果采用穷举法，当n>20时，需要运行数千万年，而采用贪婪法在很短的时间内就能完成，虽然效率大大提高了，但所得结果不是最优的路线。从城市1出发的最优路线是1→2→5→4→3→1，总费用只有13。

三、贪婪法其他例子：

1、背包问题

        给定一个载重量为M的背包，及n个重量为Wi、价值Pi的物体，要求把物体装满背包，且使得背包内的物理价值最大，这类问题称为背包问题。有两种背包问题，即物体可以分割的背包问题及物体不可以分割的0/1背包问题。这里讨论物体可以分割的背包问题。

        例：用贪婪法求如下背包问题的最优解：n=7，M=15，价值P={10，5，15，7，6，18，3}，重量为W={2，3，5，7，1，4，1}。

        解：

        （a）计算物体价格重量比  

          (b)对物体价重比进行排序

        （c）优先放入价重比高的物体

        总结：物体放入顺序为5→1→6→7→3→4，背包最大价值为54。

        在背包问题中贪心算法可以得到最优解，而对于0/1背包，贪心算法不能得到最优解，因为它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包的价值降低了。

2、单源最短路径问题

        最短路径的狄斯奎诺（Dijkstra）算法

3、最小花费生成树问题

        克鲁斯卡尔（Kruskal）算法和普利姆（Prim）算法

4、霍夫曼编码问题

四、参考文献

        1、郑宗汉，郑晓明编著. 算法设计与分析 第3版[M]. 北京：清华大学出版社, 2017.10.