Question

哪些常见算法属于贪婪算法？

Dijkstra、Prim、 Kruskal Floyd- WaWarshall、KMP string match，这些都是贪婪算法吗？贪婪算法还有哪些？

Answer 1

显然KMP和FLOYD算法不是贪心算法，FLOYD算法是使用了类似于动态规划的思想，而KMP算法则是对串的前缀进行去处理得到所有可能出现匹配的位置从而减少不必要的位移。贪心算法可能还有很多，但是一般能用到的可能只有这些。在确定一个问题是否能用贪心来解决的时候应该线能够证明在这里使用贪心算法的正确性（详见算法导论）

Answer 2

floyed,kmp都不是。网络流，费用流中的增广路算法是贪心算法。

追问

您说的网络流费用流是最大流问题吗？
除了这些还有没有典型的贪婪算法？