Перебор с возвратом

В банке головоломок Sudoku Exchange 893 916 судоку, и у каждой есть оценка: насколько хитрый приём понадобится человеку. Компьютеру приёмы не нужны. Он ставит в пустую клетку первую цифру, которая не спорит с соседями, и идёт к следующей клетке, а упёршись в клетку, куда не встаёт ничего, стирает последнюю цифру и пробует следующую. Ниже 1606 головоломок из банка: по горизонтали — оценка для человека, по вертикали — сколько цифр написал компьютер, пока не решил. Нажмите на любую точку, и перебор пойдёт прямо здесь. Потом переключите порядок, в котором он обходит клетки.

Сцена открылась на головоломке из файла лёгких. Её оценка 1,2 — самая низкая в банке: человек решает её простейшими приёмами, без единой догадки. Перебор, который обходит клетки по порядку, написал 10 696 818 цифр и стёр всё, кроме последних 57. Кривая рядом с доской — сколько цифр стоит на доске в каждый момент: она миллионы раз взлетает и падает. Теперь включите «Сначала самая стеснённая». Та же головоломка решается за 57 цифр, ровно по одной на пустую клетку, без единого тупика, а вся туча точек опускается на полтора-два порядка.

Заметьте и то, чего на графике почти нет: связи между трудностью для человека и для перебора. Медиана по файлу лёгких — 1008 цифр, по файлу дьявольских — 6847, всего в семь раз больше. А внутри любого файла точки разбросаны на пять с лишним порядков: от сорока с небольшим цифр до миллионов. Человек ищет закономерности, перебор их не видит: ему трудно там, где неудачные ранние выборы долго не обнаруживают себя.

Идея

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

Это перебор с возвратом, по-английски backtracking. Удобно думать о нём как о прогулке по дереву перебора. В корне — пустая доска. Дети узла — все способы сделать следующий выбор. Листья — либо готовые решения, либо тупики, где сделать следующий выбор нельзя. Дерево никто не строит: перебор держит в памяти только путь от корня до текущего узла и, спускаясь, меняет одну и ту же доску, а поднимаясь, возвращает её как было. Отсюда и название — «с возвратом».

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

Дерево перебора: ферзи

Классический пример — ферзи. На доске n × n нужно расставить n ферзей так, чтобы никакие два не били друг друга: ни по вертикали, ни по горизонтали, ни по диагонали. В каждой строке будет ровно один ферзь, поэтому ставим их по строкам сверху вниз: выбор на уровне k дерева — столбец ферзя в строке k. Ниже всё дерево целиком: бледные линии — то, что перебору ещё предстоит открыть. Запустите обход и следите за доской.

Посмотрите на форму дерева при n = 8. По уровням в нём 1, 8, 42, 140, 344, 568, 550, 312 и 92 узла — всего 2057, а 92 нижних узла и есть все решения задачи. До пятого уровня дерево расширяется, а дальше сужается: чем больше ферзей стоит, тем меньше клеток не под боем, и ветки одна за другой упираются в тупики — красные чёрточки, где следующая строка простреливается целиком.

Отсечения здесь решают всё. Сравните три дерева для одной и той же задачи:

Правила во всех трёх строках одни и те же, разница только в том, когда их проверяют. Проверка в конце отбраковывает расстановки по одной. Проверка на шаге отбраковывает ветку сразу со всем, что под ней: ферзь, поставленный под удар в третьей строке, без проверок потянул бы за собой 8⁵ = 32 768 полных расстановок, и все они негодные. Чем раньше замечена ошибка, тем больше дерева отрезает одна проверка.

Почему перебор ничего не теряет

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

Код

Ферзи по строкам. Занятые столбцы и диагонали хранятся в трёх массивах флагов: у всех клеток одной диагонали «↘» одинакова разность row − col, у диагонали «↙» — сумма row + col. Поэтому проверка «бьют ли новую клетку» — три обращения к массиву, а возврат — три присваивания False. Программа печатает число узлов на каждом уровне и сравнивает дерево с деревом без проверок.

n = 8: 92 solutions, 2057 nodes of the search tree
nodes by row: 1 8 42 140 344 568 550 312 92
first solution (column of the queen in rows 1..8): 1 5 8 6 3 7 2 4

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

Чтобы программа укладывалась в ограничения песочницы, перебор по порядку здесь сдаётся после 100 000 цифр; без ограничения он дошёл бы до тех же чисел, что в сцене. Посмотрите на третью головоломку, о ней ниже.

Сначала самое трудное

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

