贪婪算法-Greedy algorithm
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了贪婪算法-Greedy algorithm，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1837字，纯文字阅读大概需要3分钟。
内容图文
贪婪算法(greedy algorithm)
WIKI
A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage[1] with the intent of finding a global optimum.
定义
每步都采取最优的做法，即每步都选择局部最优解
背包问题(knapsack problem)
WIKI
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
集合覆盖问题(set cover problem)
WIKI
The set cover problem is a classical question in combinatorics, computer science and complexity theory.
NP完全问题(NP-completeness)
WIKI
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes. In this context, NPstands for "nondeterministic polynomial time".
旅行商问题(travelling salesman problem)
WIKI
The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.
集合覆盖问题和旅行商问题共同：都需要计算所有解，并从中选出最小/最短的那个
NP完全问题特点
-
元素较少时运行速度非常快，但随着元素数量的增加，速度会变得非常慢
-
涉及“所有组合”的问题通常是NP完全问题
-
不能将问题分成小问题，必须考虑各种可能的情况、
-
如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，可能是NP完全问题
-
如果问题涉及集合（如广播台集合）且难以解决，可能是NP完全问题
-
如果问题可转换为集合覆盖问题或旅行商问题，肯定是NP完全问题
内容总结
以上是互联网集市为您收集整理的贪婪算法-Greedy algorithm全部内容，希望文章能够帮你解决贪婪算法-Greedy algorithm所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。