简论贪心论贪心算法在图论中运用普通

论文导读：
摘 要：本文介绍了贪心算法的基本概念和解题思想，并通过两个典型的实例，说明了在图论中贪心算法的具体的应用。
关键词：贪心算法；最优子结构性质；贪心准则
中图分类号：TP18
贪心算法是用来求解某些问题最优解的一种有效算法，它可以简单迅速的解决很多实际应用的问题，在图论领域也有着非常广泛的应用。
1 贪心算法概述

1.1 贪心算法定义

贪心算法是一种经过改进的分级处理的方法。贪心算法在进行决策的时候总会做出对目前情况最好的选择。和动态规划算法不同的是，贪心算法并不考虑问题的整体最优，而只是选择某种意义上的局部最优。所以，贪心方法未必能针对所有问题求得整体的最优解，但是对于许多问题而言，它却能得到整体最优解。在某些情况下，贪心算法虽然得不到整体最优解，却可以得到最优解的很好的近似。

1.2 贪心算法的基本要素

对于一个具体问题，怎样才能知道能否可以用贪心算法求解并得到最优解呢？在实际应用中人们总结出了两个重要的性质：
（1）贪心选择性质；（2）最优子结构性质。
许多可以利用贪心方法求解的问题一般都具备这两个性质。

1.3 贪心算法的求解步骤

贪心算法求解问题首先要确定一个贪心准则，每一步都是按这个准则选取优化方案。按照这种度量标准对此问题的n个输入排序，并按序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。因此贪心准则的选取直接关系到可行解能否达到最优。
2 贪心算法求解单源点最短路径问题
图论中有一个非常典型的问题：单源点最短路径问题。问题描述如下：对于有向带权图G =（V，E），其中每条边上的权值是一个非负实数。选定V中的一个顶点，称之为源点。这个问题求解的是从源点到图G中其他所有顶点的最短路径的长度。所谓的长度是指经过的各边上的权值总和。
Dijkstra算法正是利用贪心算法求解此问题，用迄今已生成的所有路径长度之和为最小作为贪心准则，为此，每一条单独的路径都必须具有最小长度。此算法的实现步骤为：将顶点集合分为S和V-S这两个子集。子集S中均为已求得最短路径的顶点。初始时，集合S中只有源点，接下来不断做贪心选择来扩充此集合。取G中的一个顶点v，把从源点到v点并且只经过S中顶点的路径称为从源点到顶点v的特殊路径，设置数组dist记录每个顶点当前所对应的最短特殊路径的长度。Dijkstra算法每次都从子集V-S中取出特殊路径长度为最短的顶点，并把该顶点添加至子集S，随后对数组dist进行修改。一旦子集S等于顶点集V，算法结束。数组dist中记录的就是源点到图中其他各顶点的最短路径的长度。
例如，下图1中的有向带权图，采用Dijkstra算法，从源点1到图中剩余各顶点间最短路径的计算过程如下表1所示：
3 贪心算法求解最小生成树问题
最小生成树是非常具有实际应用价值的图论问题，具体描述如下：已知无向连通带权图G=（V，E）。E中每条边（u，v）的权值设为c[u][v]。求图G的生成树G’，使得G’上各边权值的总和是所有生成树中各边权值总和最小的。这个问题被称为最小生成树问题。最小生成树的求解方法有多种，其中应用比较广泛的几种算法，如Prim算法和Kruskal算法都是采用了贪心算法的策略。

3.1 Prim算法

Prim算法的基本思想为：首先选择图中任意顶点u，并将u置于顶点集合的子集S中。如果S是顶点集合V的真子集，就继续选择顶点j添加到子集S中，这里的j必须满足条件i?S，j?V-S，且c[i][j]是权值最小的边。按照同样的步骤不断进行贪心选择，直到子集S=V为止。此时，选取到的所有的边就构成了图G的一棵最小生成树。例如，对于图2中的无向连通带权图，按照Prim算法求最小生成树的过程如图3所示。

3.2 Kruskal算法

Kruskal算法构造最小生成树的过程相比Prim算法更加简单明了。首先将无向连通带权图G的n个顶点作为n个孤立的连通分支。并按照权值给所有的边从小到大进行排序。将第一条边加入到连通分支，然后按权值递增的顺序依次查看剩下的每一条边，如果这条边加入构成回路就抛弃，继续考察下一条边，反之加入到连通分支中。一旦加入边的条数等于n-1，则算法结论文导读：两个典型问题，贪心算法不但能够正确的求解，而且与其他算法相比，更是体现了其高效的优势。当然，图论中还有许多未解的问题，这些问题能否用贪心算法求解，或者能否找到更好的贪心准则提高求解的效率则需要更加深入的研究和发现。参考文献：余祥宣，崔国华，邹海明.计算机算法基础（第三版）.华中科技大学出版社，2006.王晓
束。剩下唯一的连通分支就是要求取的最小生成树。
例如，对上图2，按Kruskal算法求得最小生成树的过程如下图4所示。
比较上述两种方法可以看出，虽然都是利用贪心算法解决，但是由于选择的贪心准则不一样，因次求解步骤和最小生成树的选边过程都是不一样的。
4 总结
贪心算法也存在着缺点，比如应用范畴比较狭窄而且有一些极难证明，但是针对图论的部分问题，比如上述的两个典型问题，贪心算法不但能够正确的求解，而且与其他算法相比，更是体现了其高效的优势。当然，图论中还有许多未解的问题，这些问题能否用贪心算法求解，或者能否找到更好的贪心准则提高求解的效率则需要更加深入的研究和发现。
参考文献：
余祥宣，崔国华，邹海明.计算机算法基础（第三版）[M].华中科技大学出版社，2006.
王晓东.算法设计与分析（第2版）[M].清华大学出版社，2008.
[4]杨克昌.计算机常用算法与程序设计案例教程[M].清华大学出版社，2011.
[5]王桂平，王衍，任嘉辰.图论算法理论、实现及应用[M].北京大学出版社，20摘自：毕业论文提纲www.7ctime.com
11.