Жадные алгоритмы

Обсуждение жадных алгоритмов — это стратегии

Жадные алгоритмы — это стратегии, которые строят решения шаг за шагом, выбирая локально оптимальный вариант на каждом шаге в надежде прийти к глобально оптимальному результату. Они мощные, простые и часто намного быстрее, чем динамическое программирование или полный перебор, но работают только тогда, когда задача удовлетворяет определённым структурным свойствам (таким как оптимальная подструктура и ``свойство жадного выбора'').

Во многих классических задачах (планирование интервалов, минимизация времени ожидания, выбор активностей, кодирование Хаффмана) доказано, что жадные алгоритмы дают оптимальные ответы. В спортивном программировании основная сложность — распознать, когда жадность корректна и каков правильный жадный критерий.

Корректные жадные решения обычно опираются на доказательства, такие как:

• Аргумент обмена: показать, что любое оптимальное решение можно перестроить так, чтобы оно следовало жадным шагам.
• Аргумент опережения: показать, что жадное решение всегда как минимум не хуже любого другого частичного решения.

Пример 1: Задача выбора активностей

Задача: Вам даны $n$ активностей со временем начала $s_i$ и временем окончания $f_i$. Выберите максимальное число непересекающихся активностей.