贪婪技术与穷尽搜索有何不同？

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个工作要做，这里有5个，你需要用最少的时间来完成它们，时间是由每个人的附加值和表中的工作显示出来的。

看来，穷举搜索和贪婪技术的唯一不同之处在于两者用来解决问题的数据结构。贪婪使用加权图，而穷举则使用数组。这在我们的算法中经常发生吗？许多算法相互模仿，但仅仅使用更有效的数据结构来完成我们的问题吗？

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。而那个是这个贪婪搜索的最终解决方案--你不能通过左转或右转来改进它，但显然不是最好的。但是，与穷尽搜索相比，您获得的步骤要少得多。

Answer 2

贪婪算法在整个过程中的每一步都会进行局部最优选择，希望得到一个全局最优解，在此过程中，作为一种彻底的搜索，将寻找所有可能的解，并选择最优的解。

贪婪算法比穷举算法运行速度快，但贪婪算法不能保证问题的最优解。

Answer 3

对于某些问题，穷举和贪婪可能会得到相同的结果，但算法和时间复杂度(性能)会有所不同。此外，穷举搜索总是会给出最优解，但是贪婪算法会给出一些问题的最优解，而对于另一些问题则不会。

穷举搜索意味着尝试问题的每一个可能的解决方案并选择最佳的解决方案。因此，在这种情况下，这意味着我们找到了所有的方法来分配工作，然后选择最好的。贪婪算法将问题分解为较小的子问题.对于每个子问题，它以最好的“现在”的方式来解决这个子问题。从长远来看，这可能不是最好的，但对于一些问题，它将是。在这种情况下，贪婪意味着我们接受一份工作，并分配给谁做得最快。