Жадные алгоритмы
Жадные алгоритмы: локально лучший шаг, задача о непересекающихся интервалах, границы применимости.
Жадный алгоритм на каждом шаге делает локально лучший выбор и никогда не пересматривает решения. Когда жадность корректна, получается самое быстрое и короткое решение из возможных. Когда некорректна — уверенно выдаёт неправильный ответ. Всё искусство — отличать первое от второго.
Эталонная задача: даны n мероприятий с временем начала и конца; выбрать максимум непересекающихся. Правильная жадность: всегда брать мероприятие с САМЫМ РАННИМ КОНЦОМ — оно оставляет максимум времени для остальных.
Максимум непересекающихся интервалов. Введите: 4, затем пары «начало конец»: 1 3, 2 5, 4 7, 6 8
Почему «ранний конец» верен: пусть оптимальный ответ взял первым какое-то другое мероприятие. Заменим его на мероприятие с самым ранним концом — оно закончится не позже, значит, всё остальное расписание останется допустимым. Ответ не ухудшился. Этот приём доказательства («обменное рассуждение») — стандарт для жадных.
А вот антипример, показывающий, что жадность не универсальна: монеты достоинством 1, 3 и 4, надо набрать 6. Жадный берёт 4+1+1 — три монеты. Оптимум: 3+3 — две. С такими системами монет нужна динамика (следующий уровень!), а не жадность.
Признаки, что жадный МОЖЕТ работать: сортировка очевидно напрашивается; выбор на текущем шаге не ограничивает будущее сильнее, чем любой другой; удаётся набросать обменное рассуждение.
Задание: n заявок с дедлайнами и наградами не даём — начните с простого: даны длины n верёвок, соединять две верёвки стоит сумму их длин; докажите (или опровергните на маленьком тесте), что жадное соединение двух самых коротких даёт минимальную стоимость. Проверьте себя перебором для n = 4.
Отметьте урок пройденным и переходите к DSU.