Обратный прыжок - Backjumping

В отслеживании источников алгоритмов , backjumping является методом , который уменьшает пространство поиска , таким образом увеличивая эффективность. В то время как обратный переход всегда идет вверх на один уровень в дереве поиска, когда все значения переменной были протестированы, обратный переход может подниматься на большее количество уровней. В этой статье используется фиксированный порядок оценки переменных , но те же соображения применимы и к динамическому порядку оценки. ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$

• 

  Дерево поиска, которое посещается при регулярном возврате

• 

  Обратный переход: серый узел не посещается

Определение

Каждый раз, когда при поиске с возвратом перепробованы все значения переменной, не найдя никакого решения, он пересматривает последнюю из ранее назначенных переменных, изменяя ее значение или продолжая поиск с возвратом, если другие значения не нужно пробовать. Если - текущее частичное присвоение, и все значения были опробованы без поиска решения, то при поиске с возвратом делается вывод, что расширения решения не существует. Затем алгоритм "идет вверх" до , изменяя значение, если возможно, в противном случае снова возвращается. ${\ Displaystyle x_ {1} = a_ {1}, \ ldots, x_ {k} = a_ {k}}$${\ displaystyle x_ {k + 1}}$${\ Displaystyle x_ {1} = a_ {1}, \ ldots, x_ {k} = a_ {k}}$${\ displaystyle x_ {k}}$${\ displaystyle x_ {k}}$

Частичное назначение не всегда необходимо полностью, чтобы доказать, что никакая ценность не приводит к решению. В частности, префикс частичного присвоения может иметь то же свойство, то есть существует такой индекс , который не может быть расширен для формирования решения с любым значением для . Если алгоритм может доказать этот факт, он может напрямую рассмотреть другое значение для вместо того, чтобы пересматривать, как это обычно бывает . ${\ displaystyle x_ {k + 1}}$${\ displaystyle j <k}$${\ displaystyle x_ {1}, \ ldots, x_ {j} = a_ {1}, \ ldots, a_ {j}}$${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {k}}$

Пример, в котором было безуспешно попытаться выполнить текущее присвоение для всех возможных значений . Возврат возвращается к , пытаясь присвоить ему новое значение. ${\ Displaystyle x_ {1} x_ {2} x_ {3} x_ {4}}$${\ displaystyle x_ {5}}$${\ displaystyle x_ {4}}$	Вместо возвратов, алгоритм делает некоторую дальнейшую разработку, доказывая , что оценки , и не являются частью какого - либо решения. ${\ displaystyle x_ {1} x_ {2} x_ {5} = 211}$${\ displaystyle x_ {1} x_ {2} x_ {5} = 212}$${\ displaystyle x_ {1} x_ {2} x_ {5} = 213}$	В результате текущая оценка не является частью какого-либо решения, и алгоритм может напрямую перейти к нему , пробуя новое значение для него. ${\ displaystyle x_ {1} x_ {2}}$${\ displaystyle x_ {2}}$

Эффективность алгоритма обратного прыжка зависит от того, насколько высоко он может совершить обратный прыжок. В идеале алгоритм мог бы перейти к той переменной, которая такова, что текущее присвоение не может быть расширено для формирования решения с любым значением . В этом случае прыжок называется безопасным . ${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {1}, \ ldots, x_ {j}}$${\ displaystyle x_ {k + 1}}$${\ displaystyle j}$

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

Обратный переход в листовых узлах

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

Состояние, при котором все значения данной переменной несовместимы с текущим частичным решением , называется конечным тупиком . Это происходит именно тогда, когда переменная является листом дерева поиска (что соответствует узлам, имеющим только листья в качестве дочерних на рисунках в этой статье). ${\ displaystyle x_ {k + 1}}$${\ Displaystyle x_ {1}, \ ldots, x_ {k} = a_ {1}, \ ldots, a_ {k}}$${\ displaystyle x_ {k + 1}}$

Алгоритм обратного прыжка Гашнига выполняет обратный прыжок только в листовых тупиках. Другими словами, он работает иначе, чем отслеживание с возвратом только тогда, когда все возможные значения были проверены и оказались несовместимыми без необходимости перехода по другой переменной. ${\ displaystyle x_ {k + 1}}$

