如何是贪婪的技术来自穷举搜索有什么不同？ [英] How is Greedy Technique different from Exhaustive Search?

问题描述

我要问这个问题，由于采取了算法中当然目前在学校和试图总结我的脑袋周围的一些话题，因为我学习。

I'm asking this question due to taking a Algo course currently at school and trying to wrap my head around some topics as I study.

我有一些我写假code样品的问题，我注意到了贪婪的技术和穷举搜索之间惊人的模式。

I have some sample problems that I'm writing pseudo code for and I'm noticing alarming patterns between the greedy technique and exhaustive search.

       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量，需要完成他们在他们的最小量分别为时间显示被连接到每个人，他们在工作表中的值。

The above is the a table example of an assignment problem. Basically you have n amount of jobs to do, five here, and you need to complete them in the smallest amount of them were time is show by the values attached to each person and their job in the table.

有似乎是在穷举搜索和贪婪技术，唯一的区别是所用既解决上述问题的数据结构。贪婪的使用权，而图形详尽的使用数组。这是否发生了很多我们的算法。由于许多人模仿彼此紧密又简单地使用更高效的数据结构来实现我们的问题？谢谢你的时间！

It seems to be that the only difference in the exhaustive search and the greedy technique are the data structures used by both to solve the problems. Greedy uses weighted graphs while exhaustive uses arrays. Does this happen a lot in our algorithms. Due many of them mimic each other closely yet simply use more efficient data structures to accomplish our problems? Thanks for your time!

推荐答案

穷举搜索探索所有可能的解决方案，然后它能够​​挑选一个是最好的。

Exhaustive search explores all possible solutions and then it is able to pick the one that is the best.

贪婪搜索开始与一些（部分）解决方案。此溶液然后提高/中的方式，它总是得到更好完成。然而，这并不必然导致对所有这些的最佳解决方案。

Greedy search starts with some (partial) solution. This solution is then improved/completed in a way that it always gets better. However, this does not necessarily lead to the best solutions of all of them.

示例

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

Imagine a super simple problem: you have this sequence of numbers:

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号。而且，一个是该贪婪搜索的最终解决方案 - 你不能提高它更通过去左或右，但显然不是最好的。但你也有它比穷举搜索更少的步骤。

and you are to find the smallest number. If you do exhaustive search, you go through the whole sequence and just return the smallest number encountered. If you do greedy search, you pick some number, e.g. the one at the index 7, which is 8. You then try to greedily improve the solution: you look right - there is 9 and that is worse. You look left - there is 7, which is better, so move there. Again you look at both sides and there is 8 on the right and 6 on the left, so go left. You do that twice more times and you get to index 3 where is the number 4. And that one is the final solution of this greedy search - you cannot improve it more by going left or right, but clearly not the best possible. But you also got it in far fewer steps than with the exhaustive search.

这篇关于如何是贪婪的技术来自穷举搜索有什么不同？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！