Giu*_*Pes 19 algorithm heuristics greedy
贪心算法和启发式算法有什么区别？
我已经阅读了一些关于这个论点的文章,在我看来它们或多或少是相同类型的算法,因为它们的主要特征是在每次迭代时选择最佳(本地)选项来解决问题.
Sam*_*ney 19
我已经向我描述了启发式方法,它们是"经验法则".他们制作全球最优解决方案的能力可能无法直接证明,但通常他们做得很好.当确定最优解决方案的成本太高时,经常使用它们.此外,启发式算法通常会对过去如何解决问题进行一定程度的体验.描述启发式的更好方法是"解决策略".
贪婪算法是根据目前看起来最好的算法做出选择的算法.换句话说,选择是局部最优的,但不一定是全局最优的(可能是幸运的,但你不能证明它).此外,Greedy算法通常不会根据新信息改进其解决方案.这只是一种解决策略(又称启发式).
为了提供贪婪算法如何工作的示例,如果您使用一个来帮助您计划从国家的一侧到另一侧以最短距离行驶的路线,则可能选择短的慢路.不一定了解高速公路虽然更长,也许更直接,但是更好的选择.
另一种策略(启发式)可能会寻求使用高速公路覆盖尽可能多的旅程(因为对于大多数目的地而言,它们往往更直接),然后使用正常的道路进行过渡.在某些情况下,它可能会表现得相当糟糕,但在大多数情况下,它会做得很好,说实话,它可能是我们在通勤时使用的类似启发式(如果不使用卫星导航).
包起来...
是所有启发式,贪婪算法 - 没有
都是贪心算法,启发式 - 总的来说,是的.
为了提供一些背景知识,我在大学算法课上教的第一个问题之一是旅行推销员问题.它属于NP完全类问题,意味着没有有效的解决方法.也就是说随着问题规模的扩大,寻找解决方案所需的时间也会大幅增加.存在许多可证明的算法,但它们的性能不是很好,在现实世界的应用中,我们倾向于支持启发式(包括贪婪算法 - 参见链接).
他们的主要特征是在每次迭代中选择最佳（本地）选项
对于启发式分析根本不正确。启发式算法所做的选择在理论上被认为是次优的，但是在实践中已经证明可以产生合理的结果。启发式方法通常可以找到一个近似的解决方案：
在计算机科学，人工智能和数学优化中，启发式技术是一种设计用于在经典方法太慢时更快地解决问题，或在经典方法无法找到精确解时找到近似解的技术。这是通过权衡最优性，完整性，准确性或精度来实现的。
贪婪是启发式的一个例子（做出最佳的本地选择并希望获得最佳的全局结果），但这并不意味着启发式是贪婪的。有许多与贪婪完全无关的试探法。遗传算法被认为是启发式的：
在人工智能的计算机科学领域，遗传算法（GA）是一种模仿自然选择过程的搜索启发式方法。