Где жадность ломается и как это выяснить за пять минут

Коротко

Проверять критерий надо ДО того, как писать доказательство: обычно он неверен, и контрпример короткий. Самый быстрый способ - перебор всех маленьких случаев: написать тупой точный алгоритм, прогнать его против жадного на всех входах до пяти-шести элементов и посмотреть на первое расхождение. Типовые места провала: целый рюкзак (он же «рюкзак 0/1» - предмет берут либо целиком, либо никак; его дробный родственник жадности поддаётся), сдача монетами произвольного набора, вершинное покрытие, раскраска графа, задачи, где взятый элемент меняет ПРАВИЛА для остальных. И отдельный случай: жадность неверна, но даёт гарантированно неплохой ответ - тогда её берут как приближённый алгоритм с оценкой.

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

Как думаешь, с чего начинать

Есть задача, есть идея жадного критерия. Что делать первым: доказывать или искать контрпример?

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

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

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

Механизм: искать контрпример перебором

РЕЦЕПТ (работает почти всегда)

1. написать ТОЧНЫЙ алгоритм - любой, можно экспоненциальный:
   перебор всех подмножеств, всех перестановок, рекурсия с возвратом
2. написать жадный
3. перебрать ВСЕ входы маленького размера. «Маленький» - это буквально
   один-пять элементов, а диапазон значений - от 1 до 5-6.
   Если элемент составной (пара «начало-конец», «вес-цена»), перебираются
   все комбинации его частей: для трёх занятий со временем из 0..5 это
   6⁴ = 1296 вариантов на одно занятие, что для перебора пустяк
4. на первом расхождении остановиться и посмотреть на вход глазами
5. минимизировать контрпример: убирать элементы, пока расхождение держится

ПОЧЕМУ МАЛЕНЬКИЕ ВХОДЫ

контрпримеры к жадности почти всегда крошечные: монеты 1, 3, 4 и сумма 6;
три занятия P(0,5) Q(4,6) R(5,10); рюкзак из трёх предметов.
Причина простая: плохой случай - это «локально лучший элемент мешает
двум другим», а для такой конфигурации хватает трёх элементов

ТИПОВЫЕ МЕСТА, ГДЕ ЖАДНОСТЬ ЛОМАЕТСЯ

рюкзак 0/1          предмет либо берём целиком, либо нет
сдача монетами      произвольный набор номиналов
вершинное покрытие  «брать вершину с максимальной степенью» - неверно
раскраска графа     жадная раскраска зависит от порядка вершин
задачи с ресурсом   взятый элемент меняет ПРАВИЛА для остальных,
                    а не только уменьшает запас

Правило

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

Разбор: рюкзак дробный и целый - одна задача, два исхода

Задача: предметы с весами и ценами, рюкзак вместимости C, максимизировать суммарную цену.

предметы:  A: вес 10, цена 60    удельная цена 6
           B: вес 20, цена 100   удельная цена 5
           C: вес 30, цена 120   удельная цена 4
вместимость C = 50

Дробный рюкзак (предмет можно взять частями - песок, бензин, время):

жадность: по убыванию УДЕЛЬНОЙ цены
A целиком: вес 10, цена 60            (осталось 40)
B целиком: вес 20, цена 100           (осталось 20)
C на 20/30: вес 20, цена 120·2/3 = 80
итого: 240

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

Целый рюкзак (предмет только целиком):

та же жадность по удельной цене:
A (10, 60) → B (20, 100) → C не влезает (осталось 20 < 30)
итого вес 30, цена 160

а перебор даёт: B + C = вес 50, цена 220

Жадность ошиблась на 27% от оптимума (60 из 220). И разница между двумя задачами - одно слово «целиком». Почему оно всё меняет: в дробном рюкзаке взятый килограмм только уменьшает ЗАПАС, и остаток - такая же задача. В целом он ещё и запрещает некоторые комбинации: после A вместимость 40, и предметы 20 и 30 вместе уже не влезают, хотя по отдельности каждый влез бы. Правила для остальных изменились - это и есть признак из «Правила» выше.

дробный рюкзак:  жадность, Θ(n·log n)
целый рюкзак:    динамическое программирование, Θ(n·C)   - раздел 15

Разбор: где у жадности есть ГАРАНТИЯ

Бывает, что точного жадного алгоритма нет, а приближённый с доказанной оценкой - есть, и это практически лучший выбор. Два примера, оба про NP-трудные задачи.

ПОКРЫТИЕ МНОЖЕСТВ: выбрать как можно меньше множеств, чтобы накрыть все элементы
    жадность: каждый раз брать множество, накрывающее больше всего НЕНАКРЫТЫХ
    гарантия: не более чем в H(n) = 1 + 1/2 + ... + 1/n раз хуже оптимума,
    а H(n) = ln n + O(1), поэтому её и называют «порядка ln n»
    (n - число элементов, которые надо накрыть)
    и эта оценка ПОЧТИ НЕУЛУЧШАЕМА: лучшего отношения не даёт ни один
    полиномиальный алгоритм (если верна гипотеза P ≠ NP)

