Жадные алгоритмы
Обсуждение жадных алгоритмов — это стратегии
Жадные алгоритмы — это стратегии, которые строят решения шаг за шагом, выбирая локально оптимальный вариант на каждом шаге в надежде прийти к глобально оптимальному результату. Они мощные, простые и часто намного быстрее, чем динамическое программирование или полный перебор, но работают только тогда, когда задача удовлетворяет определённым структурным свойствам (таким как оптимальная подструктура и ``свойство жадного выбора'').
Во многих классических задачах (планирование интервалов, минимизация времени ожидания, выбор активностей, кодирование Хаффмана) доказано, что жадные алгоритмы дают оптимальные ответы. В спортивном программировании основная сложность — распознать, когда жадность корректна и каков правильный жадный критерий.
Корректные жадные решения обычно опираются на доказательства, такие как:
- Аргумент обмена: показать, что любое оптимальное решение можно перестроить так, чтобы оно следовало жадным шагам.
- Аргумент опережения: показать, что жадное решение всегда как минимум не хуже любого другого частичного решения.
Пример 1: Задача выбора активностей
Задача: Вам даны активностей со временем начала и временем окончания . Выберите максимальное число непересекающихся активностей.