Далее - компиляция статей из Википедии и других источников.
Общий метод нахождения решения задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М.
Термин "backtrack" был введен в 1950 году американским математиком Дерриком Генри Лемером. Поиск с возвратом практически одновременно и независимо был изобретен многими исследователями еще до его формального описания.
Решение задачи методом поиска с возвратом сводится к последовательному расширению частичного решения. Если на очередном шаге такое расширение провести не удается, то возвращаются к более короткому частичному решению и на этом уровне продолжают поиск дальше. Данный алгоритм позволяет найти все решения поставленной задачи, если они существуют. Для ускорения метода стараются вычисления организовать таким образом, чтобы как можно раньше выявлять заведомо неподходящие варианты. Зачастую это позволяет значительно уменьшить время нахождения решения.
Пусть имеется набор n шагов - M0, M1, …, Mj,… ,Mn-1. Каждый шаг - это линейно упорядоченное множество альтернатив v, которые могут приниматься на этом шаге. Отметим, что множества альтернатив M на разных шагах могут не совпадать по количеству и элементам. На первом шагу может быть 3 альтернативы, на втором - 8 и пр.
k - счетчик шагов, пробегает значения от 0 до n-1.
Вектор v = (v0, v1,…, vk) - кандидат на решение на шаге k. v0 - одна из альтернатив из M0, v1 принадлежит M1, vj принадлежит Mj. То есть:
v = (v0, v1, …, vk)T(vjпринадлежит Mj; j = 0, 1, …, k; k <= n -1)
Пусть G(v) - булева функция, ставящая в соответствие каждому v значение True/False. То есть:
G(v) принадлежит {True, False}.
Векторы v = (v0, v1, …, vk)T, для которых G(v) = True, назовем частичными решениями.
Пусть имеется правило P(v), которое принадлежит {True, False}, в соответствии с которым некоторые из частичных решений могут объявляться полными решениями, то есть решениями нашей задачи.
Примечание: правило P может допускать наличие полного решения как для k = n-1, так и для k << n-1.
Возможна постановка следующих задач:
найти все полные решения или установить отсутствие таковых,
найти хотя бы одно полное решение или установить его отсутствие.
Алгоритм работает следующим образом.
Сначала принимается первый шаг M0. На этом ходу последовательно перебираются альтернативы v из множества M этого шага. Как только альтернатива удовлетворяет условию G(v) = True, то есть находится частичное решение, алгоритм запоминает, какая альтернатива принята на шаге M0 и переходит к следующему шагу M1. На этом шаге также перебираются все альтернативы из M1. С каждой альтернативой производится тестирование получающегося вектора v = (v0, v1) на соответствие G(v) = True. Если альтернатива удовлетворяет G, алгоритм переходит к следующему шагу. Таким образом, с каждым шагом k увеличивается до n-1, вектор v расширяется слева направо. При достижении k значения n-1 после принятия первого vk, удовлетворяющего G, переход к следующему ходу, естественно, не производится. На этом шаге возможно, что по правилу P частичное решение принимается за полное решение. После этого производится переход к следующей альтернативе с оценкой G(v) и P(v).
На каждом шаге, после того, как все альтернативы vk данного шага Mk были перепробованы, производится откат - счетчик шагов k уменьшается на единицу, т.е. производится переход на предыдущий шаг. На этом предыдущем шагу производится перебор vk с тестированием G(v). При нахождении vk такого, что G(v) = True, производится переход к следующему шагу при k < n-1, либо продолжается перебор vk.
В конце концов на каждом шаге альтернатив для перебора уже не будет, алгоритм будет осуществлять возврат до тех пор, пока k не примет значение -1. На этом моменте алгоритм заканчивается.
Данный алгоритм находит все полные решения. Если необходимо только первое полное решение, то необходимо прерывать выполнение алгоритма после того, найдется полное решение.
Реализация алгоритма может находить наилучшее решение из всех полных. Можно Сохранять один вектор полного решения vп.р.наилучш. и каждое последующее полное решение vп.р. сравнивать c vп.р.наилучш. по каким-то параметрам, например длина пути для задачи поиска выхода из лабиринта. Если vп.р. лучше, чем vп.р.наилучш., то vп.р. сохраняем в vп.р.наилучш..
Ценность данного алгоритма в том, что все программы, реализующие его для решения множества задач строятся по единой схеме. Создаются предпосылки создания единой библиотеки классов (для систем, реализованных в парадигме ООП), реализующей алгоритм перебора с возвратом.
Пример: задача расстановки ферзей. Данная задача будет реализована в следующей главе. В той-же главе будет показано, как реализуются задачи перебора с возвратом в библиотеке ИИ МИР.
Далее: 02. Перебор с возвратом - задача ферзей
Оглавление: Перебор с возвратом