Возврат - Backtracking

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

Возврат генерал алгоритм для поиска всех (или некоторых) решений некоторых вычислительные проблемы, особенно проблемы удовлетворения ограничений, который постепенно создает кандидатов для решений и отклоняет кандидата («откат назад»), как только он определяет, что кандидат не может быть завершен до допустимого решения.[1][2]

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

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

Поиск с возвратом - важный инструмент для решения проблемы удовлетворения ограничений,[3] Такие как кроссворды, словесная арифметика, Судоку, и многие другие головоломки. Часто это самый удобный (если не самый эффективный[нужна цитата ]) техника для разбор,[4] для проблема с рюкзаком и другие комбинаторная оптимизация проблемы. Это также основа так называемого логическое программирование языки, такие как Значок, Планировщик и Пролог.

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

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

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

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

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

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

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

Псевдокод

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

  1. корень(п): вернуть частичного кандидата в корень дерева поиска.
  2. отклонять(п,c): возвращаться истинный только если частичный кандидат c доделывать не стоит.
  3. принимать(п,c): возвращаться истинный если c это решение п, и ложный иначе.
  4. первый(п,c): создать первое расширение кандидата c.
  5. следующий(п,s): сгенерировать следующее альтернативное расширение кандидата после расширения s.
  6. выход(п,c): используйте решение c из п, в зависимости от приложения.

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

процедура bt (c) является    если отклонить (P, c) тогда возвращаться если принять (P, c) тогда output (P, c) s ← first (P, c) пока s ≠ NULL делать        bt (s) s ← следующая (P, s)

Рекомендации по использованию

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

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

В принимать процедура должна вернуться истинный если c это полное и верное решение для экземпляра проблемы п, и ложный иначе. Можно предположить, что частичный кандидат c и все его предки на дереве прошли отклонять тест.

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

В первый и следующий процедуры используются алгоритмом поиска с возвратом для перечисления потомков узла c дерева, то есть кандидатов, отличных от c за один шаг расширения. Звонок первый(п,c) должен дать первого потомка c, в некотором порядке; и звонок следующий(п,s) должен вернуть следующего брата узла s, в этой последовательности. Обе функции должны возвращать отличительного кандидата "NULL", если запрошенный дочерний элемент не существует.

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

Варианты ранней остановки

Псевдокод выше вызовет выход для всех кандидатов, которые являются решением данного экземпляра п. Алгоритм можно изменить так, чтобы он останавливался после нахождения первого решения или определенного количества решений; или после тестирования указанного количества неполных кандидатов, или после того, как потратили определенную сумму ЦПУ время.

Примеры

А Судоку решается возвратом.

Примеры использования обратного отслеживания для решения головоломок или задач:

Ниже приведен пример использования обратного отслеживания для проблема удовлетворения ограничений:

Удовлетворение ограничений

Генерал проблема удовлетворения ограничений состоит в нахождении списка целых чисел Икс = (Икс[1], Икс[2], …, Икс[п]), каждый в некотором диапазоне {1, 2, …, м}, который удовлетворяет произвольному ограничению (логическая функция) F.

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

функция первый (P, c) является    k ← длина (c) если к = п тогда        возвращаться НОЛЬ еще        возвращаться (c [1], c [2],…, c [k], 1)
функция следующий (P, s) является    k ← длина (и) если s [k] = m тогда        возвращаться НОЛЬ еще        возвращаться (s [1], s [2],…, s [k - 1], 1 + s [k])

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

Звонок отклонять(п, c) должен вернуться истинный если ограничение F не может быть удовлетворен ни одним списком п целые числа, начинающиеся с k элементы c. Чтобы обратное отслеживание было эффективным, должен быть способ обнаружить эту ситуацию, по крайней мере, для некоторых кандидатов. c, не перечисляя все эти мп − k п- пары.

Например, если F это соединение из нескольких булевых предикатов, F = F[1] ∧ F[2] ∧ … ∧ F[п], и каждый F[я] зависит только от небольшого подмножества переменных Икс[1], …, Икс[п], то отклонять процедура может просто проверить условия F[я], которые зависят только от переменных Икс[1], …, Икс[k], и вернуться истинный если какое-либо из этих условий возвращается ложный. Фактически, отклонять нужно только проверить те термины, которые зависят от Икс[k], поскольку члены, зависящие только от Икс[1], …, Икс[k − 1] будут протестированы дальше в дереве поиска.

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

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

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

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

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

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

Примечания

  1. ^ Видеть Алгоритмы решения судоку.

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

  1. ^ Дональд Э. Кнут (1968). Искусство программирования. Эддисон-Уэсли.
  2. ^ Гурари, Эйтан (1999). "CIS 680: СТРУКТУРЫ ДАННЫХ: Глава 19: Алгоритмы обратного отслеживания". Архивировано из оригинал 17 марта 2007 г.
  3. ^ А. Биер; М. Хеул; Х. ван Маарен (29 января 2009 г.). Справочник по выполнимости. IOS Press. ISBN  978-1-60750-376-7.
  4. ^ Де Ватсон (22 марта 2017 г.). Практический подход к построению компилятора. Springer. ISBN  978-3-319-52789-5.
  5. ^ Росси, Франческа; Бик, Питер Ван; Уолш, Тоби (август 2006 г.). «Удовлетворение ограничений: возникающая парадигма». Справочник по программированию в ограничениях. Основы искусственного интеллекта. Амстердам: Эльзевир. п. 14. ISBN  978-0-444-52726-4. Получено 2008-12-30. Битнер и Рейнгольд считают, что Лемер впервые использовал термин «возврат» в 1950-х годах.

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

внешняя ссылка