ВЕРШИННОЕ ПОКРЫТИЕ: выбрать как можно меньше вершин, чтобы накрыть все рёбра
    «жадность по максимальной степени» - НЕ ОПТИМАЛЬНА; гарантия у неё есть,
    но слабая: это частный случай покрытия множеств, то есть порядка ln n
    а вот другой приём даёт двойку: пока есть НЕПОКРЫТЫЕ рёбра, брать любое
    из них и класть в ответ ОБА его конца
    гарантия 2: взятые рёбра попарно не имеют общих вершин (каждое следующее
    берётся из непокрытых), значит в любом покрытии есть хотя бы по одной
    вершине из каждого - оптимум не меньше их числа, а мы взяли ровно вдвое

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

Два слова о терминах, которые в уроке уже встречались. Задача называется NP-ТРУДНОЙ, если быстрого (полиномиального - то есть со временем вида n^k) алгоритма для неё не знает никто, и есть веские основания считать, что его не существует; P ≠ NP - это как раз гипотеза о том, что такого алгоритма нет. ПРИБЛИЖЁННЫЙ алгоритм - быстрый алгоритм, который даёт не оптимум, а ответ с доказанной границей отклонения. ЦЕЛЕВАЯ ФУНКЦИЯ - то, что мы максимизируем или минимизируем («число занятий», «суммарная цена»).

Такие алгоритмы называют c-приближёнными, где c - гарантированное отношение к оптимуму. Для вершинного покрытия c = 2, для покрытия множеств c = ln n. Фраза «жадный алгоритм с гарантией 2» означает именно это, а не «обычно ошибается вдвое»: это ГРАНИЦА сверху для худшего случая, а на реальных данных ошибка обычно куда меньше.

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

Первое: начинать с доказательства неверного утверждения - можно потратить вечер и ничего не понять, хотя контрпример из трёх элементов лежал рядом. Второе: искать контрпример случайными данными: плохие конфигурации редки, и генератор их не находит - перебирать нужно ВСЕ маленькие входы. Третье: найти расхождение и не минимизировать его: разбираться в контрпримере из двадцати элементов больно, а он почти всегда сжимается до трёх. Четвёртое: путать дробную и целую постановку: формулировки отличаются одним словом, а алгоритмы - разные разделы курса. Пятое: объявлять приближённый алгоритм точным: «на наших данных совпадает с перебором» - это не гарантия, а наблюдение на одном наборе данных. Шестое: считать, что раз задача NP-трудна, то и думать не о чем: разница между алгоритмом без гарантий и алгоритмом с гарантией 2 - это разница между «иногда очень плохо» и «никогда хуже чем вдвое».

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

Перебор маленьких случаев против быстрого алгоритма - это рабочий приём, который называют тестированием на основе модели (или сравнением с эталонной реализацией): пишешь заведомо правильный медленный вариант, прогоняешь оба на всех входах до какого-то размера и сравниваешь. Он находит не только неверные критерии, но и обычные ошибки в коде, причём на минимальных примерах, которые можно прочитать глазами. В боевом коде таким способом проверяют планировщики, биллинг, правила скидок - везде, где «оптимальность» написана в требованиях. Вторая половина урока - про язык, на котором обсуждают приближённые решения: если задача NP-трудна (а это узнаётся по формулировке: рюкзак, покрытие, раскраска, маршрут коммивояжёра), разговор идёт не «точно или нет», а «какая гарантия и какая цена». Умение сказать «вот жадность с гарантией двойки, вот динамика за n·C, вот точный перебор - выбирай» и есть профессиональный ответ.

Теперь сам

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

Ответ. Не сработает, и контрпример из двух занятий.

занятия (начало, конец, ценность):
    A (0, 2, ценность 1)
    B (1, 10, ценность 100)

«самый ранний конец»: берём A (конец 2), затем B недоступно (начинается в 1)
получили ценность 1

оптимум: взять только B - ценность 100

Критерий, оптимальный для числа занятий, оказался произвольно плохим для суммы ценностей: отношение ответов здесь 1 к 100, и его можно сделать любым. Причина ровно та, что в «Правиле»: мера изменилась, а значит изменилась и задача - жадность про «сколько штук» ничего не знает про «сколько стоит».

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

Главное

Сначала контрпример, потом доказательство: неверный критерий ловится перебором всех входов до пяти-шести элементов (точный алгоритм любой сложности против жадного, первое расхождение минимизировать руками), а доказывать ложное утверждение можно бесконечно. Контрпримеры к жадности крошечные - обычно три элемента, потому что нужна конфигурация «локально лучший мешает двум другим». Признак провала: взятый элемент меняет не только запас ресурса, но и ПРАВИЛА для остальных - так целый рюкзак отличается от дробного (240 против 160/220 на одних данных), а взвешенный выбор занятий от невзвешенного. Если точного жадного нет, жадность берут как приближённый алгоритм с ДОКАЗАННОЙ оценкой: покрытие множеств - ln n (и лучше нельзя), вершинное покрытие - 2 (но не жадностью по степени, а взятием обоих концов ребра). «Гарантия 2» - это граница худшего случая, а не типичная ошибка.