terserah's blog

Greedy Method
By terserah, 11 years ago, In English

I recently studied about greedy algorithm. But all I do is guessing. Can someone share a good documentation about proofing a correctness of greedy algorithm? Or maybe greedy algorithm is based on guess?

Thanks in advance! Happy Coding!

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

there's no general pattern to proof correctness of greedy algorithms, you should consider each greedy algorithm has it's own proof

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We also want to be guessing problems :D

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Every greedy algorithm has a correct proof, but not every algorithm is easy to proof. For me it's more based on the intuition at the moment, so you should trust on your guess.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe the Exchange Argument is a technique that will show that a greedy algorithm is optimal.

→ Reply