Блог пользователя terserah

Greedy Method
Автор terserah, 11 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

We also want to be guessing problems :D

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить