Жадные алгоритмы

В 675 деревень и городов Южной Моравии нужно провести связь. Вышка, поставленная в населённом пункте, накрывает всё в радиусе десяти километров. Сколько вышек нужно? Напрашивается жадный способ: ставить следующую вышку туда, где она накроет больше всего ещё не накрытых пунктов. Он быстрый, понятный и почти никогда не попадает в лучший ответ. Ниже — жадность против точного оптимума, который заранее нашёл решатель целочисленного программирования.

При радиусе 10 км жадность ставит 40 вышек, а хватило бы 29: она хуже в 1,38 раза. При 20 км — 13 вышек вместо 9. Первые жадные вышки стоят там, где много мелких деревень рядом, а не у Брно: функция считает пункты, а не жителей. Каждый шаг жадности был разумным, а итог — нет. Это типичная история, и всё искусство жадных алгоритмов — понимать, в каких задачах она всё-таки кончается хорошо.

Идея

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

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

Когда права: обменный аргумент

У типографии один станок и восемь заказов. Каждый занимает станок на несколько часов и обещан к определённому часу. Заказ, сделанный позже срока, опаздывает; хочется, чтобы самое большое опоздание было как можно меньше. Попробуйте разные порядки и правила:

«Как пришли» опаздывает на 10 часов, «короткие сначала» — на 7, «по сроку» — на 3. Перебор всех 40 320 порядков в листинге ниже подтверждает: меньше трёх часов не бывает. Правило «сначала то, у чего срок раньше» придумал Джеймс Джексон в 1955 году, и оно верно для любых заказов.

Это и есть обменный аргумент: любое решение по шагам превращается в жадное, и ни один шаг его не портит. Нажимайте в сцене «Обмен» и следите за числом: оно не растёт никогда. А правило «короткие сначала» обменом не доказать — и сцена показывает, что оно и неверно.

Второй способ доказать жадность — показать, что её ответ совпал с нижней границей. Так решается задача о залах: если в какой-то момент идут d встреч одновременно, меньше d залов не бывает, а жадная раскладка по моменту начала открывает новый зал, только когда все открытые заняты, то есть ровно в такой момент. Подробно — в первой задаче статьи.

Когда врёт: монеты

Жадная сдача — каждый раз самая крупная монета, которая помещается. С монетами тенге она всегда даёт наименьшее число монет, а стоит добавить в кошелёк монету 25, и сумма 40 выдаётся как 25 + 10 + 5 вместо 20 + 20. Наборы монет, на которых жадность всегда права, называют каноническими. Проверьте любой свой набор:

Проверять все суммы до бесконечности не нужно. В 1994 году Декстер Козен и Шмуэль Закс доказали: если жадность где-то ошибается, то уже на сумме меньше двух крупнейших монет, сложенных вместе. Поэтому сцена проверяет только суммы до этой границы, сравнивая жадность с динамикой, — и если там всё совпало, ответ «права всегда» доказан. В 2005 году Дэвид Пирсон нашёл проверку ещё быстрее — за число шагов, кубическое по числу номиналов, а не по их величине.

Когда почти права: покрытие

Вернёмся к вышкам. Задача о покрытии множествами NP-трудна: быстрого точного алгоритма для неё не знают, а решатель из сцены просто перебирает умно и не всегда успевает. Зато про жадность можно сказать, насколько она хуже.

Для 10 км самая богатая вышка накрывает 57 пунктов, и гарантия — H(57) ≈ 4,6. На настоящих данных жадность хуже всего в 1,38 раза: гарантия описывает самый плохой случай, а не обычный. Но и лучше гарантии в общем случае не придумать: Ури Файги в 1998 году показал, а Ирит Динур и Давид Штойрер в 2014 году окончательно доказали, что если P ≠ NP, ни один быстрый алгоритм не даёт покрытия, которое всегда меньше чем в (1 − ε) ln n раз хуже оптимума.

Когда права всегда: матроиды

Есть класс задач, где жадность права при любых весах: выбрать набор элементов наибольшего веса при условии «набор независим». Если у независимых наборов два свойства — подмножество независимого независимо, и из меньшего независимого набора всегда можно дорасти до большего, взяв элемент из него, — жадность «бери самый тяжёлый, если не ломает независимость» оптимальна. Такие системы называют матроидами. Леса в графе — матроид, и поэтому жадный Краскал строит минимальное остовное дерево. Линейно независимые векторы — матроид. Набор монет — нет, рюкзак — нет, и там жадность врёт. Обратное тоже верно: если жадность права при любых весах, система — матроид (Радо, 1957; Эдмондс, 1971).

Код

Типография: три правила и проверка перебором всех порядков.

Проверка монетной системы по границе Козена и Закса: жадность против динамики на всех суммах ниже двух крупнейших монет.

Вышки над Моравией: жадное покрытие для четырёх радиусов и сравнение с оптимумом, который посчитан заранее и лежит в данных, — программа проверяет, что он действительно накрывает все пункты.

Сколько это стоит

Жадные алгоритмы обычно быстрые: сортировка или куча и один проход — O(n log n). Порядок по сроку — сортировка. Залы — сортировка и куча. Жадное покрытие напрямую дороже: на каждом шаге пересчитать выгоду каждой вышки, O(k·n²) для k вышек и n пунктов, но для 675 пунктов это доли секунды. Решатель, который нашёл оптимум, на тех же данных думал секунды, а на задачах побольше может думать годами — в этом и цена точности.

Главная стоимость жадности не во времени, а в доказательстве. Жадный алгоритм почти всегда легко придумать и написать, и почти всегда легко ошибиться. Прежде чем верить жадности, ищите контрпример на маленьких входах перебором — как делает сцена с монетами.

Задачи

В первой жадность права, и это доказывает нижняя граница; среди тестов — дежурства на всех землетрясениях каталога USGS. Во второй жадность надо поправить: решать, где остановиться, не на станции, а потом, когда кончится бензин.