Жадный алгоритм: решение, которое никогда не пересматривают

Коротко

Жадный алгоритм строит ответ по шагам и на каждом берёт то, что выглядит лучшим ПРЯМО СЕЙЧАС, после чего решение не пересматривает. Это самый дешёвый приём из всех - обычно сортировка плюс один проход, - и самый опасный: НЕВЕРНЫЙ критерий ошибается не на всех входах, а только на некоторых, и потому легко проходит тесты. Верные жадные алгоритмы есть, и их немало (половина этого раздела о них), но каждый верен со своим доказательством. Поэтому у жадного алгоритма ДВЕ части: сам код (пять строк) и ДОКАЗАТЕЛЬСТВО того, что локальный выбор не портит будущее. Без второй части алгоритм не готов, сколько бы примеров ни прошло. Доказывать нужно два свойства: безопасность жадного шага (существует оптимальный ответ, содержащий наш первый выбор) и оптимальность подзадачи (после шага остаётся задача того же вида).

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

Как думаешь, сколько монет

Монеты 1, 5, 10, 25. Нужно набрать 30 рублей минимальным числом монет. Берём самую крупную, какая влезает: 25, потом 5 - две монеты, и это оптимум.

Теперь монеты 1, 3, 4 и сумма 6. Тот же способ: 4, потом 1, потом 1 - три монеты. А оптимум - 3 + 3, то есть две. Код не изменился ни на строку, изменились только данные. Вопрос: как понять ЗАРАНЕЕ, на каком наборе данных жадность сломается?

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

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

Механизм: из чего состоит жадный алгоритм

Сразу об одном соглашении, без которого все числа в уроке читались бы по-разному: занятие (1, 4) и занятие (4, 7) НЕ ПЕРЕСЕКАЮТСЯ - одно заканчивается ровно тогда, когда другое начинается. Условие совместимости поэтому нестрогое: начало >= конец предыдущего. И второе соглашение: при равных значениях критерия берём любое из подходящих - на ответ это не влияет, а проверить легко перебором.

СХЕМА

1. задать КРИТЕРИЙ: по какому признаку выбирать следующий элемент
2. отсортировать по этому критерию                    обычно Θ(n·log n)
3. идти по порядку и брать всё, что не противоречит уже взятому   Θ(n)
4. решение не пересматривать НИКОГДА

итого: сортировка плюс проход. Это самая дешёвая схема в курсе

ЧТО НАДО ДОКАЗАТЬ - ДВА СВОЙСТВА

1. БЕЗОПАСНОСТЬ ЖАДНОГО ШАГА (greedy choice property)
   существует ОПТИМАЛЬНЫЙ ответ, содержащий наш первый выбор
   не «наш выбор оптимален», а «он не мешает быть оптимальным»

2. ОПТИМАЛЬНОСТЬ ПОДЗАДАЧИ (optimal substructure)
   после жадного шага остаётся задача ТОГО ЖЕ ВИДА,
   и её оптимальное решение вместе с нашим шагом даёт оптимум целого

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

ЧЕГО ДОКАЗЫВАТЬ НЕ НАДО (и почему этого недостаточно)

- «я прогнал сто случайных тестов»   контрпример может быть редким
- «на всех примерах из учебника»     примеры подбирал автор учебника
- «интуитивно понятно»               монеты 1, 3, 4 тоже «интуитивно понятны»

Правило

Жадный алгоритм строит ответ по шагам, на каждом берёт локально лучшее по заданному критерию и никогда не пересматривает выбор. Цена - сортировка плюс проход, то есть Θ(n·log n). Правильность НЕ следует из дешевизны: её доказывают двумя свойствами - безопасностью жадного шага (существует оптимальный ответ, содержащий первый выбор) и оптимальностью подзадачи (после шага задача того же вида). Смена критерия меняет алгоритм целиком: «самый длинный», «самый ранний», «самый дешёвый» - это три разных алгоритма с тремя разными доказательствами, и верным может оказаться один из них. Если доказательство не выходит - ищи контрпример на маленьких данных: обычно он есть и короткий.

Разбор: один критерий верен, другой нет

Задача: дано n занятий со временем начала и конца; выбрать как можно БОЛЬШЕ занятий, которые не пересекаются по времени. Классика, у неё есть и жизненный смысл: расписание одной переговорной.

Попробуем три критерия на одних и тех же данных.