Безопасный переход можно найти, просто вычислив для каждого значения кратчайший префикс несовместимого с . Другими словами, если это возможное значение , алгоритм проверяет соответствие следующих оценок: ${\ displaystyle a_ {k + 1}}$${\ Displaystyle x_ {1}, \ ldots, x_ {k} = a_ {1}, \ ldots, a_ {k}}$${\ Displaystyle х_ {к + 1} = а_ {к + 1}}$${\ displaystyle a_ {k + 1}}$${\ displaystyle x_ {k + 1}}$

${\ displaystyle x_ {1} = a_ {1}}$	...	${\ displaystyle x_ {k-1} = a_ {k-1}}$	${\ displaystyle x_ {k} = a_ {k}}$	${\ Displaystyle х_ {к + 1} = а_ {к + 1}}$
${\ displaystyle x_ {1} = a_ {1}}$	...	${\ displaystyle x_ {k-1} = a_ {k-1}}$		${\ Displaystyle х_ {к + 1} = а_ {к + 1}}$
...
${\ displaystyle x_ {1} = a_ {1}}$				${\ Displaystyle х_ {к + 1} = а_ {к + 1}}$

Наименьший индекс (самый низкий в списке), для которого оценки несовместимы, был бы безопасным переходом, если бы он был единственным возможным значением для . Поскольку каждая переменная обычно может принимать более одного значения, максимальный индекс, который получается в результате проверки для каждого значения, является безопасным переходом и является точкой, в которой происходит скачок алгоритма Гашнига. ${\ Displaystyle х_ {к + 1} = а_ {к + 1}}$${\ displaystyle x_ {k + 1}}$

На практике алгоритм может проверять приведенные выше оценки одновременно с проверкой согласованности . ${\ Displaystyle х_ {к + 1} = а_ {к + 1}}$

Обратный переход во внутренних узлах

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

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

Обратный переход на внутренних узлах не может выполняться так же, как на листовых узлах. Действительно, если некоторые оценки требуют ветвления, то это потому, что они согласуются с текущим назначением. В результате поиск префикса, несовместимого с этими значениями последней переменной, не выполняется. ${\ displaystyle x_ {k + 1}}$

В таких случаях, что оказалось оценка не быть частью решения с текущей частичной оценкой является рекурсивным поиском. В частности, алгоритм «знает», что с этого момента решения не существует, потому что он возвращается к этому узлу вместо того, чтобы останавливаться после нахождения решения. ${\ Displaystyle х_ {к + 1} = а_ {к + 1}}$${\ displaystyle x_ {1}, \ ldots, x_ {k}}$

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

В этом примере алгоритм возвращается после перебора всех возможных значений из-за трех пересекающихся точек несогласованности. ${\ displaystyle x_ {k + 1}}$	Второй пункт остается несогласованным, даже если значения и удаляются из его частичной оценки (обратите внимание, что значения переменной находятся в ее дочерних элементах) ${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {k}}$	Другие противоречивые оценки по- прежнему так и без , и${\ displaystyle x_ {k-2}}$${\ displaystyle x_ {k-1}}$${\ displaystyle x_ {k}}$	Алгоритм может выполнить обратный переход, поскольку это наименьшие переменные, сохраняющие все несоответствия. Будет испробовано новое значение . ${\ displaystyle x_ {k-2}}$${\ displaystyle x_ {k-2}}$

Другими словами, когда все значения были опробованы, алгоритм может выполнить обратный переход к предыдущей переменной при условии, что текущая оценка истинности несовместима со всеми оценками истинности в конечных узлах, которые являются потомками узла . ${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {1}, \ ldots, x_ {i}}$${\ displaystyle x_ {k + 1}, x_ {k + 2}, ...}$${\ displaystyle x_ {k + 1}}$

Упрощения

При поиске возможного обратного перехода для одного из его предков все узлы в заштрихованной области можно игнорировать.${\ displaystyle x_ {k + 1}}$

Из-за потенциально большого количества узлов, которые находятся в поддереве , информация, необходимая для безопасного обратного перехода, собирается во время посещения его поддерева. Поиск безопасного прыжка можно упростить двумя соображениями. Во-первых, алгоритму нужен безопасный прыжок, но он все равно работает с прыжком, который не является максимально возможным безопасным прыжком. ${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {k + 1}}$

