Обратный прыжок - 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$ такой, что ${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 x_ {k + 1} = a_ {k + 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 x_ {k + 1} = a_ {k + 1}}$
${displaystyle x_ {1} = a_ {1}}$	...	${displaystyle x_ {k-1} = a_ {k-1}}$		${displaystyle x_ {k + 1} = a_ {k + 1}}$
...
${displaystyle x_ {1} = a_ {1}}$				${displaystyle x_ {k + 1} = a_ {k + 1}}$

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

На практике алгоритм может проверять приведенные выше оценки одновременно с проверкой согласованности ${displaystyle x_ {k + 1} = a_ {k + 1}}$ .

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

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

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

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

В таких случаях доказывается оценка ${displaystyle x_ {k + 1} = a_ {k + 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}$ . В частности, алгоритм собирает в каждом узле все наборы, поступающие от его потомков, которые не были пропущены обратным переходом. При выходе из этого узла этот набор удаляет переменную узла и собирает в место назначения обратного отслеживания или обратного перехода.

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