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!
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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!
Название |
---|
there's no general pattern to proof correctness of greedy algorithms, you should consider each greedy algorithm has it's own proof
We also want to be guessing problems :D
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.
Maybe the Exchange Argument is a technique that will show that a greedy algorithm is optimal.