哪些常见算法属于贪婪算法?
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/06/25 01:47:55
哪些常见算法属于贪婪算法?
Dijkstra、Prim、 Kruskal Floyd- WaWarshall、KMP string match,这些都是贪婪算法吗?贪婪算法还有哪些?
Dijkstra、Prim、 Kruskal Floyd- WaWarshall、KMP string match,这些都是贪婪算法吗?贪婪算法还有哪些?
![哪些常见算法属于贪婪算法?](/uploads/image/z/2734913-65-3.jpg?t=%E5%93%AA%E4%BA%9B%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E5%B1%9E%E4%BA%8E%E8%B4%AA%E5%A9%AA%E7%AE%97%E6%B3%95%3F)
显然KMP和FLOYD算法不是贪心算法,FLOYD算法是使用了类似于动态规划的思想,而KMP算法则是对串的前缀进行去处理得到所有可能出现匹配的位置从而减少不必要的位移.贪心算法可能还有很多,但是一般能用到的可能只有这些.在确定一个问题是否能用贪心来解决的时候应该线能够证明在这里使用贪心算法的正确性(详见算法导论)