What is the difference between greedy and steepest algorithms?

Question

I have slides where 2 versions of local search algorithms are compared: greedy and steepest.

Greedy: generate solution x; repeat { for each y in N(x) in random order { if f(y) > f(x) then x = y; } } until no better solution was found

Steepest: generate solution x; repeat { find the best solution y in N(x); if f(y) > f(x) then x = y; } until no better solution was found

But everywhere on the Internet I read that greedy method searches for the best (not first better found) solution. So - what is the difference? And: which version is true?

Answer 1

I agree that greedy would also mean steepest as it attempts to make the locally optimal choice. To me the difference is that the notion of steepest descent / gradient descent is closely related with function optimization, while greedy is often heard in the context of combinatorial optimization. Both however describe the same "strategy".

In my opinion these notions are not very well suited to describe the behavior that you want to describe. I prefer the terms best improvement and first improvement local search. Both a greedy local search and the steepest descent method would be best improvement local search methods.

With regular expressions, greedy has a similar meaning: That of considering the largest possible match to a wildcard expression. It would be also wrong to state greedy matching would match on the first possibility.