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

Коротко

Обменный аргумент - главный инструмент доказательства жадных алгоритмов. Схема одна и та же: возьми ЛЮБОЙ оптимальный ответ, найди в нём место, где он расходится с жадным, и покажи, что замена его элемента на наш НЕ УХУДШАЕТ ответ. Тогда существует оптимум, содержащий жадный выбор, - шаг безопасен, и дальше работает индукция. Второй способ, обычно проще в счётных задачах: жадный не отстаёт - доказать, что после каждого шага жадный ответ не хуже любого другого по выбранной мере. Оба доказательства короткие - пять-шесть строк, - и оба обязательны: без них жадный алгоритм остаётся догадкой.

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

Как думаешь, что доказывать

Соблазнительно доказывать так: «наш первый выбор - самый выгодный, значит ответ оптимален». Но это неверно даже по форме. На выборе занятий жадность берёт то, что заканчивается раньше всех, - и это занятие может быть вообще никаким: короткое, в неудобное время, в единственном оптимальном расписании его может не быть.

Значит доказывать надо не «наш выбор лучший». А что тогда? Подумай, какая формулировка была бы достаточна для индукции - и при этом выполнимой.

На что это похоже

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

Механизм: обменный аргумент по шагам

Сначала обозначения, они понадобятся во всех доказательствах раздела. Ответ - это МНОЖЕСТВО выбранных элементов; |O| значит «сколько элементов в O», x ∈ O - «x лежит в O», O − o + g - «взять O, убрать оттуда o, добавить g». Значок ∎ в конце означает «на этом доказательство закончено».

ЧТО ДОКАЗЫВАЕМ
    существует оптимальный ответ, СОДЕРЖАЩИЙ наш жадный выбор g
    (а не «g лучше всех» - это другое утверждение, и обычно ложное)

КАК
    1. пусть O - произвольный оптимальный ответ
    2. если g уже в O - доказывать нечего
    3. иначе найди в O элемент o, который «мешает» g
       (у занятий это первое по времени занятие в O)
    4. построй O' = O − o + g
    5. проверь ДВА пункта:
       а) O' по-прежнему ДОПУСТИМ (не нарушает правил задачи)
       б) O' не хуже O по целевой функции
    6. значит O' тоже оптимален и содержит g                  ∎

ВТОРОЙ СПОСОБ: «ЖАДНЫЙ НЕ ОТСТАЁТ» (greedy stays ahead)

    1. выбери МЕРУ, по которой сравниваешь частичные ответы
       (у занятий: время окончания k-го выбранного занятия)
    2. докажи индукцией по k: у жадного эта мера не хуже,
       чем у любого другого допустимого ответа
    3. из «не отстаёт на каждом шаге» следует «не хуже в конце»

когда удобнее: когда ответ - число (сколько элементов, сумма, длина),
а не множество, которое надо перестраивать

Правило

Обменный аргумент доказывает БЕЗОПАСНОСТЬ жадного шага: берём произвольный оптимальный ответ, заменяем в нём один элемент на жадный выбор и проверяем два пункта - что ответ остался допустимым и не стал хуже. Отсюда следует, что существует оптимум, содержащий наш выбор; вместе с оптимальностью подзадачи это даёт индукцию по шагам и оптимальность всего жадного ответа. Доказывать «наш выбор лучший» не надо и обычно нельзя. Альтернатива - «жадный не отстаёт»: выбрать меру частичного ответа и показать индукцией, что по этой мере жадный не хуже любого другого. Если ни одно из двух доказательств не проходит, скорее всего критерий неверен - ищи контрпример среди трёх-четырёх элементов.

Разбор: выбор занятий, доказательство обменом

Критерий: брать занятие с самым ранним КОНЦОМ среди совместимых с уже взятыми.

Утверждение. Пусть g - занятие с самым ранним концом среди всех.
Тогда существует оптимальное расписание, содержащее g.

Доказательство.
    Пусть O - любое оптимальное расписание, |O| = k.
    Если g ∈ O - готово.
    Иначе: отсортируем O по времени и возьмём o - ПЕРВОЕ занятие в O.
    Построим O' = O − o + g.

    (а) допустимость: конец g не позже конца o (g выбран как самый ранний
        по концу среди ВСЕХ занятий, значит и среди O). Остальные занятия O
        начинались не раньше конца o, значит и не раньше конца g -
        пересечений не возникло.
    (б) размер: |O'| = |O| = k - мы заменили одно занятие на одно.

    Значит O' - тоже оптимальное расписание, и g ∈ O'.                 ∎

Обрати внимание, какой именно элемент выбирается для обмена: ПЕРВЫЙ по времени в O. Это не случайность - именно он единственный может мешать g, потому что g заканчивается раньше всех. Если взять для обмена произвольное занятие, пункт (а) не пройдёт.

И сравни это с задачей про файлы из прошлого урока: там для обмена годился ЛЮБОЙ файл оптимума. Разница не в технике, а в задаче: у файлов мешает только суммарный размер, и замена на меньший файл безопасна всегда, а у занятий мешает пересечение по времени, и безопасна замена лишь одного, конкретного занятия. Выбор элемента для обмена - это и есть содержательная часть доказательства; техника одна, а что именно обменивать, каждый раз решается заново.

Вторая половина доказательства - оптимальность подзадачи, и она здесь почти очевидна: после взятия g остаются все занятия, начинающиеся не раньше конца g, и это задача ровно того же вида. Соединяем: по индукции жадный ответ оптимален для любого числа занятий.

цена алгоритма: сортировка по концу Θ(n·log n) + один проход Θ(n)

Разбор: то же, но способом «жадный не отстаёт»

Та же задача, другая техника. Мера: время окончания k-го по счёту выбранного занятия - чем раньше, тем лучше (тем больше места осталось).

