Откат — это класс алгоритмов для поиска решений некоторых вычислительных задач , в частности задач удовлетворения ограничений , который постепенно выстраивает кандидатов на решения и отказывается от кандидата («откат»), как только определяет, что кандидат не может быть доведен до допустимого решения. [1]
Классический пример из учебника по использованию отката — головоломка с восемью ферзями , которая требует всех расположений восьми шахматных ферзей на стандартной шахматной доске так, чтобы ни один ферзь не атаковал другого. В обычном подходе отката частичные кандидаты — это расположения k ферзей в первых k рядах доски, все в разных рядах и столбцах. Любое частичное решение, которое содержит двух взаимно атакующих ферзей, может быть отклонено.
Откат можно применять только для задач, которые допускают концепцию «частичного решения-кандидата» и относительно быструю проверку того, может ли он быть завершен до допустимого решения. Он бесполезен, например, для поиска заданного значения в неупорядоченной таблице. Однако, когда он применим, откат часто оказывается намного быстрее, чем полный перебор всех полных кандидатов, поскольку он может исключить многих кандидатов с помощью одной проверки.
Откат назад является важным инструментом для решения задач удовлетворения ограничений , [2] таких как кроссворды , устная арифметика , судоку и многие другие головоломки. Часто это наиболее удобный метод для разбора , [3] для задачи о рюкзаке и других задач комбинаторной оптимизации . Это также стратегия выполнения программы, используемая в языках программирования Icon , Planner и Prolog .
Обратный поиск зависит от заданных пользователем " процедур черного ящика ", которые определяют решаемую проблему, природу частичных кандидатов и то, как они расширяются до полных кандидатов. Таким образом, это метаэвристика, а не конкретный алгоритм – хотя, в отличие от многих других метаэвристик, он гарантированно находит все решения конечной проблемы за ограниченное время.
Термин «возврат» был придуман американским математиком Д. Х. Лемером в 1950-х годах. [4] Пионерский язык обработки строк SNOBOL (1962), возможно, был первым, кто предоставил встроенную общую возможность возврата.
Алгоритм обратного отслеживания перечисляет набор частичных кандидатов , которые, в принципе, могут быть завершены различными способами, чтобы дать все возможные решения данной проблемы. Завершение выполняется постепенно, последовательностью шагов расширения кандидатов.
Концептуально частичные кандидаты представлены как узлы древовидной структуры , потенциального дерева поиска. Каждый частичный кандидат является родителем кандидатов, которые отличаются от него одним шагом расширения; листья дерева являются частичными кандидатами, которые не могут быть расширены дальше.
Алгоритм обратного отслеживания обходит это дерево поиска рекурсивно , от корня вниз, в порядке поиска в глубину . В каждом узле c алгоритм проверяет, можно ли завершить c до допустимого решения. Если это невозможно, все поддерево с корнем в c пропускается ( обрезается ). В противном случае алгоритм (1) проверяет, является ли само c допустимым решением, и если это так, сообщает об этом пользователю; и (2) рекурсивно перечисляет все поддеревья c . Два теста и дочерние элементы каждого узла определяются процедурами, заданными пользователем.
Таким образом, фактическое дерево поиска , которое проходит алгоритм, является лишь частью потенциального дерева. Общая стоимость алгоритма равна количеству узлов фактического дерева, умноженному на стоимость получения и обработки каждого узла. Этот факт следует учитывать при выборе потенциального дерева поиска и реализации теста обрезки.
Чтобы применить откат к определенному классу проблем, необходимо предоставить данные P для конкретного экземпляра проблемы, которую нужно решить, и шесть процедурных параметров : root , reject , accept , first , next и output . Эти процедуры должны принимать данные экземпляра P в качестве параметра и выполнять следующие действия:
Алгоритм обратного отслеживания сводит задачу к вызову backtrack ( P , root ( P )), где backtrack — это следующая рекурсивная процедура:
процедура backtrack(P, c) — если reject(P, c) , то return , если accept(P, c) , то output(P, c) s ← первый(P, c) пока s ≠ NULL делать возврат назад(P, s) с ← следующий(P, с)
Процедура reject должна быть функцией с булевым значением , которая возвращает true только в том случае, если она уверена, что никакое возможное расширение c не является допустимым решением для P . Если процедура не может прийти к определенному выводу, она должна возвращать false . Неправильный результат true может привести к тому, что процедура backtrack пропустит некоторые допустимые решения. Процедура может предполагать, что reject ( P , t ) вернула false для каждого предка t c в дереве поиска.
С другой стороны, эффективность алгоритма обратного отслеживания зависит от того, возвращает ли reject true для кандидатов, которые находятся максимально близко к корню. Если reject всегда возвращает false , алгоритм все равно найдет все решения, но это будет эквивалентно поиску методом грубой силы.
Процедура принятия должна возвращать true, если c является полным и допустимым решением для экземпляра проблемы P , и false в противном случае. Она может предположить, что частичный кандидат c и все его предки в дереве прошли тест на отклонение .
Общий псевдокод выше не предполагает, что допустимые решения всегда являются листьями потенциального дерева поиска. Другими словами, он допускает возможность того, что допустимое решение для P может быть расширено для получения других допустимых решений.
Процедуры first и next используются алгоритмом обратного отслеживания для перечисления потомков узла c дерева, то есть кандидатов, которые отличаются от c одним шагом расширения. Вызов first ( P , c ) должен выдать первого потомка c в некотором порядке; а вызов next ( P , s ) должен вернуть следующего брата узла s в этом порядке. Обе функции должны возвращать отличительного кандидата "NULL", если запрошенный потомок не существует.
Вместе функции root , first и next определяют набор частичных кандидатов и потенциальное дерево поиска. Они должны быть выбраны так, чтобы каждое решение P встречалось где-то в дереве, и ни один частичный кандидат не встречался более одного раза. Более того, они должны допускать эффективный и действенный предикат отклонения .
Псевдокод выше вызовет вывод для всех кандидатов, которые являются решением для данного экземпляра P. Алгоритм можно модифицировать так, чтобы он останавливался после нахождения первого решения или указанного количества решений; или после проверки указанного количества частичных кандидатов, или после траты заданного количества процессорного времени.
Примеры, в которых возврат может использоваться для решения головоломок и задач, включают в себя:
Ниже приведен пример использования возврата для решения проблемы удовлетворения ограничений :
Общая задача удовлетворения ограничений состоит в нахождении списка целых чисел x = ( x [1], x [2], …, x [ n ]) , каждое из которых находится в некотором диапазоне {1, 2, …, m }, который удовлетворяет некоторому произвольному ограничению (булевой функции) F .
Для этого класса задач данные экземпляра P будут целыми числами m и n и предикатом F. В типичном решении этой задачи с возвратом можно определить частичного кандидата как список целых чисел c = ( c [1], c [2], …, c [k]) для любого k от 0 до n , которые должны быть назначены первым k переменным x [1], x [2], …, x [ k ] . Корневым кандидатом тогда будет пустой список (). Первая и следующая процедуры тогда будут
функция first(P, c) есть к ← длина(с) если k = n, то вернуть NULL, иначе вернуть (c[1], c[2], ..., c[k], 1)
Функция next(P, s) — это k ← длина(ы) если s[k] = m , то вернуть NULL, иначе вернуть (s[1], s[2], ..., s[k − 1], 1 + s[k])
Здесь длина ( c ) — это количество элементов в списке c .
Вызов reject ( P , c ) должен возвращать true, если ограничение F не может быть удовлетворено никаким списком из n целых чисел, который начинается с k элементов c . Для того чтобы возврат был эффективным, должен быть способ обнаружить эту ситуацию, по крайней мере для некоторых кандидатов c , без перечисления всех этих m n − k n -кортежей.
Например, если F является конъюнкцией нескольких булевых предикатов, F = F [1] ∧ F [2] ∧ … ∧ F [ p ] , и каждый F [ i ] зависит только от небольшого подмножества переменных x [1], …, x [ n ] , то процедура reject может просто проверить термины F [ i ], которые зависят только от переменных x [1], …, x [ k ] , и вернуть true , если любой из этих терминов возвращает false . Фактически, reject нужно проверить только те термины, которые зависят от x [ k ], поскольку термины, которые зависят только от x [1], …, x [ k − 1], будут проверены выше в дереве поиска.
Если предположить, что reject реализовано так, как указано выше, то accept ( P , c ) нужно только проверить, является ли c полным, то есть содержит ли он n элементов.
Обычно лучше упорядочить список переменных так, чтобы он начинался с наиболее важных (т. е. с тех, у которых меньше всего вариантов значений или которые оказывают большее влияние на последующий выбор).
Можно также разрешить следующей функции выбирать, какую переменную следует назначить при расширении частичного кандидата, на основе значений переменных, уже назначенных ею. Дальнейшие улучшения могут быть получены с помощью техники распространения ограничений .
Помимо сохранения минимальных значений восстановления, используемых при резервном копировании, реализации обратного отслеживания обычно сохраняют переменный след, чтобы записывать историю изменения значений. Эффективная реализация позволит избежать создания переменной записи следа между двумя последовательными изменениями, когда нет точки выбора, поскольку обратное отслеживание сотрет все изменения как одну операцию.
Альтернативой переменной trail является сохранение временной метки последнего изменения переменной. Временная метка сравнивается с временной меткой точки выбора. Если точка выбора имеет связанное время позже, чем у переменной, нет необходимости возвращать переменную при откате точки выбора, так как она была изменена до того, как произошла точка выбора.