Возврат
Обратное отслеживание — это класс алгоритмов для поиска решений некоторых вычислительных задач , в частности проблем удовлетворения ограничений , который постепенно создает кандидатов для решений и отказывается от кандидата («возврат»), как только он определяет, что кандидат не может быть завершен до заданного значения. действительное решение. [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 в качестве параметра и выполнять следующее:
- root ( P ): вернуть частичного кандидата в корень дерева поиска.
- ignore ( P , c ): возвращает true только в том случае, если частичный кандидат c не заслуживает завершения.
- Accept ( P , c ): возвращает true , если c является решением P , и false в противном случае.
- first ( P , c ): сгенерируйте первое расширение кандидата c .
- next ( P , s ): генерирует следующее альтернативное расширение кандидата после расширения s .
- вывод ( P , c ): используйте решение c из 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 . Алгоритм можно изменить так, чтобы он останавливался после нахождения первого решения или заданного количества решений; или после тестирования указанного количества частичных кандидатов, или после затрат определенного количества процессорного времени.
Примеры [ править ]
Примеры использования обратного отслеживания для решения головоломок или проблем:
- Такие головоломки , как головоломка с восемью королевами , кроссворды , словесная арифметика , судоку. [номер 1] и пасьянс «Колышек» .
- Задачи комбинаторной оптимизации, такие как синтаксический анализ и задача о рюкзаке .
- Языки целенаправленного программирования, такие как Icon , Planner и Prolog , которые используют внутренний возврат для генерации ответов.
- Алгоритм DPLL для решения булевой задачи о выполнимости .
Ниже приведен пример использования обратного отслеживания для задачи удовлетворения ограничений :
Удовлетворение ограничений [ править ]
Общая проблема удовлетворения ограничений состоит в нахождении списка целых чисел 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 элементов.
Обычно лучше упорядочить список переменных так, чтобы он начинался с наиболее важных (т.е. с тех, которые имеют наименьшее количество вариантов значений или которые оказывают большее влияние на последующие выборы).
Можно также разрешить следующей функции выбирать, какую переменную следует назначить при расширении частичного кандидата, на основе значений уже назначенных ею переменных. Дальнейшие улучшения могут быть получены с помощью техники распространения ограничений .
Помимо сохранения минимальных значений восстановления, используемых при резервном копировании, реализации обратного отслеживания обычно сохраняют переменный след для записи истории изменения значений. Эффективная реализация позволит избежать создания переменной записи следа между двумя последовательными изменениями, когда нет точки выбора, поскольку возврат приведет к удалению всех изменений как одной операции.
Альтернативой следу переменной является сохранение отметки времени последнего изменения, внесенного в переменную. Временная метка сравнивается с временной меткой точки выбора. Если точка выбора имеет связанное время позже, чем время переменной, нет необходимости возвращать переменную при возврате к точке выбора, поскольку она была изменена до появления точки выбора.
См. также [ править ]
- Нить Ариадны (логика) – Метод решения задач
- Обратный прыжок - в алгоритмах обратного отслеживания метод, уменьшающий пространство поиска.
- Обратная цепочка - Метод формирования выводов
- Алгоритм перечисления — алгоритм, который печатает все решения проблемы.
- Алгоритмы решения судоку - Алгоритмы решения судоку
Примечания [ править ]
- ^ См. Алгоритмы решения судоку .
Ссылки [ править ]
- ^ Гурари, Эйтан (1999). «CIS 680: СТРУКТУРЫ ДАННЫХ: Глава 19: Алгоритмы поиска с возвратом» . Архивировано из оригинала 17 марта 2007 года.
- ^ Бьер, А.; Хойле, М.; ван Маарен, Х. (29 января 2009 г.). Справочник по выполнимости . iOS Пресс. ISBN 978-1-60750-376-7 .
- ^ Уотсон, Дес (22 марта 2017 г.). Практический подход к построению компилятора . Спрингер. ISBN 978-3-319-52789-5 .
- ^ Росси, Франческа; ван Бик, Питер; Уолш, Тоби (август 2006 г.). «Удовлетворение ограничениями: новая парадигма» . Справочник по программированию с ограничениями . Амстердам : Эльзевир . п. 14. ISBN 978-0-444-52726-4 . Проверено 30 декабря 2008 г.
Дальнейшее чтение [ править ]
- Жиль Брассар, Пол Брэтли (1995). Основы алгоритмики . Прентис-Холл. ISBN 9780133350685 .
Внешние ссылки [ править ]
- HBmeyer.de , Интерактивная анимация алгоритма возврата
- Решение комбинаторных задач с помощью STL и обратного отслеживания , статья и исходный код C++ для общей реализации обратного отслеживания