Пусть g₁, g₂, ..., g_m - занятия, выбранные жадностью (в порядке выбора),
а o₁, o₂, ..., o_k - любое другое допустимое расписание, отсортированное по времени.

Утверждение (индукция по j): конец g_j <= конец o_j для всех j <= min(m, k).

База: g₁ - занятие с самым ранним концом среди ВСЕХ, значит и среди o₁.

Шаг: пусть конец g_j <= конец o_j. Занятие o_{j+1} начинается не раньше конца o_j,
     то есть не раньше конца g_j - значит оно БЫЛО ДОСТУПНО жадности на шаге j+1.
     Жадность берёт самое раннее по концу из доступных, поэтому
     конец g_{j+1} <= конец o_{j+1}.

Теперь пусть k > m, то есть чужое расписание ДЛИННЕЕ. Тогда o_{m+1}
начинается не раньше конца o_m >= конца g_m - значит оно было доступно
жадности после g_m, и жадность не остановилась бы на m занятиях.
Противоречие. Значит k <= m: жадный ответ не короче любого другого.    ∎

Два доказательства одной теоремы - и это не упражнение ради упражнения. Обменный аргумент удобнее, когда ответ - МНОЖЕСТВО и его можно перестраивать; «не отстаёт» - когда ответ измеряется числом и шаги сравниваются напрямую. В следующей главе пригодятся оба: у расписаний со штрафами естественнее обмен, у кода Хаффмана - тоже обмен, но с перестановкой листьев дерева.

Что ломается без этого

Первое: доказывать «наш выбор самый выгодный» - утверждение и неверное, и недостаточное. Второе: обменять не тот элемент: в доказательстве про занятия годится только ПЕРВОЕ по времени занятие оптимума, иначе допустимость не сохранится. Третье: забыть пункт (а): «размер не изменился» без проверки допустимости не доказывает ничего - можно «улучшить» ответ до недопустимого. Четвёртое: доказать безопасность первого шага и решить, что всё готово: нужна ещё оптимальность подзадачи, то есть что после шага задача того же вида. Пятое: в способе «не отстаёт» выбрать меру, по которой жадный на самом деле отстаёт, и не заметить этого: мера должна быть такой, чтобы из неё следовал ответ (здесь - время окончания, а не, скажем, суммарная длина занятий).

Зачем это в работе

Пять строк доказательства - это то, что отличает «я написал сортировку и проход» от «я знаю, что этот ответ оптимален». На практике полное доказательство пишут редко, но ПРОВЕРКУ обменом делают постоянно, в уме: «а если в идеальном ответе этого элемента нет - смогу я его туда вставить, выкинув один чужой?» Если ответ «нет» или «не знаю» - критерий под подозрением, и дальше либо ищешь контрпример, либо меняешь критерий, либо честно объявляешь алгоритм приближённым. Та же техника работает и в обратную сторону - как инструмент поиска контрпримера: место, где обмен не проходит, обычно и подсказывает, как построить плохой вход. И ещё одно: обменный аргумент уже встречался в курсе. Свойство разреза для минимального остовного дерева (раздел 11) доказывается ровно так: берём любое оптимальное дерево, добавляем наше ребро, выкидываем из образовавшегося цикла ребро не меньшего веса.

Теперь сам

Задача: n задач со временем выполнения t₁ ... tₙ, один процессор. Порядок выбираем мы. Минимизировать СУММУ времён завершения. Жадный критерий - по возрастанию времени выполнения. Докажи обменом, что он оптимален.

Ответ. Пусть O - оптимальный порядок, и в нём есть пара СОСЕДНИХ задач i, j (i раньше j), у которых t_i > t_j. Поменяем их местами.

было:   ... | задача i (t_i) | задача j (t_j) | ...
стало:  ... | задача j (t_j) | задача i (t_i) | ...

пусть до пары прошло время S.
было:   завершения пары  (S + t_i) + (S + t_i + t_j)  = 2S + 2t_i + t_j
стало:  завершения пары  (S + t_j) + (S + t_j + t_i)  = 2S + 2t_j + t_i

разница (было − стало) = 2t_i + t_j − 2t_j − t_i = t_i − t_j > 0

значит после обмена сумма СТРОГО МЕНЬШЕ

Остальные задачи не затронуты: время завершения всех, кто до пары, не изменилось, а всех, кто после, зависит только от суммы t_i + t_j, которая та же. Получили порядок строго лучше оптимального - противоречие. Значит в оптимальном порядке нет соседней пары «длинная раньше короткой», а это и есть порядок по возрастанию.

Заметь, что здесь обмен применён иначе: не «вставим наш элемент в оптимум», а «в оптимуме нет плохой пары соседей». Это разновидность того же аргумента, которую называют обменом соседних элементов, и она особенно удобна, когда ответ - ПОРЯДОК, а не множество. Та же выкладка - основа правила «короткие задачи вперёд», по которому планируют очереди и в операционных системах, и в сервисных центрах.

Главное

Безопасность жадного шага доказывают ОБМЕНОМ: берут произвольный оптимальный ответ O, находят в нём элемент, мешающий жадному выбору g, строят O' = O − o + g и проверяют два пункта - допустимость O' и что он не хуже O. Отсюда: существует оптимум, содержащий g. Для занятий обменивают именно ПЕРВОЕ по времени занятие оптимума, и именно потому, что g заканчивается раньше всех. Вариант для задач, где ответ - порядок: показать, что в оптимуме нет «плохой пары соседей» (так доказывается «короткие задачи вперёд»). Альтернативная техника - «жадный не отстаёт»: выбрать меру частичного ответа и индукцией показать, что жадный по ней не хуже любого другого. Доказательства короткие, но обязательные: без них жадный алгоритм - догадка, а не алгоритм.