Возврат

Обратное отслеживание — это класс алгоритмов для поиска решений некоторых вычислительных задач , в частности проблем удовлетворения ограничений , который постепенно создает кандидатов для решения и отказывается от кандидата («возврат»), как только он определяет, что кандидат не может быть завершен до заданного значения. действительное решение. ^[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 )), где возврат — это следующая рекурсивная процедура:

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

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

Приведенный выше псевдокод вызовет вывод для всех кандидатов, которые являются решением данного экземпляра 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 ] . Тогда корневым кандидатом будет пустой список (). Тогда первая последующие и процедуры будут

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])

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

Вызов отклонения ( P , c ) должен возвращать значение true, если ограничение 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], будут проверены дальше в дереве поиска.

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

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

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

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

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

См. также [ править ]

Нить Ариадны (логика) – Метод решения задач
Обратный прыжок - в алгоритмах обратного отслеживания метод, уменьшающий пространство поиска.
Обратная цепочка - Метод формирования выводов
Алгоритм перечисления — алгоритм, который печатает все решения проблемы.
Алгоритмы решения судоку - Алгоритмы решения судоку

Примечания [ править ]

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

Ссылки [ править ]

^ Гурари, Эйтан (1999). «CIS 680: СТРУКТУРЫ ДАННЫХ: Глава 19: Алгоритмы поиска с возвратом» . Архивировано из оригинала 17 марта 2007 года.
^ Бьер, А.; Хойле, М.; ван Маарен, Х. (29 января 2009 г.). Справочник по выполнимости . ИОС Пресс. 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++ для общей реализации поиска с возвратом

[5] См . Алгоритмы решения судоку .

[1] Гурари, Эйтан (1999). «CIS 680: СТРУКТУРЫ ДАННЫХ: Глава 19: Алгоритмы поиска с возвратом» . Архивировано из оригинала 17 марта 2007 года.

[BiereHeule2009-2] Бьер, А.; Хойле, М.; ван Маарен, Х. (29 января 2009 г.). Справочник по выполнимости . ИОС Пресс. ISBN 978-1-60750-376-7 .

[Watson2017-3] Уотсон, Дес (22 марта 2017 г.). Практический подход к построению компилятора . Спрингер. ISBN 978-3-319-52789-5 .

[4] Росси, Франческа; ван Бик, Питер; Уолш, Тоби (август 2006 г.). «Удовлетворение ограничениями: новая парадигма» . Справочник по программированию с ограничениями . Амстердам : Эльзевир . п. 14. ISBN 978-0-444-52726-4 . Проверено 30 декабря 2008 г.

[1]

[2]

[3]

[4]

[номер 1]

v т и Алгоритмы разбора
Сверху вниз	Эрли LL Рекурсивный спуск Хвостовая рекурсия
Вверх дном	Приоритет Простой Оператор Маневровый двор ЛР Простой смотреть вперед Канонический Обобщенный ГАЛОЧКА Рекурсивное восхождение Shift-уменьшить
Смешанное, другое	Комбинатор Диаграмма Левый угол Статистический
Связанные темы	ПЭГ Определенная грамматика предложения Детерминированный анализ Динамическое программирование Мемоизация Генератор парсера ЛАЛР Дерево разбора АСТ Бессканерный парсинг История создания компилятора Сравнение генераторов парсеров Грамматика приоритета операторов

v т и Структуры данных и алгоритмы
Структуры данных	Множество Ассоциативный массив Бинарное дерево поиска Дерево Фенвика График Хэш-таблица Куча Связанный список Очередь Дерево сегментов Куча Нить Дерево Трие
Алгоритмы	Возврат Бинарный поиск Поиск в ширину Поиск методом перебора Поиск в глубину Разделяй и властвуй Динамическое программирование Обход графа Складывать Жадный Хэш-функция Минимакс Онлайн Рандомизированный Рекурсия Поиск корней Сортировка Потоковое вещание Развертка линии Поиск строк Топологическая сортировка
Список структур данных Список алгоритмов