Алгоритмы с нуля

Аргумент обмена: доказываем, что жадный выбор безопасен

Суть Жадный алгоритм корректен только если его выбор безопасен. Аргумент обмена это доказывает: возьми любое оптимальное решение и сдвинь его к жадному выбору, не делая хуже — значит оптимум, согласованный с жадным, существует. Без такого обмена жадный небезопасен.

◷ 26 min

В прошлом уроке ты писал жадные алгоритмы, которые хватают локально лучший вариант на каждом шаге и никогда не оглядываются назад. Они были быстрыми и простыми — но «простой» это не то же самое что «корректный». Иногда тот жадный захват загоняет тебя в угол, и итоговый ответ хуже наилучшего возможного. Так как же вообще доверять жадному алгоритму? Ты не запускаешь его на нескольких входах и надеешься. Ты его доказываешь. Рабочая лошадка доказательства это аргумент обмена: возьми любое оптимальное решение, покажи, что можешь сдвинуть его на один шаг к тому, что выбирает жадный, не делая хуже, и заключи, что оптимум, согласованный с жадным, должен существовать. Этот урок учит тебя этому доказательству — и как распознать, когда оно проваливается.

Цель

После этого урока ты можешь доказать корректность жадного алгоритма аргументом обмена: предположи оптимальное решение, которое отличается от жадного на первом выборе, потом обменяй эту часть оптимума на жадный выбор и покажи, что результат всё ещё допустим и не хуже. Ты можешь провести этот аргумент конкретно на выборе активностей (выбери совместимую работу, завершающуюся раньше всех) и объяснить, почему обмен никогда не уменьшает число работ, которые ты вмещаешь. Ты можешь назвать две половины, которые нужны полному жадному доказательству — аргумент обмена для безопасного первого выбора плюс оптимальная подструктура для остального — и ты можешь распознать родственную технику, «жадный остаётся впереди», которая отслеживает одну величину вместо обмена. Что важно, ты можешь показать, когда аргумент обмена проваливается: монетная система 4 не имеет допустимого обмена, и этот отсутствующий обмен это ровно причина, почему жадный там неправ. Следующий урок применяет эти инструменты к классической жадной задаче от начала до конца.

Идея

Почему жадному алгоритму вообще нужно доказательство

Жадный алгоритм фиксирует локально лучший вариант на каждом шаге. Опасность очевидна: выбор, который выглядит лучшим прямо сейчас, может заблокировать лучший выбор позже. Так что перед тем как доверять жадному на задаче, ты должен доказать, что его первый выбор безопасен — что фиксация на нём никогда не стоит тебе оптимального ответа. Аргумент обмена это как раз то, чем ты доказываешь именно это.

Аргумент обмена, в трёх ходах

Ты хочешь показать: существует оптимальное решение, которое согласуется с жадным выбором. Доказательство это мысленный эксперимент, а не код.

Предположи произвольное оптимальное решение O. Может быть, оно уже делает жадный первый выбор — тогда ты закончил. Так что предположи, что нет: O оптимально, но отличается от жадного на первом решении.
Обменяй. Измени O, заменив то, что оно выбрало первым, на жадный выбор, получив новое решение O'. Всё мастерство в том, чтобы спроектировать этот обмен так, чтобы O' оставалось допустимым (корректным решением) и не хуже чем O (то же значение или лучше).
Заключи. Поскольку O было оптимально, а O' не хуже, O' тоже оптимально — и O' теперь согласуется с жадным на первом выборе. Так что оптимальное решение, содержащее жадный выбор, существует. Жадный первый выбор безопасен.

Повтори те же рассуждения на меньшей задаче, которая остаётся после первого выбора (это оптимальная подструктура), и по индукции всё жадное решение оптимально.