занятия (начало, конец):
A (1, 4)   B (3, 5)   C (0, 6)   D (5, 7)   E (3, 9)   F (5, 9)
G (6, 10)  H (8, 11)  I (8, 12)  J (2, 14)  K (12, 16)

КРИТЕРИЙ 1: самое раннее НАЧАЛО
берём C (0,6) - оно начинается раньше всех
дальше всё, что начинается НЕ РАНЬШЕ 6: первое такое G (6,10), затем K (12,16)
получили 3 занятия: C, G, K

КРИТЕРИЙ 2: самое КОРОТКОЕ занятие
короче всех сразу два: B (3,5) и D (5,7), длина 2 у обоих - берём любое,
пусть B. Дальше по длине: D (5,7) совместимо, берём
затем H (8,11), затем K (12,16)
получили 4 занятия: B, D, H, K

КРИТЕРИЙ 3: самый ранний КОНЕЦ
A (1,4) → D (5,7) → H (8,11) → K (12,16)
получили 4 занятия: A, D, H, K

Критерий «раннее начало» уже проиграл: занятие C (0,6) заняло полдня, и в итоге выбрано три занятия вместо четырёх - потеря одна, но она есть. Критерии 2 и 3 дали одинаковое ЧИСЛО занятий, хотя сами наборы разные (B, D, H, K против A, D, H, K), - и это ровно та ситуация, где останавливаться опасно. Совпадение на одном наборе данных ничего не значит; надо искать, где критерии расходятся.

Для критерия «раннее начало» хватает и трёх занятий:

A (0, 10)   B (1, 3)   C (4, 6)

раннее начало: берём A (0,10) - и всё, остальные с ним пересекаются  → 1 занятие
ранний конец:  B (1,3), затем C (4,6)                                → 2 занятия

контрпример против «самого короткого»:
    P (0, 5)   Q (4, 6)   R (5, 10)

самое короткое - Q (4,6), длина 2. Взяли Q - и P, и R
теперь невозможны: оба пересекаются с Q. Ответ 1 занятие

по раннему концу: P (0,5), затем R (5,10). Ответ 2 занятия

Короткое занятие, стоящее на стыке двух длинных, рушит критерий 2. Против критерия 3 такого контрпримера не существует, и это не «не нашлось», а доказано - доказательством из следующего урока.

Разбор: почему монеты ломаются, а на наших монетах нет

Вернёмся к монетам. Почему на наборе 1, 5, 10, 25 жадность верна, а на 1, 3, 4 - нет?

1, 5, 10, 25:  жадность оптимальна - проверено для ВСЕХ сумм до 1000
               перебором через динамику: ни одного расхождения.
               Это свойство конкретного набора, а не общее правило

1, 3, 4:       4 > 3, но 6 = 3 + 3 набирается двумя тройками,
               а взятая четвёрка оставляет 2 = 1 + 1
               жадный шаг НЕ БЕЗОПАСЕН: оптимального ответа с четвёркой нет
               и это не единичный случай: до суммы 100 жадность ошибается
               24 раза (6, 10, 14, 18, ... - через каждые четыре)

Вот и ответ на вопрос из начала урока. Жадность ломается там, где взятый элемент НЕ ВХОДИТ ни в один оптимальный ответ. Значит проверять надо именно это свойство, а не «кажется ли выбор разумным».

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

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

Первое: считать, что жадный алгоритм верен, потому что он прошёл тесты. Контрпример к неверному критерию обычно состоит из трёх-четырёх элементов, и случайные тесты его почти никогда не содержат - его надо строить руками или перебором всех маленьких случаев. Второе: доказывать не то утверждение: «наш выбор - самый выгодный» звучит похоже на безопасность шага, но это другое и вообще неверно; доказывать надо «существует оптимум, содержащий наш выбор». Третье: забыть про вторую половину - оптимальность подзадачи: бывает, что шаг безопасен, а после него задача МЕНЯЕТ ВИД, и индукция не работает. Четвёртое: брать критерий «по интуиции», не проверив соседние: «самое короткое» и «самый ранний конец» выглядят одинаково разумно, а верен только второй. Пятое: применять жадность там, где нужна точность, вместо того чтобы признать её ПРИБЛИЖЁННЫМ алгоритмом с оценкой качества - для многих NP-трудных задач это честный и правильный выбор.

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

