AI 中文社
Copyright © 2022-2024 aizws.net · 网站版本: v1.2.6·内部版本: v1.23.3·
页面加载耗时 0.00 毫秒·物理内存 64.2MB ·虚拟内存 1301.8MB
欢迎来到 AI 中文社区（简称 AI 中文社），这里是学习交流 AI 人工智能技术的中文社区。 为了更好的体验，本站推荐使用 Chrome 浏览器。
算法：贪婪算法
设计算法以实现给定问题的最佳解决方案。在贪婪算法方法中，决策是从给定的解决方案域做出的。由于贪婪，选择了似乎提供最佳解决方案的最接近的解决方案。
贪心算法试图找到一个本地化的最优解决方案，最终可能导致全局优化的解决方案。但是，通常贪婪算法不提供全局优化的解决方案。
计数硬币
这个问题是通过选择最不可能的硬币来计算到期望的值，并且贪婪的方法迫使算法选择最大可能的硬币。如果我们提供₹1,2,5和10的硬币，我们被要求计算₹18，那么贪婪程序将是
- 1 - 选择一个₹10硬币，剩余计数为8
- 2 - 然后选择一个₹5硬币，剩余计数为3
- 3 - 然后选择一个₹2硬币，剩余计数为1
- 4 - 最后，选择一个₹1个硬币可以解决问题
虽然，它似乎工作正常，但这个数量我们只需要选择4个硬币。但是，如果我们稍微改变问题，那么相同的方法可能无法产生相同的最佳结果。
对于货币系统，我们有硬币值为1,7,10的值，计算值为18的硬币绝对是最佳的，但对于15的计数，它可能会使用超过必要的硬币。例如，贪婪的方法将使用10 + 1 + 1 + 1 + 1 + 1，总共6个硬币。而只使用3个硬币(7 + 7 + 1)就可以解决同样的问题
因此，我们可以得出结论，贪婪的方法选择了一个立即优化的解决方案，并且可能在全局优化成为主要问题的地方失败。
例子
大多数网络算法都使用贪婪的方法。以下是其中一些列表 -
- 旅行推销员问题
- Prim的最小生成树算法
- Kruskal的最小生成树算法
- Dijkstra的最小生成树算法
- 图 - 地图着色
- 图 - 顶点覆盖
- 背包问题
- 作业调度问题
有许多类似的问题使用贪婪的方法来找到最佳解决方案。
下一章：算法：分而治之
在分而治之的方法中，手头的问题被分成较小的子问题，然后每个问题都独立解决。当我们继续将子问题划分为更小的子问题时，我们最终可能会达到无法进行更多划分的阶段。解决那些“原子”最小可能的子问题(分数)。最后合并所有子问题的解决方 ...