Откат - Backtracking


Из Википедии, свободной энциклопедии

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

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

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

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

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

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

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

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

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

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

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

ПСЕВДОКОД

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

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

Алгоритм возвратов сводит задачу к вызову BT ( корневой ( P )), где Ь является следующей рекурсивной процедурой:

procedure bt(c)
  if reject(P,c) then return
  if accept(P,c) then output(P,c)
  s  first(P,c)
  while s  NULL do
    bt(s)
    s  next(P,s)

соображения по использованию

Отклонять процедуру должна быть булевой функцией , которая возвращает верно только тогда , когда он уверен , что не возможно расширением с не является правильным решением для P . Если процедура не может прийти к определенному выводу, он должен возвращать ложь . Неправильный истинный результат может вызвать Ы процедуру пропустить некоторые действительные решения. Процедура может предположить , что отвергают ( Р , т ) возвращается ложным для каждого предка т из C в дереве поиска.

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

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

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

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

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

Ранние варианты остановочных

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

Примеры

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

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

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

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

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

Для этого класса задач, данные экземпляра Р будет целые числа т и п , а предикат Р . В типичном растворе обратного прослеживания к этой проблеме, можно было бы определить частичный кандидат в виде списка целых чисел с = ( с [1], с [2], ..., C [K]) , для любого к между 0 и п , что должны быть назначены первые K переменных х [1], х [2], ..., х [ к ] . Корневая кандидат затем будет пустой список (). В первых и последующих процедурах , затем будут

function first(P, c)
  k  length(c)
  if k = n
    then return NULL
  else return (c[1], c[2], , c[k], 1)

function next(P, s)
  k  length(s)
  if s[k] = m
    then return NULL
  else return (s[1], s[2], , s[k - 1], 1 + s[k])

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

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

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

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

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

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

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

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

Заметки

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

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

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

  • Жиль Brassard, Пол Bratley (1995). Основы Algorithmics . Prentice-Hall.

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