CODEWITHSUNDEEP
algorithm
Guest
Guest

Reputation: 3177

Why is this a greedy algorithm?

I have this question in my text book:

" Suppose that we have a set of activities to schedule among a large number of lecture halls, where any activity can take place in any lecture hall. We wish to schedule all the activities using as few lecture halls as possible. Give an efficient greedy algorithm to determine which activity should use which lecture hall. "

And the answer is given here: http://mitpress.mit.edu/algorithms/solutions/chap16-solutions.pdf

(the firs solution)

And my answer is, why is the algorithm a greedy algorithm?

I think that it is because it makes the (greedy?) choice that you always take an activity and put it into a lecture hall, where there already is one or more activities (if possible), instead of putting the activity into a new empty lecture hall. But I am not sure. :)

Upvotes: 6

Views: 3275

Answers (4)

biziclop
biziclop

Reputation: 49804

I don't know if a single official definition of "greedy" exists at all, but for me a greedy solution is one that reduces a problem to the selection of a series of locally optimal solutions in the hope that when they're put together, they're close to the overall optimal solution. (Sometimes this hope is more than hope though.)

Upvotes: 1

Charles Keepax
Charles Keepax

Reputation: 2410

The definition of a greedy algorithm is that it takes the apparent best choice at each step, as opposed to considering several steps ahead. Thus finds a local minima of the search space (gradient descent perhaps worth a little google). A chess program makes a good example of this, a greedy algorithm would always make the most powerful direct move (take a piece, maximise piece development) but wouldn't consider several moves into the future.

Unfortunately, I don't seem to be able to open the link you have included at the moment. But I can hesitate a good guess that the algorithm is greedy because once it has fitted an event into a hall it will not reconsider that decision (backtracking is probably worth a quick google at this point).

Upvotes: 1

Ted Hopp
Ted Hopp

Reputation: 234857

It's because you do the most with lecture hall 1 before even considering the rest of the problem. In this sense, lecture hall 1 is "greedy".

Upvotes: 2

soandos
soandos

Reputation: 5146

Greedy means that you don't reconsider your choices. that makes it very hard to come up with an optimal solution, and it describes the algorithm there.

Upvotes: 3

Related Questions