Поиск с возвратом

Поиск с возвратом, бэктрекинг (англ. backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М. Как правило, позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п.

Термин backtracking был введен в 1950 году американским математиком Дерриком Генри Лемером.

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

Описание метода

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

Использование метода

Классическим примером использования алгоритма поиска с возвратом является задача о восьми ферзях. Её формулировка такова: «Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого». Сперва на доску ставят одного ферзя, а потом пытаются поставить каждого следующего ферзя так, чтобы его не били уже установленные ферзи. Если на очередном шаге такую установку сделать нельзя — возвращаются на шаг назад и пытаются поставить ранее установленного ферзя на другое место.

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

Псевдокод

Чтобы применить метод поиска с возвратом к определённому классу задач, необходимо предоставить данные P для конкретного экземпляра задачи, который требуется решить, а также шесть процедурных параметров: root, reject, accept, first, next и output. Эти процедуры должны принимать данные экземпляра P в качестве параметра и выполнять следующие действия:

1. root(P): возвращает частичного кандидата в корне дерева поиска.
2. reject(P, c): возвращает true только в том случае, если частичный кандидат c не стоит продолжать дополнять.
3. accept(P, c): возвращает true, если c является решением задачи P, и false в противном случае.
4. first(P, c): генерирует первое расширение кандидата c.
5. next(P, s): генерирует следующее альтернативное расширение кандидата после расширения s.
6. output(P, c): использует решение c задачи P, в зависимости от конкретного применения.

Алгоритм поиска с возвратом сводит задачу к вызову backtrack(P, root(P)), где backtrack - это следующая рекурсивная процедура:

procedure backtrack(P, c) is
    if reject(P, c) then return
    if accept(P, c) then output(P, c)
    s ← first(P, c)
    while s ≠ NULL do
        backtrack(P, s)
        s ← next(P, s)

Недостатки

Метод поиска с возвратом является универсальным. Достаточно легко проектировать и программировать алгоритмы решения задач с использованием этого метода. Однако время нахождения решения может быть очень велико даже при небольших размерностях задачи (количестве исходных данных), причём настолько велико (может составлять годы или даже века), что о практическом применении не может быть и речи. Поэтому при проектировании таких алгоритмов, обязательно нужно теоретически оценивать время их работы на конкретных данных. Существуют также задачи выбора, для решения которых можно построить уникальные, «быстрые» алгоритмы, позволяющие быстро получить решение даже при больших размерностях задачи. Метод поиска с возвратом в таких задачах применять неэффективно.

См. также

• Рекурсия
• Метод ветвей и границ

Ссылки

• interactive animation of a backtracking algorithm
• Gurari, Eitan. Backtracking algorithms CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms  (неопр.) (1999). Архивировано 17 марта 2007 года.