Отсюда правило: следующий выбор делать там, где вариантов меньше всего. В литературе по ограничениям его называют «сначала самое стеснённое» (minimum remaining values), а Роберт Харалик и Гордон Эллиот, изучавшие его в 1980 году, сформулировали принцип так: чтобы преуспеть, пробуйте сначала там, где скорее всего провалитесь. Клетка, где разрешена одна цифра, — один из первых приёмов, которым учат решать судоку, и для лёгких головоломок его почти всегда хватает: перебор с этим правилом решает две лёгкие головоломки из трёх, ни разу не упершись в тупик.

По всему банку медиана падает с 4556 цифр до 97. Самой долгой для перебора по порядку оказалась головоломка из файла трудных с оценкой 3,2: 36 544 073 цифры. Стеснённая клетка решает её за 880. Таких, где перебор по порядку пишет больше миллиона цифр, в банке 991.

Гарантии правило не даёт. Третья головоломка листинга — самая долгая для него во всём банке: 17 979 цифр против 81 641 у перебора по порядку. Правило выигрывает и здесь, но всего в четыре с половиной раза. А на 3943 головоломках из 893 916 перебор по порядку и вовсе быстрее: первые клетки по порядку случайно оказались удачными. Найдите в сцене кнопку «Самая долгая для стеснённой» и сравните оба порядка на ней.

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

Следующий шаг после выбора стеснённой клетки — вывод следствий: поставив цифру, сразу вписать все цифры, которые стали единственными, и так до тех пор, пока что-то вписывается. На этом устроены SAT-решатели: алгоритм DPLL 1962 года — перебор с возвратом, к которому добавлено распространение единичных дизъюнктов. Как это выглядит на том же судоку, показано в главе курса о трудных задачах.

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

Время перебора — число узлов дерева, умноженное на работу в узле. Работа в узле обычно мала и понятна: у ферзей — три проверки на каждый столбец, у судоку — разбор масок. А число узлов заранее неизвестно, и в худшем случае оно экспоненциально: у задачи о ферзях дерево растёт примерно в пять-шесть раз с каждым следующим n. Ниже полный перебор для n от 4 до 12 на Python и до 15 на Go; ось времени логарифмическая, и экспонента выглядит прямой.

Память, наоборот, скромная: в каждый момент перебор хранит только путь от корня — O(глубины) кадров рекурсии и одну общую доску. Поэтому перебор упирается во время, а не в память: он может работать сутками на нескольких килобайтах.

Для многих задач, где нужен перебор, ничего принципиально лучшего не известно. Судоку на доске n² × n², раскраска графа в три цвета, выполнимость формулы — NP-полные задачи, и быстрый алгоритм для любой из них дал бы ответ на вопрос «P = NP?» (глава курса). Поэтому на практике вопрос звучит иначе: уложится ли перебор на этих данных и как это узнать, не дожидаясь конца.

Оценка Кнута: размер дерева без обхода

В 1975 году Дональд Кнут опубликовал способ, который придумал ещё в 1962-м. Спустимся от корня по случайной ветке: в каждом узле посчитаем, сколько у него детей, d₁, d₂, …, и пойдём в случайного из них. Если бы всё дерево ветвилось так же, как этот путь, на первом уровне было бы d₁ узлов, на втором d₁d₂, на третьем d₁d₂d₃. Сумма 1 + d₁ + d₁d₂ + … — оценка числа узлов, а последнее произведение, если спуск дошёл до решения, — оценка числа решений. Вернитесь к сцене с ферзями, включите «Оценку Кнута» и сделайте несколько спусков.

Одна оценка может ошибаться сильно, а среднее многих спусков быстро становится приличным. Листинг делает по тысяче спусков для n = 8 и 10, где дерево легко обойти и сравнить, и по десять тысяч для 20 и 27, где число решений известно из полного перебора, а обход дерева занял бы часы и века.

 n  walks   nodes (estimate)        exact   solutions (estimate)              exact
 8   1000               2059         2057                    104                 92
10   1000              35637        35539                    651                724
20  10000      3713131807868            ?            30688146577        39029188884
27  10000           2.84e+19            ?     217095032575214752 234907967154122528

Для 27 ферзей оценка за десятые доли секунды ошиблась на 8%. Точное число решений, 234 907 967 154 122 528, проект Q27 получил в сентябре 2016 года, и вычисление на специальных программируемых микросхемах заняло чуть больше года. Для 20 ферзей оценка обещает около 3,7·10¹² узлов — в двадцать тысяч раз больше, чем при n = 15. Если 15 ферзей Go-программа перебирает за две секунды, то 20 займут у неё около половины суток. Это стоит знать до запуска, а не после. Кнут вспоминал, как однажды прождал всю ночь вывода программы перебора, а потом выяснил, что ответа пришлось бы ждать около миллиона веков.

