贪心算法与穷举搜索有何不同？

Question

我有一些样本问题，正在编写伪代码，并且注意到贪心技术和穷举搜索之间存在令人担忧的模式。

       Job 1, Job 2, Job 3, Job 4, Job 5
Person:  1     9     2      7      8
Person:  2     6     4      3      7
Person:  3     5     8      1      8
Person:  4     7     6      9      4 

上面是一个任务问题的表格示例。基本上，你有n个工作要做，这里有五个，你需要在最短的时间内完成它们，时间由表格中每个人和他们的工作所附带的值表示。

看起来枚举搜索和贪心技术的唯一区别是两者用于解决问题的数据结构不同。贪心使用加权图，而枚举使用数组。在我们的算法中是否经常出现这种情况？许多算法是否紧密模仿彼此，但只是使用更有效的数据结构来解决问题？

- Stubudd

---

感谢您的编辑！我不确定在被编辑后该怎么做，我阅读了有关编辑帖子的特权页面。所以我只想再次说声谢谢！ - Stubudd

Answer 1

穷举搜索探索了所有可能的解决方案，然后选择最佳的一个。

贪心搜索从某个（部分）解决方案开始。然后以一种总是得到更好解决方案的方式来改进/完善此解决方案。但是，这并不一定导致所有最佳解决方案。

例子

想象一个超级简单的问题：你有这个数字序列：

index:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
numbers: 1  6  5  4  5  6  7  8  9  5  2  1  0  1  5  4  5  6  4  1

你需要找到最小的数字。如果你进行穷举搜索，你会遍历整个序列并返回遇到的最小数字。如果你进行贪婪搜索，你选择一些数字，例如索引为7的数字8。然后你尝试贪心地改进解决方案：向右看 - 有9，更糟糕了。向左看 - 有7，更好，所以移动到那里。再次查看两侧，右侧有8，左侧有6，所以向左走。你再执行两次这样的步骤，就可以到达索引3，那里是数字4。这是贪婪搜索的最终解决方案 - 你不能通过向左或向右移动来进一步改进它，但显然不是最佳解决方案。但是相比于穷举搜索，你也用更少的步骤得到了结果。

- zegkljan

Answer 2

贪心算法在每一步中做出局部最优选择，希望这将导致全局最优解；而穷举搜索将查看所有可能的解决方案，并选择最优解。

贪心算法比穷举算法运行得更快，但贪心算法不能保证问题的最优解。

- bhspencer

Answer 3

对于某些问题，穷举和贪心算法可能会产生相同的结果，但算法和时间复杂度（性能）将有所不同。此外，穷举搜索总是会给出最优解，但贪心算法只会为某些问题提供最优解，而对于其他问题则不会。

穷举搜索意味着尝试问题的每种可能解决方案，并选择最佳方案。因此，在这种情况下，我们需要找出所有分配工作的方式，然后选择最佳方案。 贪心算法将问题分解为较小的子问题。对于每个子问题，它以“现在最好”的方式解决该子问题。它可能不是长期最佳的解决方案，但对于某些问题，它确实是最佳的。在这种情况下，贪心意味着我们选择一个工作并将其分配给完成速度最快的人。

- Simon