Второе упрощение состоит в том, что узлы в поддереве , которые были пропущены обратным переходом, можно игнорировать при поиске обратного перехода . Точнее, все узлы, пропущенные обратным переходом от узла к узлу , не имеют отношения к поддереву с корнем , а также не имеют отношения к другим их поддеревьям. ${\ displaystyle x_ {l}}$${\ displaystyle x_ {l}}$${\ displaystyle x_ {m}}$${\ displaystyle x_ {l}}$${\ displaystyle x_ {m}}$

В самом деле, если алгоритм перешел от узла к пути через путь, но совершил обратный переход назад, то вместо этого он мог перейти непосредственно от узла к . В самом деле, обратный переход указывает на то, что узлы между и не имеют отношения к поддереву с корнем . Другими словами, обратный переход указывает на то, что посещение области дерева поиска было ошибкой. Следовательно, эту часть дерева поиска можно игнорировать при рассмотрении возможного обратного перехода от одного из его предков или от него. ${\ displaystyle x_ {l}}$${\ displaystyle x_ {m}}$${\ displaystyle x_ {l}}$${\ displaystyle x_ {m}}$${\ displaystyle x_ {l}}$${\ displaystyle x_ {m}}$${\ displaystyle x_ {m}}$${\ displaystyle x_ {l}}$

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

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

Обратный прыжок на основе графика

Обоснование обратного перехода на основе графов состоит в том, что безопасный переход можно найти, проверив, какие из переменных находятся в ограничении с переменными , которые создаются в конечных узлах. Для каждого листового узла и каждой переменной индекса, который создается там, индексы, меньшие или равные которым переменная находится в ограничении, могут использоваться для поиска безопасных переходов. В частности, когда все значения были опробованы, этот набор содержит индексы переменных, оценки которых позволяют доказать, что решение не может быть найдено путем посещения поддерева с корнем . В результате алгоритм может выполнить обратный переход к наивысшему индексу в этом наборе. ${\ displaystyle x_ {1}, \ ldots, x_ {k}}$${\ displaystyle x_ {k + 1}, x_ {k + 2}, ...}$${\ displaystyle x_ {i}}$${\ displaystyle i> k}$${\ displaystyle k}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {k + 1}}$

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

Обратный прыжок на основе конфликта (он же обратный прыжок, направленный на конфликт (cbj))

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

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

Формально ограничение предпочтительнее другого, если самый высокий индекс переменной в, но не в , ниже, чем самый высокий индекс переменной в, но не в . Другими словами, за исключением общих переменных, ограничение, имеющее все нижние индексы, является предпочтительным. ${\ displaystyle C}$${\ displaystyle D}$${\ displaystyle C}$${\ displaystyle D}$${\ displaystyle D}$${\ displaystyle C}$

В листовом узле алгоритм выбирает самый низкий индекс , который несовместим с последней переменной, вычисленной в листе. Среди ограничений, которые нарушаются в этой оценке, он выбирает наиболее предпочтительное и собирает все его индексы меньше чем . Таким образом, когда алгоритм возвращается к переменной , наименьший собранный индекс определяет безопасный переход. ${\ displaystyle i}$${\ displaystyle x_ {1}, \ ldots, x_ {i}}$${\ displaystyle k + 1}$${\ displaystyle x_ {k + 1}}$

На практике этот алгоритм упрощается путем сбора всех индексов в один набор вместо создания набора для каждого значения . В частности, алгоритм собирает в каждом узле все наборы, поступающие от его потомков, которые не были пропущены обратным переходом. При выходе из этого узла этот набор удаляет переменную узла и собирается в пункт назначения для обратного отслеживания или обратного перехода. ${\ displaystyle k}$

Конфликт направленного backjumping был предложен для задач удовлетворения ограничений по Патрик Проссеру в своем основополагающем 1993 бумаге.

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

• Возврат
• Ограниченное обучение

Ссылки

• Дехтер, Рина (2003). Обработка ограничений . Морган Кауфманн. ISBN 1-55860-890-7.
• Проссер, Патрик (1993). «Гибридные алгоритмы для задачи удовлетворения ограничений» (PDF) . Вычислительный интеллект 9 (3). Цитировать журнал требует |journal=( помощь )