定义
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解，在解决很多问题中，贪心算法是一种最有效的算法，产生最优的解
特点
- 在每一步，选择当前能够获得最大收益的操作（贪婪+短视）
- 不需要“高瞻远瞩”
典型应用场景
最小生成树
考虑一个计算机网络，每台计算机使用光纤连接。其中每条光纤会产生一些维护成本。使用带边长（权重）的图表示如下（其中边上的权重是维护成本）
image.png
问题：如果希望将总维护成本降为最低，同时保持网络连通，应该保留哪些边？去掉哪些边？
最小生成树的定义为
image.png
我们通过直觉可以得到上例的最小生产树为
image.png
Kruskal的算法
- 将图G中所有的边按照权重从小到大排序；
- 树T初始化为空，依次挑选不在T中权重最小的，且在T上不产生环的边加入T
执行实例
image.png
求上图的最小生成树
第一步将边的权重进行排序：B-C， C-D，B-D，C-F，D-F，E-F，A-D，A-B，C-E，A-C
第二步，依次加入B-C，C-D，（加入B-D会产生环，因此要略过），C-F，E-F, A-D，最后得到如下所示的最小生成树
image.png
Prim的算法
定义
图论中的一种算法，可在加权连通图里搜索，意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，[艾兹格·迪科斯彻]再次发现了该算法。因此，在某些场合，[普里姆算法]又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
执行实例
image.png
- 将全部的节点初始化，注意A节点为起始节点，前序节点设置为nil，权重设置为0
- 遍历所有节点，因为A的权重最小，将A加入到集合中，更新B，C，D，E， F节点的权重值和前序节点，结果如表格中第二行所示
- 遍历所有节点，得到D的权重最小为4，将D加入到集合中，更新B，C， E，F节点的权重值和前序节点，结果如表格中第三行所示
- 遍历所有节点，发现B和C的权重都为最小值2，随机取B节点加入到集合中，更新C，E，F的权重值和前序节点，结果如表格中第四行所示
- 遍历所有节点，发现C的权重值最小为1，将C节点加入到集合中，更新E，F的权重值和前序节点，结果如表格中第五行所示
- 遍历所有节点，发现F的节点值最小为3，将F节点加入到集合中，更新E节点
的权重值和前序节点，结果如表格中第六行所示，至此可生成如右图所示的最小生成树
Prim和Dijkstra算法的区别
Prim算法与Dijkstra算法的区别在优先队列中元素的键值
- Prim中，键值是从S中节点到本节点的最小权重边的权重
- Dijkstra中，键值是从出发点到本节点的当前最短路径长度
网友评论