Где перебор не справляется

Одинаковые поддеревья. Перебор не помнит, что уже считал. Сколькими способами разменять 5000 тенге? Остаток 1000 тенге после «2000 + 2000» и после «1000 + 1000 + 1000 + 1000» — одна и та же подзадача, но перебор решит её заново в каждой ветке. Если подзадачи повторяются, а их немного, нужна память и динамическое программирование: так рюкзак с небольшими весами решается за доли секунды там, где перебор подмножеств не кончится никогда.

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

Симметрия. У задачи о ферзях 92 решения, но существенно разных среди них 12: остальные получаются поворотами и отражениями доски. Перебор об этом не знает и честно находит все. Простейшее лекарство — запретить симметричные начала: например, ставить первого ферзя только в левую половину строки и удваивать ответ. Дерево сокращается почти вдвое; проект, который сосчитал решения для 27 ферзей, за счёт симметрий искал перебором лишь чуть больше восьмой их части.

Регулярные выражения. Большинство движков регулярных выражений — Perl, Python, Java, PCRE — сопоставляют строку перебором с возвратом, и выражение вроде (x+)+y на строке из иксов без y заставляет их перебрать экспоненциально много способов разрезать строку. Чем это кончается в продакшене, разобрано в главе курса об автоматах; движки на автоматах Томпсона этой беды не знают.

Где работает

• SAT-решатели. Алгоритм Дэвиса — Логемана — Лавленда (1962) — перебор значений переменных с возвратом и выводом следствий. Современные решатели добавили к нему обучение на конфликтах: из каждого тупика выводится новое ограничение, и возврат прыгает сразу на много уровней вверх. На таких решателях проверяют микросхемы и программы.
• Пролог. В нём перебор с возвратом встроен в сам язык: программа описывает, что должно выполняться, а машина ищет подходящие значения и откатывается, когда очередное условие не выполнено.
• Решатели ограничений. Расписания, раскладка грузов, назначение частот, раскраска графов (раскраска) — перебор с выбором самой стеснённой переменной, выводом следствий и, в задачах на оптимум, ветвями и границами.
• Головоломки. Генераторы судоку проверяют перебором, что у задачи ровно одно решение: найдя первое, перебор продолжает искать второе. Кнут описал в 2000 году «танцующие ссылки» — способ быстро делать и отменять выбор в задачах точного покрытия, к которым сводятся судоку, пентамино и многие раскладки.

История

Задачу о восьми ферзях опубликовал в 1848 году шахматный композитор Макс Беццель. В 1850 году Франц Наук нашёл все 92 решения, хотя и не доказал, что других нет. Тогда же задачей занимался Карл Фридрих Гаусс: в письмах к астроному Генриху Шумахеру он насчитал 72 решения, прежде чем узнал о результате Наука. Что решений ровно 92, доказал в 1874 году Джеймс Глейшер, и в том же году независимо от него — Паулс.

Название метода старше его первого описания. По свидетельству Соломона Голомба и Леонарда Баумерта, словом backtrack его назвал в 1950-е годы Деррик Лемер, математик и один из первых, кто решал комбинаторные задачи на вычислительных машинах. Алгоритмом для машины метод впервые описал Р. Дж. Уокер в 1960 году, а Голомб и Баумерт в статье 1965 года «Backtrack programming» разобрали его на множестве задач.

В учебники ферзи попали через Никлауса Вирта. В статье 1971 года «Program development by stepwise refinement» он показывал на них, как писать программу постепенным уточнением, и сосчитал, сколько работы она делает: 876 проверок клеток до первого решения и 15 720 — до последнего. Ровно столько же проверок делает наш листинг: у каждого из 2057 − 92 = 1965 узлов выше нижнего уровня он осматривает восемь клеток следующей строки, и 8 · 1965 = 15 720. Годом позже тот же пример разобрал Эдсгер Дейкстра в «Заметках о структурном программировании».

Кнут вернулся к перебору много раз: в 1975 году — со статьёй об оценке размера дерева, посвящённой семидесятилетию Лемера, в 2000-м — с «танцующими ссылками», а в 2022 году раздел о переборе с возвратом занял заметную часть тома 4B «Искусства программирования».

Задачи

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