5.4 Отсечение поиска¶

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

Рассмотрим задачу: нужно посчитать количество путей в квадратной решётке n × n из левого верхнего угла в правый нижний, таких что путь посещает каждую клетку ровно один раз. Например, для решётки 7 × 7 число таких путей равно 111712. Это классическая задача, в которой грубый перебор очень быстро становится слишком дорогим.

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

После каждой оптимизации будем смотреть на два показателя:

время работы;
число рекурсивных вызовов.

Это позволяет ясно увидеть, насколько сильно отсечение уменьшает дерево поиска.

Базовый алгоритм¶

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

Итог для такой реализации:

время работы: 483 секунды;
число рекурсивных вызовов: 76 миллиардов.

Это очень медленно. Но хорошая новость в том, что в дереве поиска есть огромное количество ветвей, которые можно отбрасывать намного раньше.

Оптимизация 1¶

В любом допустимом пути первый шаг делается либо вниз, либо вправо. При этом каждому пути, начинающемуся вправо, соответствует симметричный путь, начинающийся вниз. Эти два пути зеркальны относительно главной диагонали квадрата.

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

Это очень простое наблюдение, но оно сразу вдвое сокращает перебор.

Результат:

время работы: 244 секунды;
число рекурсивных вызовов: 38 миллиардов.

Оптимизация 2¶

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

Почему? Потому что путь обязан закончиться именно в этой клетке. Если мы достигли её заранее, а часть поля ещё не покрыта, то потом уже нельзя вернуться назад и аккуратно достроить маршрут.

Значит, как только во время поиска мы попадаем в конечную клетку раньше времени, рекурсию можно немедленно завершать.

Результат:

время работы: 119 секунд;
число рекурсивных вызовов: 20 миллиардов.

Даже такая простая проверка снова почти вдвое уменьшает объём работы.

Оптимизация 3¶

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

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

Это очень сильное отсечение. Оно срабатывает гораздо чаще, чем может показаться поначалу.

Результат:

время работы: 1.8 секунды;
число рекурсивных вызовов: 221 миллион.

Здесь особенно хорошо видно, как одно удачное наблюдение может уменьшить перебор не на проценты, а на порядки.

Оптимизация 4¶

Идею предыдущего пункта можно обобщить.

Необязательно ждать, пока путь упрётся именно в стену. Достаточно заметить более общий случай: если путь не может идти прямо, но при этом может повернуть в две разные стороны, то часто это тоже означает, что оставшиеся свободные клетки раскалываются на две изолированные части.

Иными словами, если текущее положение маршрута создаёт «перегородку» внутри поля, после которой пространство распадается на две несвязные области, продолжать поиск бессмысленно.

После добавления этой проверки поиск становится ещё быстрее.

Результат:

время работы: 0.6 секунды;
число рекурсивных вызовов: 69 миллионов.

Что произошло на практике¶

Сравним начальную и итоговую версии:

без отсечений: 483 секунды;
после всех оптимизаций: 0.6 секунды.

То есть алгоритм стал почти в 1000 раз быстрее.

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

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

Похожий пример¶

Представь не клетчатое поле, а лабиринт из комнат, где нужно пройти через каждую комнату ровно один раз и закончить в заданной точке.

Если в какой-то момент ты уже оказался у выхода, а часть комнат ещё не посещена, маршрут заведомо не подходит.

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

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

Главное, что стоит запомнить¶

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

Хорошие правила отсечения обычно основаны на вопросе:

можно ли по текущему частичному решению уже сейчас доказать, что полного решения не существует?

Если ответ да, ветвь нужно немедленно остановить.

Этот раздел книги показывает очень важную практическую мысль: в задачах на перебор решающую роль часто играет не сама рекурсия, а то, насколько умно мы умеем обрывать бесполезные варианты. Основа раздела взята из книги Competitive Programmer’s Handbook, раздел 5.4. На мой субъективный взгляд обязательная книга для прочтения, но если вам пока хватает знаний, можете продолжать изучать сайт :)