Жадные алгоритмы - самый часто встречающийся приём в прикладном коде, потому что они проще всего пишутся и быстрее всего работают. Планировщик задач берёт следующую по приоритету; балансировщик отдаёт запрос наименее загруженному серверу; аллокатор выбирает первый подходящий блок памяти; кеш вытесняет давно не использованную запись. Во всех этих местах жадность - не доказанный оптимум, а осознанный компромисс: решение принимается без знания будущего, и о его качестве говорят отдельно («не хуже оптимума вдвое», «на реальной нагрузке близко к идеалу»). Главный профессиональный навык здесь - не написать жадный алгоритм, а честно сказать, доказан он или взят как приближение. Самая дорогая ошибка в этой теме выглядит так: кто-то написал пять строк, проверил на своих данных и объявил задачу решённой; через год данные поменялись, и ответ стал тихо неоптимальным - без падений, без ошибок, просто хуже.

Теперь сам

Задача: есть n файлов размеров s₁ ... sₙ и диск ёмкости C. Надо записать на диск КАК МОЖНО БОЛЬШЕ файлов. Предложи жадный критерий и скажи, доказуем ли он.

Ответ. Критерий: брать файлы по возрастанию размера, пока очередной влезает.

Здесь жадность оптимальна, и безопасность шага доказывается в одну строку. Пусть оптимальный ответ содержит k файлов. Если k = 0, доказывать нечего (тогда и s_min не влезает). Пусть k >= 1 и самый маленький файл s_min в оптимум не входит. Выкинем из оптимума ЛЮБОЙ файл - он не меньше s_min, потому что s_min наименьший из всех, - и добавим s_min. Суммарный размер не вырос (мы заменили файл на не больший, значит он по-прежнему не превосходит C), число файлов осталось k. Значит существует оптимум из k файлов, содержащий s_min, - жадный шаг безопасен.

Дальше ИНДУКЦИЯ, и стоит проговорить её один раз подробно, потому что дальше в разделе она будет встречаться постоянно. После того как s_min взят, остаётся та же задача: файлы без s_min и ёмкость C − s_min. По предположению индукции для неё жадность даёт оптимум - скажем, m файлов. Вместе с нашим шагом это m + 1 файл. А больше m + 1 быть не может: иначе, выкинув s_min из такого ответа, мы получили бы для меньшей задачи больше m файлов - противоречие с предположением. База индукции - пустой набор файлов, где ответ ноль.

пример: C = 10, файлы 7, 3, 2, 8
по возрастанию 2, 3, 7, 8:
    2 влезает   (занято 2)
    3 влезает   (занято 5)
    7 не влезает (5 + 7 = 12 > 10)
    8 не влезает
ответ: 2 файла

перебор подтверждает: трёх не выйдет (самые маленькие 2 + 3 + 7 = 12 > 10),
а двойки набираются и иначе - 7 + 3 = 10, 2 + 8 = 10

А теперь важное: измени цель на «записать как можно БОЛЬШЕ БАЙТ» - и тот же критерий станет неверным. Это уже третий раз в уроке, когда ответ зависит не от данных, а от формулировки цели. На C = 10 и файлах 7, 6, 5 возрастание даёт 5 + ... - больше ничего не влезает, итого 5 байт, а оптимум - 7. Это задача о рюкзаке, и жадность в ней не работает: одна и та же постановка «влезает - не влезает» с другой целевой функцией переходит из жадности в динамическое программирование.

Главное

Жадный алгоритм строит ответ по шагам, берёт локально лучшее по критерию и никогда не пересматривает выбор - это сортировка плюс проход, Θ(n·log n). Правильность надо ДОКАЗЫВАТЬ двумя свойствами: безопасность жадного шага (существует оптимальный ответ, содержащий наш первый выбор - не «наш выбор лучший») и оптимальность подзадачи (после шага остаётся задача того же вида). Из них по индукции следует оптимальность всего ответа. Критерий - это и есть алгоритм: на выборе занятий «самый ранний конец» верен, а «самое короткое» ломается на (0,5), (4,6), (5,10) и «самое раннее начало» - на (0,10), (1,3), (4,6), то есть обоим хватает трёх занятий. Прогон тестов доказательством не является: контрпример обычно крошечный и случайными данными не находится. Если доказать не удаётся, жадность годится как ПРИБЛИЖЁННЫЙ алгоритм - но тогда нужна оценка качества.