Алгоритм поиска с возвратом (откатом)

Введение

Алгоритм поиска

Алгоритм поиска по строке, используемый в математической оптимизации. Метод перебора с возвратом (бэктрекинг) – это класс алгоритмов для поиска решений некоторых вычислительных задач, в частности, задач удовлетворения ограничений, который инкрементно строит варианты решений и отбрасывает вариант ("возвращается назад"), как только определяет, что его невозможно дополнить до допустимого решения. Классическим примером использования бэктрекинга является задача о восьми ферзях, которая требует найти все расстановки восьми шахматных ферзей на стандартной шахматной доске так, чтобы ни один ферзь не атаковал другого. В стандартном подходе к бэктрекингу, частичные варианты представляют собой расстановку k ферзей в первых k строках доски, все в разных строках и столбцах. Любой частичный вариант, содержащий два ферзя, атакующих друг друга, может быть отброшен. Бэктрекинг применим только к задачам, которые допускают понятие "частичного варианта решения" и относительно быструю проверку возможности его дополнения до допустимого решения. Он бесполезен, например, для поиска заданного значения в неупорядоченной таблице. Однако, когда он применим, бэктрекинг часто значительно быстрее, чем полный перебор всех вариантов, поскольку позволяет исключить множество вариантов с помощью одной проверки. Бэктрекинг является важным инструментом для решения задач удовлетворения ограничений, таких как кроссворды, словесная арифметика, судоку и многие другие головоломки. Он часто является наиболее удобным методом для разбора, для задачи о рюкзаке и других комбинаторных задачах оптимизации. Это также стратегия выполнения программы, используемая в языках программирования Icon, Planner и Prolog. Бэктрекинг опирается на заданные пользователем "процедуры-черные ящики", которые определяют решаемую задачу, природу частичных вариантов и способы их расширения до полных вариантов. Следовательно, это метаэвристика, а не конкретный алгоритм, хотя, в отличие от многих других метаэвристик, он гарантированно находит все решения конечной задачи за конечное время. Термин "бэктрекинг" был введен американским математиком Д. Х. Лемером в 1950-х годах. Пионерский язык обработки строк SNOBOL (1962) мог быть первым, предоставившим встроенную общую возможность бэктрекинга.

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned. Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate many candidates with a single test. Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient technique for parsing, for the knapsack problem and other combinatorial optimization problems. It is also the program execution strategy used in the programming languages Icon, Planner and Prolog. Backtracking depends on user given "black box procedures" that define the problem to be solved, the nature of the partial candidates, and how they are extended into complete candidates. It is therefore a metaheuristic rather than a specific algorithm – although, unlike many other meta heuristics, it is guaranteed to find all solutions to a finite problem in a bounded amount of time. The term "backtrack" was coined by American mathematician D. H. Lehmer in the 1950s. The pioneer string processing language SNOBOL (1962) may have been the first to provide a built in general backtracking facility.

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

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

Учитывания по использованию

Процедура отклонения должна быть булевой функцией, возвращающей true только в том случае, если она уверена, что никакое возможное расширение кандидата c не является допустимым решением для задачи P. Если процедура не может прийти к однозначному заключению, она должна возвращать false. Неверный результат true может привести к тому, что процедура возврата (backtrack) пропустит некоторые допустимые решения. Процедура может предполагать, что reject(P,t) возвращает false для каждого предка t кандидата c в дереве поиска. С другой стороны, эффективность алгоритма возврата зависит от того, чтобы reject возвращал true для кандидатов, максимально близких к корню. Если reject всегда возвращает false, алгоритм все равно найдет все решения, но это будет эквивалентно полному перебору. Процедура accept должна возвращать true, если кандидат c является полным и допустимым решением для экземпляра задачи P, и false в противном случае. Она может предполагать, что частичный кандидат c и все его предки в дереве прошли проверку отклонения. Общий псевдокод выше не предполагает, что допустимые решения всегда являются листьями потенциального дерева поиска. Иными словами, он допускает возможность того, что допустимое решение для P может быть дополнительно расширено для получения других допустимых решений. Процедуры first и next используются алгоритмом возврата для перечисления дочерних узлов узла c дерева, то есть кандидатов, отличающихся от c на один шаг расширения. Вызов first(P,c) должен возвращать первого дочернего узла c в некотором порядке, а вызов next(P,s) должен возвращать следующего брата узла s в том же порядке. Обе функции должны возвращать специальный "пустой" кандидат, если запрошенный дочерний узел не существует. Вместе функции root, first и next определяют множество частичных кандидатов и потенциальное дерево поиска. Их следует выбирать таким образом, чтобы каждое решение задачи P встречалось где-то в дереве, и ни один частичный кандидат не встречался более одного раза. Кроме того, они должны обеспечивать эффективное и надежное условие отклонения.

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

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