TM·IX Пределы вычислений Глава 58 из 65
Экспедиция коммивояжёра
Соревнование по старым правилам конкурса 1962 года: кратчайший объезд тридцати трёх городов. Сначала маршрут прокладываете вы, потом на старт выходят алгоритмы — жадный, дерево, 2-opt, отжиг, эволюция, — а в конце судья доказывает, кто ближе всех подошёл к оптимуму. А ещё судоку и пифагоровы тройки, которые решает SAT-решатель.
Пределы вычислений
- 54 Автоматы
- 55 Машина Тьюринга
- 56 Неразрешимое
- 57 P и NP
- 58 Трудные задачи вы здесь
Опирается на: 57 · Письмо Гёделя 23 · Жадность и электричество 26 · Подбросим монетку
Что вы унесёте из главы
- строить хорошие решения трудных задач: жадный старт, 2-opt, имитация отжига
- понимать, насколько решение хуже оптимума: приближённые алгоритмы с гарантией и нижние границы
- отдавать задачу готовым инструментам: SAT-решателям и целочисленному программированию
Прошлая глава кончилась вопросом. Задачи о маршрутах, расписаниях и раскрое NP-трудны, и большинство специалистов уверены, что быстрого точного алгоритма для них нет. А логисты каждый день решают их для тысяч машин. Для этого приходится пожертвовать одним из трёх требований: точностью, гарантией или худшим случаем. Приближённый алгоритм довольствуется почти лучшим маршрутом. Эвристика ничего не обещает заранее, но на практике выходит почти на оптимум. Точный решатель доводит дело до конца на входах, которые встречаются в жизни, хоть и не на любых. Каждая такая уступка даёт свой инструмент, и мы испытаем их все на одной задаче, устроив соревнование.
1962. Конкурс на десять тысяч долларов
Устроим свой конкурс по тем же правилам. Тридцать три города у нас будут моравские: самые населённые города и посёлки Южноморавского края, где в главе 23 мы тянули провода по остовному дереву. Расстояния — по прямой. Первый участник — вы.
Задачу о кратчайшем объезде называют задачей коммивояжёра: так в старых учебниках называли разъездного торговца. Вариант «есть ли объезд не длиннее $L$» NP-полон: в прошлой главе к нему свелась рассадка гостей. Сама задача найти кратчайший — NP-трудна. У нас расстояния обычные, по прямой, и для них выполняется неравенство треугольника: дорога из A в C напрямую не длиннее, чем через B. На этом неравенстве держатся почти все гарантии ниже.
Посчитаем, сколько всего маршрутов. Начнём с Брно — с какого города начинать, всё равно, — и выберем порядок остальных 32: это $32!$ вариантов, а каждый тур посчитан дважды, в одну сторону и в обратную. Получается $32!/2 \approx 1{,}3 \cdot 10^{35}$ туров. Компьютер, который проверяет миллиард туров в секунду, перебирал бы их $4 \cdot 10^{18}$ лет — в сотни миллионов раз дольше, чем существует Вселенная. Посмотрим, как с этим справляется самый умный из точных методов, который можно написать за десять строк.
Участник первый: точный расчёт
Динамическое программирование из главы 22 справляется и с этим. Для коммивояжёра его независимо предложили в 1962 году, в год конкурса, Ричард Беллман и пара Майкл Хелд — Ричард Карп; Карп — автор двадцати одной задачи из прошлой главы. Подзадача: кратчайший путь, который выходит из города 0, проходит ровно через множество городов $S$ и кончается в городе $j$. Ответ для $S$ собирается из ответов для множеств на один город меньше: надо выбрать, из какого города $k$ мы пришли в $j$. Множество удобно хранить битовой маской — числом, где бит $j$ равен единице, если город $j$ в множестве; сдвиги и маски мы разбирали в главе 28.
Вместо $n!$ туров — $n^2 2^n$ шагов: для шестнадцати городов это доли секунды, а перебор всех туров шёл бы годами. Но экспонента никуда не делась. Тридцать три города — несколько суток и таблица на семьдесят миллиардов клеток, которая не поместится в память обычного компьютера. Пятьдесят городов — тысячи лет. Точный метод, который не знает ничего, кроме определения задачи, на нашем конкурсе сходит с дистанции первым.
Участник второй: ближайший сосед
Самая естественная стратегия — та, которой пользуется человек без карты: из каждого города ехать в ближайший, где ещё не был. Глава 23 предупреждала, что здесь жадность ошибается. Посмотрим, насколько. Для сравнения нам понадобится оптимум: он равен 393,88 км, и в конце главы судья это докажет.
Из Брно жадина проезжает почти на 40 % больше, чем нужно. На картинке видно почему: в начале каждый шаг короткий, но города разбираются по одному, пока в конце не остаются забытые на краях, и за ними приходится ехать через всю карту. Если попробовать все 33 старта и взять лучший, проигрыш падает до 14 %. На случайных точках ближайший сосед в среднем примерно на четверть длиннее оптимума. Плохо, но не катастрофа, к тому же считается мгновенно, за $O(n^2)$, — хорошая отправная точка для следующих участников.
Участник третий: дерево, пройденное дважды
Жадный маршрут не даёт никакой гарантии: можно построить карту, где он хуже оптимума во сколько угодно раз. Следующий участник думает дольше, зато даёт обещание. Он берёт минимальное остовное дерево из главы 23, обходит его как экскурсовод — в глубину, по каждому ребру туда и обратно, — а потом спрямляет: если очередной город уже посещён, едет сразу к следующему новому.
Если расстояния удовлетворяют неравенству треугольника, маршрут по обходу минимального остовного дерева со спрямлениями не длиннее удвоенного оптимума.
Возьмём оптимальный тур и выбросим из него любое ребро. Останется путь через все города — остовное дерево. Значит, минимальное остовное дерево не длиннее оптимума: $T \le \mathrm{OPT}$. Обход дерева в глубину проходит каждое ребро дважды, его длина $2T$. Спрямление заменяет кусок пути A → … → C прямой дорогой A → C, а по неравенству треугольника прямая не длиннее. Итого маршрут не длиннее $2T \le 2 \cdot \mathrm{OPT}$.
Это приближённый алгоритм: он работает за полиномиальное время и гарантирует ответ не хуже оптимума в заданное число раз — здесь в два. На моравских городах он проиграл 27 %, хуже лучшего жадного старта: гарантия говорит о худшем случае и ничего не обещает про обычный. Зато в доказательстве спрятан первый инструмент судьи: длина дерева, 318,6 км, — это нижняя граница. Короче оптимум быть не может, и, ещё не зная его, мы уже знаем, что он лежит между 318,6 и 498,4 км.
В 1976 году Никос Кристофидес, а независимо от него советский математик Анатолий Сердюков (опубликовал в 1978-м) нашли способ сэкономить на обратных проходах. В дереве города с нечётным числом рёбер разбиваются на пары самым дешёвым способом — это задача о паросочетании, родственница главы 25, — и после добавления этих рёбер у каждого города чётная степень. Граф можно обойти, пройдя каждое ребро по одному разу, как в задаче Эйлера, а потом спрямить. Гарантия — полтора оптимума. Сорок четыре года её никто не мог улучшить. В 2020 году Анна Карлин, Натан Кляйн и Шаян Овейс Гаран сделали это — на величину порядка $10^{-36}$. Коэффициент стал чуть меньше 1,5. Выигрыш ничтожен, но работа доказала, что полтора — не предел, и считается большим достижением.
Участник четвёртый: 2-opt
Вернёмся к маршруту жадины. На нём есть перекрёстки — места, где маршрут пересекает сам себя. Любой человек, увидев такое, распутает петлю. Пусть маршрут идёт A → B, потом долго, потом C → E, и рёбра AB и CE пересекаются. Заменим их на AC и BE, а кусок между B и C проедем в обратном порядке. На плоскости это всегда выгодно: две диагонали четырёхугольника длиннее двух его противоположных сторон — снова неравенство треугольника. Такой ход называют 2-opt: меняются ровно два ребра. Предложил его Г. А. Кроус в 1958 году.
Каждый кадр — одно распутывание. Жадный маршрут за двадцать пять ходов превращается в тур длиной около 399 км — на один с небольшим процент хуже оптимума. Из ста случайных стартов 2-opt шестнадцать раз находит сам оптимум, а иногда застревает на 16 % выше. Застревает он в маршруте, где ни одна пара рёбер больше не улучшается, хотя лучший маршрут существует: чтобы до него добраться, надо сначала сделать хуже.
Общая схема называется локальным поиском: взять решение и улучшать его маленькими ходами, пока улучшения находятся. Решение, которое никаким одним ходом не улучшить, — локальный оптимум. Это вершина холма в тумане: вокруг всё ниже, но где-то может стоять гора. Ходы можно делать крупнее — менять три ребра, а не два, или цепочки рёбер переменной длины. Так устроен алгоритм Лина — Кернигана (1973), и его потомок LKH Келда Хельсгауна до сих пор находит лучшие известные маршруты для огромных задач. Для миллионов точек он выдаёт туры, которые, судя по нижним границам, хуже оптимума на доли процента. Но и у него есть холмы. Как спуститься с холма, чтобы подняться на гору?
Участник пятый: отжиг
Кузнец, который хочет получить прочный металл, нагревает его и остужает медленно. Горячие атомы мечутся и могут перескочить из неудачного положения в удачное, а при медленном остывании успевают уложиться в правильную решётку. Если остудить сразу, атомы замрут в беспорядке — в локальном минимуме энергии. В 1983 году трое физиков из IBM — Скотт Киркпатрик, Чарльз Гелатт и Марио Векки — предложили в журнале Science делать с маршрутами то же самое и назвали метод имитацией отжига. Правило они взяли из работы Метрополиса и соавторов 1953 года — того Метрополиса, что дал имя методу Монте-Карло в главе 26.
Правило такое. Выбираем случайный ход 2-opt. Если он укорачивает маршрут, делаем его всегда. Если удлиняет на $\Delta$ километров, делаем его с вероятностью $e^{-\Delta/T}$, где $T$ — «температура». При высокой температуре принимаются почти любые ходы, и поиск свободно бродит по маршрутам. При низкой — только улучшения, и это обычный 2-opt. Температуру понемногу снижают. Попробуйте сами: ниже температура в ваших руках.
Все пять запусков из случайных маршрутов приходят к 393,88 км — к оптимуму, и на каждый уходят доли секунды. Но отжиг — тоже эвристика без гарантий: на других картах и с другим расписанием он застревает, поэтому его запускают несколько раз и берут лучшее. Тонкость в расписании остывания: слишком быстрое замораживает поиск в первом попавшемся холме, слишком медленное тратит время зря. Расписание подбирают опытом, как кузнец. Киркпатрик и соавторы в той же статье применили отжиг к насущной для IBM задаче: как разместить элементы на кристалле микросхемы, чтобы провода между ними были короче. Отжиг и сегодня работает в программах проектирования микросхем, в расписаниях и в раскрое.
Участник шестой: эволюция
Последний эвристический участник подсмотрел приём у природы. Генетические алгоритмы, которые в 1970-х развил Джон Холланд, держат сразу целую популяцию решений. Лучшие выживают и скрещиваются, у потомков случаются мутации, и поколение за поколением популяция становится лучше. Для маршрутов скрещивание делают так, чтобы потомок остался маршрутом: кусок берётся у матери, а остальные города — в том порядке, в каком они идут у отца.
Эволюция начинает со случайных маршрутов втрое длиннее оптимума и за четыреста поколений подбирается к нему на несколько процентов. В нашем соревновании результат скромный: отжиг в одиночку справился лучше и быстрее. Для коммивояжёра чистые генетические алгоритмы обычно проигрывают хорошему локальному поиску, а побеждают гибриды — когда каждого потомка дополнительно распутывают 2-opt. Сила эволюции — в задачах, где про устройство решений почти ничего не известно и умного хода не придумать: формы антенн, параметры двигателей, настройки других алгоритмов.
Судья: как доказать, что лучше нельзя
Эвристики дают маршрут, но молчат о том, далеко ли до оптимума. Судье нужна другая сторона вилки — нижняя граница: число, про которое доказано, что короче тура быть не может. Одну мы уже знаем: остовное дерево, 318,6 км. Она слабая, но её можно подтянуть. Хелд и Карп в 1970 году предложили 1-дерево: остовное дерево на всех городах, кроме одного, плюс два кратчайших ребра из этого одного. Любой тур — тоже 1-дерево: выбросьте из него город, останется путь, то есть дерево. Значит, кратчайшее 1-дерево не длиннее оптимума.
Дальше — приём с надбавками. Начислим каждому городу штраф $\pi_i$ и будем считать длину ребра $(i, j)$ как $d_{ij} + \pi_i + \pi_j$. В любом туре у каждого города ровно два ребра, поэтому все туры удлиняются на одно и то же $2\sum\pi_i$ и их порядок не меняется. А 1-деревья меняются по-разному. Штрафуем города, у которых в 1-дереве больше двух рёбер, и поощряем листья — и 1-дерево постепенно становится похожим на тур.
За пятьдесят шагов граница вырастает с 333 км до 393,7, к сотому отстаёт от длины тура, который нашёл отжиг, всего на метр, а к трёхсотому совпадает с ней совсем: остаток меньше нанометра, это уже погрешность округления дробей. Таков приговор судьи: короче 393,88 км маршрута нет, отжиг нашёл оптимум, и ваш результат, как и результаты остальных участников, можно мерить от этого числа. Мы доказали оптимальность, не перебрав ни одного тура: верхняя граница от эвристики и нижняя от 1-деревьев встретились посередине.
Так бывает не всегда: на больших и трудных картах вилка между границами не схлопывается. Тогда в дело идут два приёма, которые и составляют целочисленное программирование. Задачу записывают как линейную программу с переменными «едем ли по дороге $(i, j)$»: $x_{ij} \in \{0, 1\}$.
Если разрешить переменным дробные значения от 0 до 1, получится обычная линейная программа, а она решается за полиномиальное время — это доказал Леонид Хачиян в 1979 году. Её ответ — снова нижняя граница: целый тур — частный случай дробного. Если дробный ответ оказался целым, перед нами оптимальный тур. Если нет, есть два хода. Отсечение: найти неравенство, которое выполняется для всех туров, но нарушается дробным ответом, — как условие «нет отдельных петель», которое Данциг добавлял по мере надобности, — и решить заново. Ветвление: выбрать дробную переменную и решить две задачи — с $x_{ij} = 0$ и с $x_{ij} = 1$, отбрасывая ветви, где нижняя граница уже хуже найденного тура. Этот метод ветвей и границ предложили Эйлса Лэнд и Элисон Дойг в 1960 году.
На этих идеях построен Concorde — программа Дэвида Эпплгейта, Роберта Биксби, Вашека Хватала и Уильяма Кука. В 2006 году она вместе с эвристикой Хельсгауна нашла кратчайший тур по 85 900 точкам и доказала, что короче нет. Точки — схема микросхемы, которая возникла в Bell Labs в конце 1980-х. Расчёт занял, по подсчётам авторов, больше 136 процессорных лет. Те же ветвление и отсечения работают в промышленных решателях целочисленных программ: на них составляют расписания авиакомпаний и поездов, планируют производство и доставку. Вот и ответ на вопрос из начала главы, как справляются логисты: задача NP-трудна, но реальные задачи с их структурой решатель часто дожимает до доказанного оптимума или до гарантии вроде «не хуже оптимума на 0,3 %».
Показательное выступление: SAT-решатель
Вот он, сертификат для ответа «нет», которого так не хватало на карте co-NP: двести терабайт шагов, и каждый отдельная программа проверяет механически. Попробуем ту же задачу с решателем cs.sat.solve. Это DPLL, который вы написали в прошлой главе, только с двумя наблюдаемыми литералами.
До трёх тысяч решатель красит числа мгновенно, почти без тупиков. На 3500 тупиков уже больше десяти тысяч, на 4000 он сдаётся, хотя раскраска там заведомо есть — до 7824. Хёле и соавторам понадобился решатель другого поколения. В DPLL тупик учит только одному: эта ветка плоха, вернёмся на шаг. Современные решатели, начиная с GRASP (1996) и Chaff (2001), разбирают каждый тупик: какая цепочка выводов к нему привела и какие из сделанных выборов в нём виноваты. Из разбора получается новое условие, запрещающее виноватое сочетание. Его добавляют к формуле, чтобы больше не наступать на те же грабли, и откатываются прямо к виноватому выбору, сколько бы шагов назад он ни был сделан. Такие решатели называют CDCL, обучением на конфликтах. Они справляются с формулами из миллионов переменных, проверяют схемы процессоров и программы, разрешают зависимости в менеджерах пакетов и составляют расписания.
А вот решатель за работой над судоку, NP-полноту которого в общем виде мы обсуждали в прошлой главе. Переменных 729 — «в клетке $r, c$ стоит цифра $d$», условий около двенадцати тысяч: в каждой клетке есть цифра, не две цифры сразу, в каждой строке, столбце и квадрате каждая цифра есть и не повторяется.
Газетную головоломку решатель проходит, не сделав ни одного выбора: всё выводится единичным распространением, как у опытного человека, который ставит цифру, только когда она единственно возможна. Головоломкам с минимумом подсказок нужно несколько выборов и возвратов. А без распространения тот же решатель тонет в переборе: каждый вывод отсекал целую ветку вариантов, и теперь их приходится проходить.
Вне зачёта: пожарные части
Напоследок ещё одна задача из списка Карпа — на ней видно, что жадность иногда даёт гарантию. Край решил построить пожарные части в некоторых из 675 сёл так, чтобы от любого села до ближайшей части было не больше 8 км. Как обойтись наименьшим числом частей? Каждое село-кандидат накрывает множество сёл вокруг себя, и нужно выбрать как можно меньше множеств, которые вместе накрывают всё. Это покрытие множествами, NP-трудная задача. Жадный способ очевиден: каждый раз брать село, которое накроет больше всего ещё не накрытых.
Если оптимальное покрытие использует $k$ множеств, жадный алгоритм использует не больше $k \ln n + 1$, где $n$ — число элементов.
Пусть ещё не накрыто $m$ элементов. Оптимальные $k$ множеств накрывают их все, значит, одно из них накрывает не меньше $m/k$ — а жадный берёт множество не хуже. После шага ненакрытых не больше $m(1 - 1/k)$. После $t$ шагов — не больше $n(1 - 1/k)^t < n e^{-t/k}$. При $t = k \ln n$ это меньше единицы, то есть ноль. Значит, шагов не больше $k \ln n + 1$.
Для 675 сёл $\ln n \approx 6{,}5$: жадные 56 частей могут быть в шесть с половиной раз хуже лучшего, хотя на деле разрыв куда меньше. Гарантию нашли в 1970-х Дэвид Джонсон, Ласло Ловас и Вашек Хватал. А в 2014 году Ирит Динур и Давид Штойрер доказали, что если $\mathrm P \ne \mathrm{NP}$, то никакой полиномиальный алгоритм не может гарантировать заметно лучше, чем $\ln n$. Выходит, по части гарантий жадность здесь — лучшее, что можно сделать. В задаче «Жадное покрытие» вы сделаете её быстрой.
Итоги соревнования
Сведём результаты на тридцати трёх моравских городах. Своё место в таблице вы знаете из площадки в начале главы.
| Участник | Маршрут | Хуже оптимума |
|---|---|---|
| Точный расчёт по подмножествам | — | сошёл: несколько суток счёта и десятки миллиардов клеток памяти |
| Ближайший сосед из Брно | 546,4 км | на 39 % |
| Ближайший сосед, лучший из 33 стартов | 449,5 км | на 14 % |
| Дерево, пройденное дважды | 498,4 км | на 27 %, зато гарантия «не больше 2×» |
| 2-opt от жадного маршрута | 399,2 км | на 1,4 % |
| Эволюция, 400 поколений | 408,6 км | на 3,7 % |
| Имитация отжига | 393,88 км | 0 |
| Судья: 1-деревья | не короче 393,88 км | нижняя граница, а не маршрут |
Из этой таблицы складывается рецепт на случай, когда трудная задача встретится вам на работе. Сначала узнайте её: если это коммивояжёр, раскраска, рюкзак или покрытие в чужом костюме, не ищите точного быстрого алгоритма. Прикиньте размер: двадцать объектов — точный перебор с отсечениями или динамика по подмножествам, и думать не о чем. Присмотритесь к структуре: может быть, ваши данные — частный случай, где работает жадность, как у остовного дерева. Если задача большая и общая, запишите её на языке, который понимают готовые решатели, — формулой для SAT-решателя или целочисленной программой — и попробуйте их: они часто дают доказанный оптимум. Если и это не помогло, стройте хорошее решение эвристиками: жадный старт, потом локальный поиск, потом отжиг, если локальный поиск застревает. И всегда держите рядом нижнюю границу, чтобы знать, сколько ещё можно выиграть: три процента до оптимума — повод остановиться, тридцать — повод думать дальше.
Задачи
Три задачи — три инструмента главы: локальный поиск, отжиг и жадность с гарантией.
Напишите two_opt(points, tour): точки — список пар координат, tour — маршрут, список номеров точек. Верните маршрут, который получается из данного ходами 2-opt, пока ни один ход больше не укорачивает маршрут. Ход: выбрать два ребра маршрута, AB и CE, и, если $|AC| + |BE| < |AB| + |CE|$, заменить их на AC и BE, развернув кусок маршрута между B и C. Тесты проверяют, что вы вернули маршрут через все точки, что он не длиннее исходного и что в нём не осталось ни одного выгодного хода. На 33 городах Моравии от жадного маршрута длиной 546 км нужно уложиться в 437 км, а маршрут через 300 точек — распутать быстрее трёх секунд.
Заготовка делает один проход по всем парам рёбер. Но каждый разворот меняет маршрут, и пары, которые до него были невыгодны, могут стать выгодными. Повторяйте проходы, пока очередной проход не найдёт ни одного улучшения.
Сравнивайте с запасом: d[a][c] + d[b][e] < d[a][b] + d[c][e] - 1e-9. Без него из-за ошибок округления в дробях из главы 28 два хода с равной выгодой могут бесконечно разворачивать один и тот же кусок туда и обратно.
Почему у j верхняя граница n if i else n - 1? При i = 0 и j = n - 1 оба ребра выходят из одного города: ребро 0–1 и ребро от последнего города к нулевому. Разворот такого «куска» ничего не меняет.
Один проход стоит $O(n^2)$ проверок, а проходов на случайных точках обычно немного — пять-семь. Остановится алгоритм непременно: каждый ход укорачивает маршрут, а маршрутов конечное число, так что бесконечно укорачивать нельзя. Это стандартный довод для любого локального поиска, и он же объясняет, почему в сравнении нужен запас: без него «укорочение» на $10^{-16}$ из-за округления могло бы повторяться вечно. Разные порядки просмотра пар приводят к разным локальным оптимумам: на моравских городах от одного и того же жадного маршрута — от 394 до 465 км. Поэтому 2-opt запускают из нескольких стартов, а для больших карт ускоряют, просматривая для каждого города только ближайших соседей.
Вернёмся к рассадке гостей из прошлой главы, только теперь у каждой пары гостей есть число like[i][j] — насколько им приятно сидеть рядом (отрицательное — неприятно; матрица симметрична). Напишите seat(like, seed=0): рассадку за круглым столом — список всех гостей по одному разу — с как можно большей суммой симпатий соседей. Это коммивояжёр в другом костюме: «расстояния» без неравенства треугольника, и мы ищем максимум, а не минимум. Тесты сажают по сорок гостей за три стола и требуют набрать не меньше 98 % от лучшей рассадки, которую мы нашли и доказали заранее; на стол — четыре секунды. Шесть гостей тесты рассаживают перебором и ждут именно лучшую рассадку.
Заготовка — подъём на холм: она принимает только пересадки, которые увеличивают сумму, и застревает на 3–7 % ниже лучшего. Добавьте правило Метрополиса, как в разделе об отжиге, только знак здесь обратный: мы ищем максимум, поэтому ухудшение — это gain < 0, и его принимают с вероятностью math.exp(gain / t).
Температуру нужно понижать. Удобно геометрически, от «горячей» $T_0$ до «холодной» $T_1$: на шаге $k$ из $K$ берите $t = T_0 \cdot (T_1/T_0)^{k/K}$. Подберите $T_0$ так, чтобы вначале принималась заметная часть ухудшений: симпатии здесь от −5 до 10, и $T_0$ порядка 5 — разумный старт; $T_1$ — несколько сотых.
Отжиг иногда уходит от лучшего найденного и не возвращается. Запоминайте лучшую рассадку за весь путь и возвращайте её. И не забудьте маленькие столы: при $n < 4$ все рассадки одинаковы, а rnd.sample(range(n), 2) при $n = 1$ упадёт.
Ход тот же, что у 2-opt: развернуть кусок рассадки. Выгоду хода считаем за четыре обращения к таблице, не пересчитывая всю сумму, — иначе 300 тысяч шагов не уложились бы в секунды. В горячей фазе рассадка свободно меняется, в холодной отжиг превращается в подъём на холм, но к этому времени он уже стоит у подножия высокой горы. На столах из тестов такой отжиг набирает 98,5–100 % лучшей рассадки, а заготовка — от 93 до 97 %. Лучшие рассадки для тестов мы нашли целочисленным программированием с отсечениями — тем же методом, что Данциг в 1954 году.
Напишите greedy_cover(n, sets): элементы — числа от 0 до n - 1, sets — список множеств (списков элементов, возможно с повторами). Верните номера множеств в том порядке, в каком их выбирает жадный алгоритм: каждый раз — множество, которое накрывает больше всего ещё не накрытых элементов, а при ничьей — с меньшим номером. Когда накрыто всё, остановитесь. Если накрыть всё невозможно, верните None. В тестах — двадцать тысяч элементов и пять тысяч множеств, и ответ нужен быстрее двух секунд.
Заготовка верна, но на каждом шаге пересчитывает выгоду всех пяти тысяч множеств. Шагов больше тысячи, и на каждом — пять тысяч пересечений множеств: сотни миллионов операций. Зато выгода множества со временем только уменьшается: ненакрытых элементов становится меньше.
Ленивая жадность: держите множества в куче из главы 18 по старой выгоде, (-выгода, номер). Достали верхнее — пересчитали выгоду. Если она не изменилась, это множество и есть лучшее: у остальных старая выгода не больше, а текущая — тем более. Если уменьшилась — положите обратно с новой выгодой и достаньте следующее.
Ничьи разрешит сама куча: кортежи сравниваются по порядку, и при равной выгоде вперёд выйдет меньший номер. Убедитесь, что это верно и для множеств, которые вернулись в кучу с пересчитанной выгодой. А если достали множество с нулевой старой выгодой, а что-то ещё не накрыто, — накрыть это нечем.
Ленивая жадность выбирает то же, что обычная: старая выгода — верхняя оценка текущей. Когда верхний элемент кучи после пересчёта сохранил выгоду, все остальные в куче имеют старую выгоду не больше этой, а текущую — и подавно. Значит, лучше него нет, а при равенстве куча уже поставила вперёд меньший номер. Приём экономит пересчёты в сотни раз и работает в любой жадной схеме, где выгода только убывает. Такое убывание отдачи называют субмодулярностью; на нём держатся, например, алгоритмы расстановки датчиков и составления кратких выдержек из текстов.
Куда дальше
С трудностью, оказывается, можно жить. Точный ответ для тридцати трёх городов нашёлся за доли секунды, хотя задача NP-трудна: эвристика дала маршрут, а нижняя граница доказала, что лучше нет. Для тысяч городов мы довольствовались бы маршрутом, который хуже оптимума на процент, — и знали бы, что это всего процент.
Но обходится трудность не всегда. В прошлой главе решатель раскладывал на множители десятизначные числа, и с каждым битом ему становилось всё тяжелее. Для 600-значных чисел обходного пути нет: никакая эвристика из этой главы с ними не справится. Значит, трудность — не только беда. На ней можно построить замок, спрятав секрет так, чтобы без ключа его не нашли ни отжиг, ни решатели, ни все компьютеры мира. Но прежде чем строить замки на трудности, стоит посмотреть, как строили и вскрывали старые, державшиеся на хитрости и тайне. С этого начинается часть X, «Шифровальный отдел».