Задача про вершинне покриття

Задача про суми підмножин.

Теоретичні основи “жадібних” алгоритмів.

Алгоритм GREEDY-ACTIVITY-SELECTOR дає набір з найбільшої можливої кількості спільних заявок.

Як довести, що жадібний алгоритм дає оптимальне розв’язання?

Це не завжди тривіально, але в типовому випадку таке доведення потрібне схемі, використаній в доведенні теореми. Спочатку ми доводимо, що жадібний вибір на першому кроці не закриває шляхи до оптимального розв’язання: для всякого розв’язання є інше, погоджене з жадібним вибором і не гірше першого. Потім показується, що підзадача, що виникає після жадібного вибору на першому кроці, аналогічна вихідній, і міркування завершується за індукцією.

Оптимальність для підзадач.

Інакше кажучи, розв'язувані за допомогою жадібних алгоритмів задачі мають властивість оптимальності для підзадач (have optimal substructure): оптимальне розв’язання всієї задачі містить у собі оптимальні розв’язання підзадач. Простими словами можна пояснити так: на кожному кроці жадібний алгоритм бере «самий жирний шматок», а потім уже намагається зробити найкращий вибір серед тих, що залишилися, які б вони не були.