Обратное отслеживание — это класс алгоритмов для поиска решений некоторых вычислительных задач , в частности проблем удовлетворения ограничений , который постепенно создает кандидатов для решения и отказывается от кандидата («возврат»), как только он определяет, что кандидат не может быть завершен до заданного значения. действительное решение. [1]
Классическим хрестоматийным примером использования обратного поиска является головоломка с восемью ферзями , которая требует расположения восьми шахматных ферзей на стандартной шахматной доске так, чтобы ни один ферзь не атаковал другого. В обычном подходе с возвратом частичные кандидаты представляют собой расположение k ферзей в первых k строках доски, причем все в разных строках и столбцах. От любого частичного решения, содержащего двух взаимно атакующих ферзей, можно отказаться.
Поиск с возвратом можно применять только для задач, которые допускают концепцию «частичного решения-кандидата» и относительно быструю проверку того, можно ли завершить его до допустимого решения. Например, он бесполезен для поиска заданного значения в неупорядоченной таблице. Однако, когда это применимо, обратный поиск часто происходит намного быстрее, чем полный перебор всех полных кандидатов, поскольку он может исключить множество кандидатов с помощью одного теста.
Возврат — важный инструмент для решения задач удовлетворения ограничений , [2] таких как кроссворды , словесная арифметика , судоку и многие другие головоломки. Часто это наиболее удобный метод анализа [3] задачи о рюкзаке и других задач комбинаторной оптимизации . Это также стратегия выполнения программы, используемая в языках программирования Icon , Planner и Prolog .
Возврат зависит от заданных пользователем « процедур черного ящика », которые определяют решаемую проблему, природу частичных кандидатов и то, как они расширяются до полных кандидатов. Таким образом, это скорее метаэвристика , чем конкретный алгоритм, хотя, в отличие от многих других метаэвристик, он гарантированно находит все решения конечной задачи за ограниченный промежуток времени.
Термин «обратный путь» был придуман американским математиком Д. Х. Лемером в 1950-х годах. [4] Пионерский язык обработки строк SNOBOL (1962), возможно, был первым, кто предоставил встроенную возможность общего поиска с возвратом.
Алгоритм обратного поиска перечисляет набор частичных кандидатов , которые, в принципе, можно дополнить различными способами, чтобы дать все возможные решения данной задачи. Завершение осуществляется постепенно, посредством последовательности шагов расширения-кандидата.
Концептуально частичные кандидаты представлены как узлы древовидной структуры , потенциального дерева поиска. Каждый частичный кандидат является родителем кандидатов, которые отличаются от него одним шагом расширения; листья дерева — это частичные кандидаты, которые не могут быть расширены дальше.
Алгоритм поиска с возвратом обходит это дерево поиска рекурсивно , от корня вниз, в порядке глубины . В каждом узле c алгоритм проверяет, можно ли завершить c до допустимого решения. Если это невозможно, все поддерево с корнем в c пропускается ( обрезается ). В противном случае алгоритм (1) проверяет, является ли c само по себе допустимым решением, и если да, то сообщает об этом пользователю; и (2) рекурсивно перечисляет все поддеревья c . Два теста и дочерние элементы каждого узла определяются процедурами, заданными пользователем.
Следовательно, фактическое дерево поиска , по которому проходит алгоритм, является лишь частью потенциального дерева. Общая стоимость алгоритма равна количеству узлов фактического дерева, умноженному на стоимость получения и обработки каждого узла. Этот факт следует учитывать при выборе потенциального дерева поиска и реализации теста сокращения.
Чтобы применить возврат к определенному классу задач, необходимо предоставить данные P для конкретного экземпляра проблемы, которую необходимо решить, а также шесть процедурных параметров : root , ignore , Accept , First , Next и Output . Эти процедуры должны принимать данные экземпляра P в качестве параметра и выполнять следующее:
Алгоритм обратного отслеживания сводит проблему к обратному отслеживанию вызова ( P , root ( P )), где возврат — это следующая рекурсивная процедура:
процедура backtrack(P, c) - если отклонить(P, c), то вернуть , если принять(P, c) , то вывести(P, c) s ← первый(P, c) пока s ≠ NULL , делайте возврат(P, с) s ← следующий(P, s)
Процедура отклонения должна быть функцией с логическим значением , которая возвращает true только в том случае , если точно известно, что никакое возможное расширение c не является допустимым решением для P . Если процедура не может прийти к определенному выводу, она должна вернуть false . Неправильный истинный результат может привести к тому, что процедура возврата пропустит некоторые действительные решения. Процедура может предполагать, что ignore ( P , t ) вернул ложь для каждого предка t из c в дереве поиска.
С другой стороны, эффективность алгоритма обратного отслеживания зависит от отклонения, возвращающего true для кандидатов, которые находятся как можно ближе к корню. Если ignore всегда возвращает false , алгоритм все равно найдет все решения, но это будет эквивалентно перебору.
Процедура принятия должна возвращать true, если c является полным и допустимым решением для экземпляра проблемы P , и false в противном случае. Можно предположить, что частичный кандидат c и все его предки в дереве прошли тест на отбраковку .
Общий псевдокод, приведенный выше, не предполагает, что действительные решения всегда являются листьями потенциального дерева поиска. Другими словами, он допускает возможность того, что правильное решение для P может быть расширено для получения других допустимых решений.
Первая и следующая процедуры используются алгоритмом обратного отслеживания для перечисления дочерних элементов узла 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 ← длина(с) если 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 .
Вызов отклонения ( 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 ] , то процедура отклонения может просто проверить термины F [ i ] , которые зависят только от переменных x [1], …, x [ k ] , и вернуть true , если какой-либо из этих терминов возвращает false . Фактически, для отклонения необходимо проверить только те термины, которые действительно зависят от x [ k ], поскольку термины, которые зависят только от x [1], …, x [ k − 1] , будут проверены дальше в дереве поиска.
Предполагая, что отказ реализован, как указано выше, тогда методу принятия ( P , c ) нужно только проверить, является ли c полным, то есть имеет ли он n элементов.
Обычно лучше упорядочить список переменных так, чтобы он начинался с наиболее важных (т. е. с тех, которые имеют наименьшее количество вариантов значений или которые оказывают большее влияние на последующие выборы).
Можно также разрешить следующей функции выбирать, какую переменную следует назначить при расширении частичного кандидата, на основе значений уже назначенных ею переменных. Дальнейшие улучшения могут быть получены с помощью техники распространения ограничений .
Помимо сохранения минимальных значений восстановления, используемых при резервном копировании, реализации обратного отслеживания обычно сохраняют переменный след для записи истории изменения значений. Эффективная реализация позволит избежать создания переменной записи следа между двумя последовательными изменениями, когда нет точки выбора, поскольку возврат приведет к удалению всех изменений как одной операции.
Альтернативой следу переменной является сохранение отметки времени последнего изменения, внесенного в переменную. Временная метка сравнивается с временной меткой точки выбора. Если точка выбора имеет связанное время позже, чем время переменной, нет необходимости возвращать переменную при возврате к точке выбора, поскольку она была изменена до появления точки выбора.