Алгоритмы с нуля
Greedy: тест с выбором
Суть Синтез по всему юниту в формате выбора: greedy choice property, exchange argument, когда greedy обыгрывает DP и когда тихо ошибается, и правильный ключ сортировки для interval scheduling.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на senior-высоте — в орбитеШесть вопросов через весь юнит. Каждый — это решение, которое вы принимаете, когда всерьёз тянетесь за greedy: не определение для пересказа, а суждение о том, доказуемо ли локальный выбор является глобальным, и что делать, когда это не так.
Цель
Убедитесь, что вы связываете воедино greedy choice property, exchange argument, выбор ключа сортировки для interval-задач и сигнатуру отказа небезопасного greedy — синтез, к которому вели все четыре урока.
Викторина
Completed
Коллега говорит: greedy прошёл все 40 моих случайных тестов, значит он корректен для этой задачи. Почему это рассуждение несостоятельно и что на самом деле решило бы вопрос?
Heads-up Случайные тесты выбирают отдельные входы; они никогда не устанавливают универсальное свойство. Greedy на монетах {1,3,4} оптимален для сумм от 1 до 5 и ошибается только на 6 — малый набор тестов проходит мимо единственного провального случая.
Heads-up Никакое конечное число тестов не доказывает оптимальность на бесконечной области входов. Проблема не в размере выборки, а в том, что тестирование не может удостоверить утверждение для всех входов — это может только доказательство.
Heads-up Случайные тесты или подобранные — для логики неважно: примеры могут подтвердить баг, но никогда не подтвердят отсутствие контрпримера. Доказательство или контрпример — единственный вердикт.
Викторина
Completed
Нужно выбрать максимум непересекающихся встреч в одной комнате. Коллега сортирует по кратчайшей длительности (короткие встречи плотнее упаковываются). На [0,4], [3,5], [4,8] что получится и почему ключ неверен?
Heads-up Кратчайшая длительность берёт [3,5] первым и затем блокируется от обоих других, давая 1, а не 2. Весь смысл этого контрпримера в том, что он расходится с оптимумом.
Heads-up [3,5] пересекается и с [0,4], и с [4,8], так что все три не могут сосуществовать. Максимальный непересекающийся набор здесь равен 2: [0,4], затем [4,8].
Heads-up Сортировка по старту — это ключ для MERGING интервалов, а не для максимизации. Для most-non-overlapping единственный доказуемо оптимальный ключ — earliest finish time; и длительность, и старт неверны.
Викторина
Completed
В exchange argument для activity selection вы убираете первую работу X из оптимума O и вставляете greedy-работу G с самым ранним финишем. Какой единственный факт сохраняет расписание допустимым?
Heads-up Аргумент никогда не предполагает равных стартов — G может стартовать раньше или позже. Важен порядок по финишу G.finish <= X.finish, именно он гарантирует, что более поздние работы всё ещё помещаются.
Heads-up Не удаляется ничего, кроме X; доказательство должно ПОКАЗАТЬ, что оставшиеся работы по-прежнему помещаются, и делает это через G.finish <= X.finish. Никакого магического удаления конфликтов нет.
Heads-up Greedy берёт работу с самым ранним ФИНИШЕМ, которая часто короткая, а не длинная. Длительность нерелевантна; двигателем обмена является неравенство по времени финиша.
Викторина
Completed
Для размена монетами {1, 3, 4} и суммы 6 greedy выдаёт 4+1+1 = 3 монеты, а DP — 3+3 = 2. Что это рассогласование говорит про exchange argument и какой корректный запасной вариант?
Heads-up Greedy уже сортирует монеты по убыванию; провал внутренне присущ набору номиналов {1,3,4}, а не сортировке. Никакой порядок не спасает — greedy choice property действительно не выполняется.
Heads-up Спецобработка одного входа — это заплатка на дыре, а не починка. {1,3,4} лишён свойства структурно, и другие суммы тоже могут провалиться. Принципиальный ответ — DP, которому такое свойство не нужно.
Heads-up DP исчерпывающе минимизирует число монет и доказуемо оптимален; 3+3 = 2 монеты действительно лучше, чем 4+1+1 = 3. Именно greedy возвращает худший ответ здесь.
Викторина
Completed
По всему юниту: в чём точное различие между greedy и динамическим программированием на одной и той же задаче оптимизации?
Heads-up Greedy явно НЕ исследует комбинации — он фиксирует один локальный выбор и не сравнивает альтернативы. Именно поэтому он может ошибаться там, где DP прав, как с монетами {1,3,4}.
Heads-up Всё наоборот: DP корректен на любой задаче с optimal substructure; greedy корректен только на подмножестве, где есть ещё и greedy choice property. Greedy меняет широту корректности на скорость.
Heads-up Они могут возвращать разные результаты — в этом весь урок про {1,3,4}. Различие в том, что они исследуют (все комбинации против одного локального выбора), а не в стиле рекурсии.
Викторина
Completed
В Gas Station коллега возвращает -1 в первый же момент, когда бак уходит в минус на станции i. Почему это неверно и какая логика корректна?
Heads-up Пересыхание от одного кандидата-старта ничего не говорит про другие старты. Маршрут всё ещё может быть выполним с более поздней станции; выполнимость решается суммарным net fuel, а не первым провалом.
Heads-up Сброс в start+1 медленнее и опирается на неверный инвариант: каждая станция между start и i тоже дисквалифицирована (до неё доезжали с неотрицательным баком от start, так что стартуя там, до i доедешь с ещё меньшим топливом). Пропустите их все — прыгайте в i+1.
Heads-up Локальный баланс первой станции нерелевантен глобальной выполнимости. Единственное условие, решающее, работает ли ХОТЬ КАКОЙ-ТО старт, — это суммарный net fuel >= 0.
Итог
Сквозная линия юнита — одна дисциплина: greedy всегда выполняется и всегда что-то возвращает, поэтому единственный важный вопрос — доказуемо ли его локальный выбор глобален. Exchange argument (или stays-ahead) — то, чем вы доказываете безопасность; отсутствующий swap — как у монет 4 для 6 — сам по себе доказательство провала, а запасной вариант — DP. Для interval-задач сложное — это ключ сортировки: earliest finish для максимизации, start для merging, sweep по стартам и финишам для комнат. А для scan-greedy вроде Gas Station никогда не решайте по локальному провалу — решайте по глобальному инварианту.