Обратный поиск

редактировать

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

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

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

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

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

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

Содержание

  • 1 Описание метода
    • 1.1 Псевдокод
    • 1.2 Рекомендации по использованию
    • 1.3 Варианты ранней остановки
  • 2 Примеры
    • 2.1 Удовлетворение ограничений
  • 3 См. Также
  • 4 Примечания
  • 5 Ссылки
  • 6 Дополнительная литература
  • 7 Внешние ссылки

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

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

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

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

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

Псевдокод

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

  1. root (P): возвращать частичного кандидата в корень дерева поиска.
  2. reject (P, c): возвращает истину, только если частичный кандидат 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, соответствующее приложению.

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

процедура bt (c) isifreject (P, c) затем return если accept (P, c) затем output (P, c) s ← first ( P, c) while s ≠ NULL do bt (s) s ← next (P, s)

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

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

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

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

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

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

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

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

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

Примеры

A Судоку, решаемые путем поиска с возвратом.

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

Ниже приведен пример, в котором для решения задачи удовлетворения ограничений :

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

используется обратное отслеживание. Общая проблема удовлетворения ограничений состоит в поиске списка целые числа 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]. Тогда корневым кандидатом будет пустой список (). Тогда первая и следующая процедуры будут выглядеть так:

function first (P, c) is k ← length (c) if k = n then return NULL elsereturn (c [1], c [2],…, c [k], 1)
функция next (P, s) равно k ← length (s), если s [k] = m, затемreturn NULL else return (s [1], s [2],…, s [k - 1], 1 + s [k])

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

Отклонение вызова (P, c) должно возвращать истину, если ограничение F не может быть удовлетворено ни одним списком из n целых чисел, который начинается с k элементов c. Чтобы возврат с возвратом был эффективным, должен быть способ обнаружить эту ситуацию, по крайней мере для некоторых кандидатов c, без перечисления всех этих m 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], будут проверяться дальше в дереве поиска.

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

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

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

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

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

См. Также

Примечания

Ссылки

Дополнительная литература

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

Последняя правка сделана 2021-05-11 05:37:36
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте