浅析贪心算法

1.基本思路：

a.顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

b.贪心算法一般可以先做一个排序，然后选择。

2.例题：

（1）迪杰斯特拉算法求最短路径

http://touch-2011.iteye.com/blog/1076031

（2）最小生成树的算法

http://touch-2011.iteye.com/blog/1075840

（3）哈弗曼编码

http://touch-2011.iteye.com/blog/1058800