В 1950 году американский математик Деррик Лемер ввёл термин «backtracking» для поиска с возвратом. Метод перебирает варианты, как полный перебор, но отсекает тупиковые ветви на ходу: судоку он собирает за 614 шагов, восемь ферзей расставляет за 876. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов разбирают, чем поиск с возвратом отличается от полного перебора.
Задачи на принцип «попробуй – отмени» известны давно. Самая старая – ход коня по доске, описанный в IX веке; над расстановкой восьми ферзей бился Гаусс и предлагал рекурсивный подход. Из бытовых – кроссворды, судоку и головоломки на соотношение букв и чисел.
Алгоритмическое описание метода дал Роберт Уокер: он связал поиск с возвратом с обходом в глубину. Голомб и Баумерт опубликовали статью «Backtrack Programming» в Journal of the ACM, где задали общую рамку подхода и показали её на разных задачах.
Поиск с возвратом – метод пошагового построения решения с откатом из тупика. Порядок действий короткий: попробовать шаг – проверить условия – откатиться при неудаче. Частичное решение растёт, пока не упрётся в нарушенное ограничение.
Метод схож с brute force – полным перебором, – но иначе обходится с неверными ответами: поиск с возвратом отсеивает их прямо при построении решения, а brute force сверяет с условиями уже готовые комбинации. Ранний отсев и даёт выигрыш в скорости.
Отсечение – главный приём метода. Как только частичное решение нарушает условие, вся ветвь объявляется тупиковой, и продолжения проверять не нужно. Одна отброшенная развилка снимает разом десятки комбинаций.
Работу метода показывает задача о всех парах массива {A, B}. Сначала перебор идёт по одной ветке до упора в пару AA. Затем шаг назад к вершине A даёт вариант AB, а откат к старту открывает ветвь B с её продолжениями. Дерево обходится целиком, но каждая ветка проверяется отдельно.
Перебор идёт в глубину, поэтому в памяти живёт только текущий путь, а не всё дерево. Глубина стека равна числу шагов, а не количеству вариантов, и памяти метод просит немного даже на огромных задачах.
Рис. 1. Красные стрелки – откаты: перебор возвращается к развилке, а не начинает заново
Судоку поиск с возвратом собирает целиком: синим отмечены цифры, данные с самого начала, зелёным и белым – подобранные. Чем темнее зелёный, тем больше попыток стоила клетка. Решение заняло 614 шагов, а дольше всего перебирались белые клетки.
Порядок обхода клеток решает, во сколько шагов обойдётся сетка. Выгодно начинать с клетки, где кандидатов меньше всего: ошибка вскрывается на первом же шаге, а не после десятка подстановок.
Карта попыток показывает, где метод буксовал. Светлый ровный фон означает, что условия вели перебор почти без ошибок, а тёмные пятна отмечают клетки, к которым программа возвращалась снова и снова.
Счётчик в каждой клетке показывает, сколько раз программа подбирала цифру. Рекорд одной клетки – 16 попыток, а вся сетка собралась за 171 шаг – втрое быстрее предыдущей. Разброс попыток показывает, где перебор буксовал.
Судоку удобно для проверки метода: правила простые, а пространство решений огромно. Девять цифр в восьмидесяти одной клетке дают столько комбинаций, что слепой перебор не кончится никогда, а поиск с возвратом укладывается в сотни шагов. Проверить ответ при этом можно глазами за минуту.
Задача о восьми ферзях решается тем же способом: фигуры расставляют так, чтобы ни одна не била другую. Первый ферзь встаёт в угол, второй ищет свободную клетку в соседнем столбце, и так до восьмого; при конфликте программа двигает предыдущего дальше. Красные числа – попытки занять клетку, всего их набралось 876. Найденная расстановка не единственная: у задачи 92 решения, и лишь 12 различны с точностью до поворотов и отражений.
Проверка для ферзей дешёвая: сравнить строку, столбец и две диагонали. Дешевизна проверки и делает отсечение выгодным – отбросить ветвь стоит меньше, чем достроить её до конца.
Рис. 2. Судоку и восемь ферзей: одна механика, разные условия
Головоломками область применения не ограничивается. Тем же перебором составляют расписания, распределяют ресурсы и загрузку производства, прокладывают маршруты, собирают портфель активов и ищут комбинации в биоинформатике и генетике.
В расписаниях и маршрутах роль клеток играют ресурсы и окна времени. Условие «два занятия не встают в один час у одного преподавателя» работает точно так же, как запрет двух одинаковых цифр в строке судоку.
Верхняя оценка сложности метода экспоненциальна:
T = O(mn),
где T – время работы, m – число вариантов на каждом шаге, n – количество шагов.
Оценка пугает, но на практике поиск с возвратом обгоняет brute force: тупиковые ветви он бросает сразу, не доводя перебор до конца.
Скорость держится на порядке перебора и силе условий. Слабые ограничения превращают метод в полный перебор, сильные срезают дерево у самого корня.
Чем поиск с возвратом отличается от полного перебора?
Backtracking строит решение по шагам и проверяет ограничения на каждом из них. Brute force сначала создаёт все ответы и лишь потом сверяет их с критериями. Разница вскрывается на первом же нарушении: один метод замечает его сразу, второй – только в конце.
Когда выбирать backtracking?
Метод выигрывает там, где пространство решений огромно и растёт экспоненциально. Второе условие – ограничения, по которым кандидатов отсеивают на ходу. Третье – достаточно одного ответа, а не всех сразу.
Сколько проходов делает алгоритм?
Число проходов задают варианты и критерии отсева. В худшем случае зависимость экспоненциальная: число вариантов возводится в степень количества шагов. Каждый лишний шаг умножает перебор, а не прибавляет к нему.
Где поиск с возвратом проигрывает?
Метод проигрывает на большом массиве без критериев отсева: отбрасывать нечего, и работа скатывается к полному перебору. Время тогда растёт без границ, а выигрыша перед brute force не остаётся.
Что запомнить?
Поиск с возвратом оценивает альтернативы на каждом шагу и сверяет их с критериями. Полный перебор сначала соберёт все варианты и лишь затем отфильтрует. Сложность у обоих экспоненциальная, но на практике возврат приходит к ответу раньше.
Рис. 3. Пять шагов метода и цена каждой разобранной задачи