Возврат - Backtracking

Для алгоритма поиска строки , используемого в неограниченной оптимизации , см. Поиск строки с возвратом .
Алгоритмы поиска по графам и деревьям
Списки
похожие темы

Отслеживание с возвратом - это общий алгоритм для поиска решений некоторых вычислительных проблем , в частности проблем удовлетворения ограничений , который постепенно создает кандидатов для решений и оставляет кандидата («откат»), как только он определяет, что кандидат не может быть завершен до допустимого уровня. решение.

Классический учебный пример использования обратного отслеживания - это головоломка с восемью ферзями , в которой запрашиваются все расстановки восьми шахматных ферзей на стандартной шахматной доске, чтобы ни один ферзь не напал на других. В обычном подходе с возвратом частичные кандидаты - это расположение k ферзей в первых k строках доски, все в разных строках и столбцах. От любого частичного решения, содержащего двух взаимно атакующих ферзей, можно отказаться.

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

Поиск с возвратом - важный инструмент для решения проблем удовлетворения ограничений , таких как кроссворды , словесная арифметика , судоку и многие другие головоломки. Часто это наиболее удобный метод для синтаксического анализа , для задачи о ранце и других задач комбинаторной оптимизации . Это также основа так называемых языков логического программирования, таких как Icon , Planner и Prolog .

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

Термин «возврат» был придуман американским математиком Д.Х. Лемером в 1950-х годах. Пионерский язык обработки строк SNOBOL (1962), возможно, был первым, кто предоставил встроенные средства общего поиска с возвратом.

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

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

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

Алгоритм поиска с возвратом рекурсивно просматривает это дерево поиска от корня вниз в порядке глубины . В каждом узле c алгоритм проверяет, можно ли завершить c до допустимого решения. В противном случае все поддерево с корнем в c пропускается ( обрезается ). В противном случае алгоритм (1) проверяет, является ли c правильным решением, и, если да, сообщает об этом пользователю; и (2) рекурсивно перечисляет все поддеревья c . Два теста и дочерние элементы каждого узла определяются пользовательскими процедурами.

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

Псевдокод

Чтобы применить обратное отслеживание к определенному классу проблем, необходимо предоставить данные 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 в соответствии с приложением.

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

procedure backtrack(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(s)
        s ← next(P, s)

Соображения по использованию

Отклонять процедуру должна быть булевой функцией , которая возвращает верно только тогда , когда он уверен , что не возможно расширением с не является правильным решением для P . Если процедура не может прийти к определенному выводу, она должна вернуть false . Неправильный истинный результат может привести к тому, что процедура bt пропустит некоторые действительные решения. Процедура может предполагать, что reject ( P , t ) вернул false для каждого предка t элемента c в дереве поиска.

С другой стороны, эффективность алгоритма поиска с возвратом зависит от отклонения, возвращающего истину для кандидатов, которые находятся как можно ближе к корню. Если reject всегда возвращает false , алгоритм все равно найдет все решения, но это будет эквивалентно перебору.

Процедура accept должна возвращать true, если c является полным и действительным решением для экземпляра проблемы P , и false в противном случае. Он может предположить, что частичный кандидат c и все его предки в дереве прошли тест отклонения .

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

В первые и последующие процедуры используются алгоритмом обратного прослеживания для перечисления дочерних узлов с дерева, то есть кандидаты , которые отличаются от 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 .

Для этого класса задач, данные экземпляра Р был бы целые числа т и п , а предикат Р . В типичном решении этой проблемы с возвратом можно определить частичного кандидата как список целых чисел c = ( c [1], c [2],…, c [k]) для любого k от 0 до n , что присваиваются первым k переменным x [1], x [2],…, x [ k ] . Тогда корневым кандидатом будет пустой список (). Тогда первая и следующая процедуры будут 

function first(P, c) is
    k ← length(c)
    if k = n then
        return NULL
    else
        return (c[1], c[2], …, c[k], 1)

function next(P, s) is
    k ← length(s)
    if s[k] = m then
        return NULL
    else
        return (s[1], s[2], …, s[k − 1], 1 + s[k])

Здесь length ( c ) - это количество элементов в списке c .

Вызова отвергают ( Р , гр ) должна возвращать верно , если ограничение Р не может быть удовлетворено любым списком п целых чисел , который начинается с K элементов с . Чтобы обратное отслеживание было эффективным, должен быть способ обнаружить эту ситуацию, по крайней мере, для некоторых кандидатов 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 ] , и вернуть истину, если какой-либо из этих терминов вернет ложь . Фактически, для отклонения необходимо проверять только те термины, которые действительно зависят от x [ k ], поскольку термины, которые зависят только от x [1],…, x [ k - 1], будут проверяться дальше в дереве поиска.

Предполагая, что отклонение реализовано, как указано выше, тогда accept ( P , c ) должен только проверить, является ли c полным, то есть имеет ли оно n элементов.

Как правило, лучше упорядочить список переменных так, чтобы он начинался с самых критических (то есть с тех, у которых меньше всего вариантов значений, или которые имеют большее влияние на последующий выбор).

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

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

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

Смотрите также

Заметки

Рекомендации

дальнейшее чтение

Внешние ссылки