Optimal O  :  [ X ] rest...        (X = what O chose first, not greedy's pick)
                |  swap X -> G
                v
New     O'  :  [ G ] rest...        same size / value, still feasible
                ^
                greedy's choice G now sits in an optimal solution -> G is safe

Ключевая идея: ты не строишь ответ жадного — ты переформовываешь оптимум к нему

Заметь направление. Ты не доказываешь, что жадный лучший с нуля. Ты начинаешь с известного оптимума и преобразуешь его обмен за обменом, пока он не станет выглядеть как вывод жадного, доказывая на каждом обмене, что ничего не было потеряно. Если каждый обмен безвреден, вывод жадного так же хорош как оптимум.

Рабочая цель: выбор активностей

У тебя есть работы, у каждой время начала и завершения. Ты хочешь как можно больше работ, которые не пересекаются. Жадное правило: всегда выбирай совместимую работу, которая завершается раньше всех. Интуиция: завершение раньше всех оставляет больше всего места для всего, что после неё. Аргумент обмена делает эту интуицию строгой.

Пусть G это работа, завершающаяся раньше всех в целом, и пусть O это любое оптимальное расписание. Пусть X это первая работа в O (та, что завершается раньше всех в O). Поскольку G завершается раньше всех всех работ, G.finish <= X.finish. Замени X в O на G:

Всё ещё допустимо? Да. X была совместима с остальной частью O, то есть всё прочее в O начинается в момент или после X.finish. Поскольку G.finish <= X.finish, те же самые работы тоже начинаются в момент или после G.finish. Так что G не пересекается ни с одной из них.
Не хуже? Да. Мы убрали ровно одну работу и добавили ровно одну работу: число не изменилось. O' планирует ровно столько же работ, сколько O.

Так что O' оптимально и содержит G. Жадный первый выбор безопасен. Сними G и работы, с которыми она конфликтует, и остаток это меньшая задача выбора активностей — реши её тем же способом. Жадный оптимален.

Родственная техника: «жадный остаётся впереди»

Аргумент обмена меняет местами внутри оптимума. «Жадный остаётся впереди» вместо этого отслеживает одну измеримую величину и доказывает, что значение жадного на каждом шаге не хуже, чем у любого другого решения. Для выбора активностей ты бы доказал: после выбора своих первых k работ k-я работа жадного завершается не позже, чем k-я работа любого другого допустимого расписания — так что жадный никогда не отстаёт и в итоге вмещает не меньше работ. Обе техники доказывают одну корректность; выбирай ту, что чище для задачи. Обмен обычно более общий инструмент.

Когда аргумент обмена проваливается, жадный неправ

Аргумент это не штамп для галочки — он работает только когда безвредный обмен действительно существует. Если ты не можешь сдвинуть оптимум к жадному выбору не сделав хуже, это не пробел в твоей сообразительности; это доказательство, что жадный небезопасен. Монетная система 4 при размене 6 это классический провал: жадный хватает 4, потом нуждается в 1 + 1, итого 3 монеты — но оптимум это 3 + 3, всего 2 монеты. Попробуй сдвинуть пару троек оптимума к четвёрке жадного, и ты застрял: убрать тройку и добавить четвёрку это перелёт. Допустимого обмена не существует, так что жадный здесь не доказуемо оптимален — и действительно он неправ.

Код

Жадный алгоритм выбора активностей

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


      1
      function selectActivities(jobs) {
    

      2
      // Greedy rule: consider jobs in order of earliest finish time
    

      3
      const byFinish = [...jobs].sort((a, b) => a.finish - b.finish);
    

      4
      const chosen = [];
    

      5
      let lastFinish = -Infinity;        // finish time of the last job we took
    

      6
      for (const job of byFinish) {
    

      7
        // Compatible if it starts at or after the last chosen job ended
    

      8
        if (job.start >= lastFinish) {
    

      9
          chosen.push(job.name);         // safe greedy pick (exchange argument)
    

      10
          lastFinish = job.finish;       // advance the boundary
    

      11
        }
    

      12
      }
    

      13
      return chosen;
    

      14
      }

L3 Сортируй по времени завершения. Раньше всех завершающаяся первой это ровно тот выбор, который аргумент обмена доказал безопасным.
L5 lastFinish это стена: момент, когда завершилась ранее выбранная работа. Начинается с -Infinity, так что первая работа всегда подходит.
L8 Проверка совместимости: работа разрешена только если она начинается в момент или после того, как завершилась последняя (без пересечения).
L9 Берём её. По аргументу обмена, оптимальное расписание, содержащее эту совместимую работу, завершающуюся раньше всех, существует.
L10 Сдвигаем стену вперёд к времени завершения этой работы, потом продолжаем сканировать остальное.

Ключевой момент: доказательство это то, что позволяет тебе перестать думать

Код никогда не пересматривает выбор — нет отката, нет сравнения альтернатив. Эта уверенность целиком исходит из аргумента обмена: каждый выбор безопасен, так что единственный проход слева направо гарантированно оптимален. Без доказательства этот код был бы просто обнадёживающей эвристикой.

Запуск: жадный находит максимальное множество

Вывод

Жадный берёт A (завершается в 4), потом D (начинается в 5, после 4), потом H (начинается в 8, после 7), потом K (начинается в 12, после 11): четыре непересекающиеся работы. Никакое расписание не вмещает больше — аргумент обмена это причина, почему мы можем это утверждать без проверки каждого возможного подмножества.

Контраст: где обмена не существует

Тот же жадный «хватай самый большой подходящий кусок» работает для одних монетных систем и проваливается для других. Код ниже запускает жадный против истинного оптимума (найденного исчерпывающим динамическим программированием) для системы 4. Несовпадение это отпечаток отсутствующего обмена.

Вывод

Жадный использует 3 монеты (4 + 1 + 1); оптимум это 2 (3 + 3). Нет способа сдвинуть две тройки оптимума к четвёрке жадного не сломав его, так что аргумент обмена отказывается проходить — и алгоритм неправ. Техника доказательства корректно предсказывает провал.

Пошаговый разбор

Давай протрассируем сам аргумент обмена на выборе активностей. Мы начинаем с гипотетического оптимального расписания O, которое НЕ начинается с работы, завершающейся раньше всех, потом выполняем обмен и смотрим, как ничего не становится хуже. Работы: G=[0,3] (завершается раньше всех), X=[1,4], P=[4,6], Q=[6,9]. Предположим O = {X, P, Q} — три работы, оптимально — но оно пропустило G.


      1
      // Optimal O does not start with greedy's job G
    

      2
      O  = [ X , P , Q ]      // X finishes at 4
    

      3
      G.finish (3) <= X.finish (4)   // G finishes no later
    

      4
      swap: remove X, insert G
    

      5
      O' = [ G , P , Q ]      // still no overlaps?
    

      6
      count(O') == count(O)   // no worse

Сложность

Доказательство ничего не стоит во время выполнения

Аргумент обмена это рассуждение, которое ты делаешь один раз, на бумаге, перед тем как выпустить продукт. Оно не выполняется. Что выполняется, так это алгоритм, который оно обосновывает — и этот алгоритм дёшев именно потому, что доказательство убрало всякую необходимость пересматривать выбор.

Время выполнения выбора активностей: O(n log n)

sort jobs by finish time   ->  O(n log n)
single left-to-right scan  ->  O(n)
total                      ->  O(n log n), dominated by the sort

Есть n работ. Сортировка по времени завершения это единственный дорогой шаг с O(n log n); жадный проход посещает каждую работу раз, делая O(1) работы на работу (одно сравнение, может быть одно добавление), итого O(n). Всего получается O(n log n). Память это O(n) для отсортированной копии и списка выбранных, или O(1) дополнительно если ты сортируешь на месте и только считаешь результат.

Почему доказательство важно для стоимости

Сравни это с полным перебором: проверка каждого подмножества работ на самое большое непересекающееся это O(2^n). Аргумент обмена это то, что сворачивает этот экспоненциальный поиск в один отсортированный проход. Доказательство это не формальность — это вся причина, почему быстрому алгоритму позволено существовать. Жадное правило без допустимого обмена (как монеты 4) даёт быстрый неправильный ответ; доказательство это граница между быстро-и-корректно и быстро-и-неправильно.

Чтение стоимости провала

В монетном демо исчерпывающий DP optimalCoins работает за O(amount x coins) — мы использовали его только чтобы выявить ошибку жадного, а не как настоящий алгоритм. Урок там диагностический: когда жадный и заведомо корректный метод расходятся хотя бы на одном входе, аргумент обмена никогда и не собирался замкнуться, и ты должен использовать DP (или другой точный метод) вместо него.

Практика 0 / 7

Что аргумент обмена пытается доказать о жадном алгоритме?

В аргументе обмена, после того как ты обменял часть оптимального решения O к жадному выбору, какие два свойства должно иметь новое решение O'?

Для выбора активностей, почему замена первой работы X из O на жадную работу G держит расписание допустимым?

Жадный на монетной системе {1, 3, 4} делает размен 6. Что происходит, и что это выявляет?

Чем техника «жадный остаётся впереди» отличается от аргумента обмена?

Полное доказательство корректности жадного обычно имеет две части. Какие они?

Запусти жадный селектор активностей на 11 работах из примера кода. Сколько непересекающихся работ он выбирает?

Почему это работает

Почему «не хуже» вместо «строго лучше»? Аргументу обмена нужно только чтобы обменённое решение O' было так же хорошо как оптимум O, а не лучше. Если бы ты всегда мог сделать его строго лучше, то O не было оптимальным изначально — противоречие, которое нормально, но излишне. Честное утверждение мягче: жадный выбор никогда тебе ничего не стоит. Поскольку O было оптимально, а O' соответствует его значению, O' тоже оптимально и теперь содержит жадный выбор. «Не хуже» это ровно правильная сила: достаточно сильная, чтобы доказать безопасность, достаточно слабая, чтобы реально выполняться.

Частая ошибка

Ошибка: считать жадный правым, потому что он сработал на твоих примерах. Прохождение трёх тестовых входов не доказывает ничего об оптимальности — жадный на монетах 4 корректен для сумм от 1 до 5 и ломается только на 6. Жадная эвристика может быть права на тысяче входов и неправа на тысяче-первом. Единственный заслуживающий доверия вердикт исходит из доказательства (аргумента обмена или «остаётся впереди») или, когда никакое доказательство не замыкается, из контрпримера, который его опровергает. «Кажется, работает» это самое дорогое предположение в проектировании жадного.

Граничные случаи

Когда обмен безвреден, но выбор не жадный. У некоторых задач есть несколько оптимальных первых выборов — ничьи. Аргумент обмена всё равно работает: тебе нужно только одно оптимальное решение, которое согласуется с жадным, а не чтобы каждый оптимум согласовывался. В выборе активностей, если две работы завершаются в одно и то же раннее время, выбор любой безопасен, и обмен (G.finish <= X.finish) выполняется с равенством. Ничьи никогда не ломают аргумент; они просто означают, что у жадного было больше одного безопасного хода.

Ещё практика

Рецепт для доказательства жадного алгоритма. (1) Сформулируй жадное правило точно (например «время завершения раньше всех»). (2) Возьми произвольный оптимальный O; если он уже следует первому выбору правила, готово — иначе он отличается на первом шаге. (3) Спроектируй обмен: замени отличающуюся часть O на жадный выбор, чтобы получить O'. (4) Докажи, что O' допустимо и не хуже чем O. (5) Призови оптимальную подструктуру: рекурсируй на меньшей оставшейся задаче. Если шаг 3 или 4 не может быть выполнен, ищи контрпример вместо этого — жадный, вероятно, неправ. Попробуй этот рецепт на «спланируй работы чтобы минимизировать максимальное опоздание» далее.

Проверь себя

Викторина

Объясни аргумент обмена: что он доказывает, три хода, почему обмен в выборе активностей допустим, родственную технику «остаётся впереди», и что значит проваленный обмен.

Итог

Жадный алгоритм корректен только если его первый выбор безопасен, и аргумент обмена это как ты доказываешь безопасность.

Три хода:

Предположи произвольный оптимальный O, который отличается от жадного на первом выборе.
Обменяй отличающуюся часть O на жадный выбор, получив O', которое всё ещё допустимо и не хуже чем O.
Заключи, что O' оптимально и содержит жадный выбор — так что жадный первый выбор безопасен.

Направление, которое важно: ты не строишь ответ жадного из ничего; ты переформовываешь известный оптимум к нему, один безвредный обмен за раз.

Выбор активностей (выбери совместимую работу, завершающуюся раньше всех): обмен допустим, потому что G жадного завершается не позже чем первая работа X из O (G.finish <= X.finish), так что каждая поздняя работа всё ещё помещается и число никогда не падает. Время выполнения это O(n log n), в основном из-за сортировки по времени завершения.

Две половины полного доказательства: аргумент обмена (безопасный первый выбор) плюс оптимальная подструктура (остаток это меньший экземпляр), связанные вместе индукцией. Родственный «жадный остаётся впереди» доказывает то же самое, отслеживая одну величину и показывая, что жадный никогда не отстаёт.

Когда обмен проваливается, жадный неправ: монеты 4 для суммы 6 дают жадному 3 монеты (4+1+1) против оптимальных 2 (3+3). Безвредного обмена не существует, и этот отсутствующий обмен это доказательство, что жадный небезопасен — контрпример, а не ошибка в коде.

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

Продолжить восхождение ↑Планирование интервалов: выбор активностей и слияние интервалов