Динамика по маскам

Пятнадцать мест Алматы — от Площади Республики и Зелёного базара до Кок-Тобе и MEGA, — и нужно объехать все по улицам и вернуться туда, откуда начали, проехав как можно меньше. Разных кругов 14!/2 = 43 589 145 600. Перебор на Go занял бы больше десяти минут, если судить по замеру ниже, а таблица находит лучший круг в 42,41 километра за сотые доли секунды в вашем браузере. Нажимайте на точки: добавляйте до восемнадцати, убирайте, сравнивайте с быстрыми правилами.

Правило «каждый раз ехать в ближайшую ещё не посещённую точку» проезжает 48,37 километра — на 14 % больше. Оно хорошо начинает и плохо заканчивает: последние точки оказываются разбросаны по городу, и к ним приходится возвращаться через полгорода. Пунктир «+ 2-opt» — то же правило, после которого маршрут правят: разворачивают кусок круга, пока это его сокращает. На этих пятнадцати точках правка находит тот же лучший круг, но добавьте шестнадцатую, Dostyk Plaza, — и она застревает на 43,73 километра против 42,56. Точный ответ можно знать только тогда, когда есть с чем сравнивать.

Идея

Что нужно знать о недоехавшем маршруте, чтобы доехать его наилучшим образом? Не порядок, в котором вы объезжали точки, — только какие точки уже позади и где вы стоите сейчас. Остаток пути от этого и зависит: какие точки осталось посетить и откуда к ним ехать.

Состояние — пара «множество посещённых точек, точка, где мы стоим», а множество записано числом, в котором бит i равен единице, если точка i уже посещена. Для каждого состояния храним длину кратчайшего пути из старта, который обошёл ровно эти точки и кончился в этой. Переход — съездить в ещё не посещённую точку: включить её бит. Множеств 2ⁿ, а не n!: все пути, которые обошли одни и те же точки и стоят в одной, сливаются в одно состояние, и из них помнится только кратчайший.

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

Таблица Хелда — Карпа

Пронумеруем точки от 0 до n − 1 и начнём в точке 0. best[S][j] — длина кратчайшего пути, который вышел из 0, побывал ровно в точках множества S и стоит в j ∈ S. Точку 0 в маску не включаем: она старт.

Ответ — наименьшее best[все точки][j] + d(j, 0): с последней точки вернуться в старт. Сам круг восстанавливается указателями назад: для каждого состояния запоминаем, из какой точки j в него пришли, и идём от конца, выключая биты.

Каждый переход включает один бит, и маска растёт. Поэтому таблицу можно заполнять по возрастанию маски, а можно — слоями: сначала все множества из одной точки, потом из двух, из трёх… Слои показаны под картой: высота столбика — сколько в слое состояний. Больше всего их посередине, где число множеств из s элементов, «из 14 по 7», наибольшее.

Ключевое место доказательства — «последний шаг от куска не зависит». Будущее пути зависит только от того, где мы и какие точки уже взяты. Если бы, скажем, стоимость следующего переезда зависела от времени суток, а время — от длины уже проеханного, пары «множество, точка» не хватило бы, и в состояние пришлось бы добавить время.

Код

Расстояния между местами — по улицам, алгоритмом Дейкстры из каждого места; места привязаны к ближайшему перекрёстку. Дальше таблица по маскам с указателями назад, правило ближайшего соседа, правка 2-opt и проверка перебором на первых девяти местах.

Таблица на 15 мест — 229 376 ячеек, но настоящих состояний вдвое меньше, 114 688: точка, где мы стоим, обязана входить в маску. Переходов — 745 472. Сравните с 43 589 145 600 кругами перебора: разница в десятки тысяч раз, и она растёт с каждой точкой — перебор умножается на n, таблица только удваивается с небольшим. На девяти местах перебор и таблица дают одни и те же 27,70 километра, как и должно быть.

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

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

Состояний (n − 1) · 2^{n − 2}, из каждого — до n переходов: время O(2ⁿ · n²), память O(2ⁿ · n). Это экспонента, но несравнимо меньшая, чем n! у перебора.

Ось времени логарифмическая. Перебор растёт всё круче: каждая новая точка умножает его время на n, и на 11 точках Python перебирает дольше полутора секунд. Таблица растёт ровной линией — каждые две точки примерно в пять раз — и на 16 точках в Python занимает десятую долю секунды. Но ровная линия на логарифмической оси — тоже экспонента. Таблица для 25 точек — это 2²⁴ · 24 ≈ 400 миллионов ячеек, гигабайты памяти. Динамика по маскам — оружие для n до двадцати с небольшим, а дальше задачу коммивояжёра решают иначе: ветвями и границами, отсечениями линейного программирования, эвристиками с гарантией. Об этом — отдельная статья о задаче коммивояжёра.

