How is Greedy Technique different from Exhaustive Search?

Question

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 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 shown 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? Do many algorithms mimic each other closely yet simply use more efficient data structures to accomplish our problems?

Answer 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.

Answer 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.