How is Greedy Technique different from Exhaustive

问题:

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 

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?

回答1:

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.

Example

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

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.

回答2:

A greedy algorithm will make a locally optimal choice at each step in the process hoping that this will result in a globally optimal solution, where as an exhaustive search will look at all possible solutions and pick the most optimal one.

The greedy algorithm will run more quickly than the exhaustive one but the greedy algorithm does not guarantee an optimal solution to the problem.

回答3:

Exhaustive and greedy might yeild the same result for some problems but the algorithms and time complexity (performance) will differ. Also, exhaustive search will always give the optimal solution but greedy algorithms will give optimal solutions for some problems and for others they won't.

Exhaustive search means try every possible solution to the problem and choose the best one. So in this case it means that we figure out all the ways to divide the jobs and then pick the best one. Greedy algorithms divide the problem into smaller sub-problems. For each subproblem it solves that sub-problem in the way that's best 'right now'. It might not be the best in the long run, but for some problems it will be. In this case, greedy means that we take a job and assign it to who ever does it the fastest.