Быстрее 2ⁿ точный алгоритм для общей задачи коммивояжёра — с произвольными расстояниями — пока никто не нашёл: в работах 2018 года вопрос, бывает ли алгоритм за (2 − ε)ⁿ, всё ещё назван открытым. Динамике, придуманной в 1962 году, больше шестидесяти лет, а в худшем случае она по-прежнему лучшая известная.

Иногда в состоянии нужна не одна маска, а перебор всех её подмасок: «разбить множество на группы», «покрыть множествами». Тогда переходов становится 3ⁿ — почему именно столько, доказано в статье о битовых трюках. Для двадцати элементов это три с половиной миллиарда шагов, и оценку стоит прикинуть заранее.

Маска как граница: доминошки

Маска не обязана быть множеством посещённых точек. Сколькими способами можно выложить доску 8 × 8 доминошками 1 × 2? Будем класть их клетка за клеткой, по строкам. В каждый момент уложенная часть доски отделена от пустой ломаной границей, и для продолжения важно только одно: какие клетки на этой границе уже накрыты доминошками, торчащими из уложенной части. Таких клеток на границе ровно по одной на столбец — значит, это маска из 8 бит. Нажмите «Профиль по шагам»: оранжевая ломаная и есть граница, её называют профилем.

Переход у каждой клетки простой. Если клетка уже накрыта сверху — снять её бит и идти дальше. Если свободна — положить доминошку вниз (бит остаётся включённым, теперь он означает клетку под нами) или вправо (включается бит соседа справа). Вырезанная клетка ведёт себя как уже накрытая, только накрыть её ничем нельзя. Масок 2⁸ = 256, клеток 64, переходов на клетку не больше двух: несколько десятков тысяч шагов на всё.

Для полосок 2 × n получаются числа Фибоначчи: последняя доминошка либо стоит вертикально, либо две лежат одна над другой горизонтально. Для 3 × n при нечётном n ноль — клеток нечётное число. Доска 8 × 8 — 12 988 816 раскладок, и это число известно с 1961 года: Питер Кастелейн и независимо Гарольд Темперли с Майклом Фишером вывели формулу для числа раскладок прямоугольника, в которой нет никакого перебора. Но формула годится только для прямоугольников, а профиль считает любую доску — с вырезами, с дырами, со стенами.

Вырежьте два противоположных угла. Раскладок ноль, и таблица честно его находит, хотя причина видна и без неё: углы по диагонали одного цвета, остаётся 32 клетки одного цвета и 30 другого, а каждая доминошка накрывает по одной каждого. Эту задачу о «покалеченной доске» предложил философ Макс Блэк в 1946 году, а популярной её сделали Соломон Голомб и Мартин Гарднер. Если же вырезать две клетки разного цвета — например, два угла одной стороны, — раскладки всегда найдутся (это теорема Ральфа Гомори): листинг насчитывает их 2 436 304.

Где работает

Порядок соединения таблиц. Запрос к базе данных, соединяющий несколько таблиц, можно выполнять в разном порядке, и стоимость разных порядков может различаться во много раз. Оптимизатор PostgreSQL выбирает порядок динамикой по множествам таблиц, ровно слоями, как в сцене: в документации разработчиков сказано, что первый проход строит соединения двух таблиц, второй — трёх, следующий — четырёх, и так до всех сразу. Сам подход восходит к оптимизатору System R из IBM. Цена известна: таблиц с двенадцати PostgreSQL по умолчанию переходит на генетический алгоритм — параметр geqo_threshold равен 12, потому что, как пишет документация, на многих таблицах полный поиск занимает больше времени, чем экономит.

Маршруты с немногими остановками. Объезд дюжины адресов, обход нескольких складов, порядок посещения точек в дневном плане — там, где точек немного, таблица даёт точный ответ за доли секунды, и гадать, насколько эвристика ошиблась, не нужно.

Назначения и упаковка. Кому из n исполнителей какую работу дать и как разложить вещи по поездкам — обе задачи ниже. Для назначений есть и полиномиальный венгерский алгоритм, но маски проще и легко принимают дополнительные условия.

Олимпиады. Ограничение «n ≤ 20» в условии — почти всегда подсказка: 2²⁰ — около миллиона, и решение — динамика по маскам или встреча посередине.

История

Таблицу для задачи коммивояжёра опубликовали в 1962 году независимо Ричард Беллман — «Dynamic programming treatment of the travelling salesman problem» в журнале ACM — и Майкл Хелд с Ричардом Карпом, «A dynamic programming approach to sequencing problems» в журнале SIAM. Её так и зовут алгоритмом Хелда — Карпа, или Беллмана — Хелда — Карпа. У раскладок доминошек своя история, старше программ: их изучали физики под названием задачи о димерах — доминошка там модель двухатомной молекулы, занимающей два соседних места на решётке, — и именно для неё Кастелейн, Темперли и Фишер в 1961 году нашли свою формулу.

Задачи

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