В программировании ограничений и решении SAT бэкджампинг (также известный как нехронологический бэктрекинг [1] или интеллектуальный бэктрекинг [2] ) является усовершенствованием алгоритмов бэктрекинга , которое сокращает пространство поиска . В то время как бэктрекинг всегда идет на один уровень вверх в дереве поиска , когда все значения переменной были проверены, бэкджампинг может идти на большее количество уровней вверх. В этой статье используется фиксированный порядок оценки переменных, но те же соображения применимы к динамическому порядку оценки.
Всякий раз, когда откат перебрал все значения для переменной, не найдя решения, он пересматривает последнюю из ранее назначенных переменных, изменяя ее значение или продолжая откат, если не нужно пробовать другие значения. Если это текущее частичное назначение и все значения для были перебраны, не найдя решения, откат приходит к выводу, что не существует расширяющегося решения. Затем алгоритм «поднимается» до , изменяя значение , если это возможно, и снова откатываясь в противном случае.
Частичное присваивание не всегда необходимо в полном объеме для доказательства того, что никакое значение не приводит к решению. В частности, префикс частичного присваивания может иметь то же свойство, то есть существует индекс, который не может быть расширен для формирования решения с любым значением для . Если алгоритм может доказать этот факт, он может напрямую рассмотреть другое значение для вместо того, чтобы пересматривать, как он обычно делает.
Эффективность алгоритма обратного перехода зависит от того, насколько высоко он может сделать обратный переход. В идеале алгоритм может перейти от к любой переменной , которая такова, что текущее назначение к не может быть расширено для формирования решения с любым значением . Если это так, то это называется безопасным переходом .
Установление того, является ли прыжок безопасным, не всегда осуществимо, поскольку безопасные прыжки определяются в терминах набора решений, которые и пытается найти алгоритм. На практике алгоритмы обратного прыжка используют наименьший индекс, который они могут эффективно доказать как безопасный прыжок. Различные алгоритмы используют различные методы для определения того, является ли прыжок безопасным. Эти методы имеют разные затраты, но более высокая стоимость нахождения более высокого безопасного прыжка может быть компенсирована сокращением объема поиска из-за пропуска частей дерева поиска.
Простейшее условие, при котором возможен обратный переход, — это когда все значения переменной оказались несовместимыми без дальнейшего ветвления. В удовлетворении ограничений частичная оценка является последовательной тогда и только тогда, когда она удовлетворяет всем ограничениям, включающим назначенные переменные, и несовместимой в противном случае. Может быть так, что непротиворечивое частичное решение не может быть расширено до непротиворечивого полного решения, поскольку некоторые из неназначенных переменных не могут быть назначены без нарушения других ограничений.
Состояние, при котором все значения заданной переменной несовместимы с текущим частичным решением, называется тупиком листа . Это происходит именно тогда, когда переменная является листом дерева поиска (что соответствует узлам, имеющим только листья в качестве дочерних элементов на рисунках этой статьи).
Алгоритм обратного перехода Джона Гашнига выполняет обратный переход только в тупиковых концах. [3] Другими словами, он работает иначе, чем возврат, только когда каждое возможное значение было проверено и оказалось несовместимым без необходимости перехода по другой переменной.
Безопасный переход можно найти, просто оценивая для каждого значения кратчайший префикс несовместимого с . Другими словами, если является возможным значением для , алгоритм проверяет согласованность следующих оценок:
Наименьший индекс (самый низкий в списке), для которого оценки несогласованны, был бы безопасным переходом, если бы было единственным возможным значением для . Поскольку каждая переменная обычно может принимать более одного значения, максимальный индекс, который получается в результате проверки для каждого значения, является безопасным переходом и является точкой, в которой алгоритм Джона Гашнига совершает переход.
На практике алгоритм может проверять приведенные выше оценки одновременно с проверкой согласованности .
Предыдущий алгоритм делает обратный прыжок только тогда, когда значения переменной могут быть показаны несовместимыми с текущим частичным решением без дальнейшего ветвления. Другими словами, он допускает обратный прыжок только в конечных узлах в дереве поиска.
Внутренний узел дерева поиска представляет собой назначение переменной, которая согласуется с предыдущими. Если ни одно решение не расширяет это назначение, предыдущий алгоритм всегда возвращается назад: в этом случае обратный переход не выполняется.
Backjumping во внутренних узлах не может быть выполнен как для листовых узлов. Действительно, если некоторые оценки требуют ветвления, то это потому, что они согласуются с текущим назначением. В результате поиск префикса, который не согласуется с этими значениями последней переменной, не увенчается успехом.
В таких случаях то, что доказало, что оценка не является частью решения с текущей частичной оценкой, является рекурсивным поиском. В частности, алгоритм «знает», что с этого момента решения не существует, потому что он возвращается к этому узлу вместо того, чтобы остановиться после нахождения решения.
Этот возврат происходит из-за ряда тупиков , точек, где алгоритм доказал, что частичное решение несовместимо. Для дальнейшего обратного перехода алгоритм должен учитывать, что невозможность нахождения решений обусловлена этими тупиками. В частности, безопасные переходы являются индексами префиксов, которые по-прежнему делают эти тупики несовместимыми частичными решениями.
Другими словами, когда все значения были перепробованы, алгоритм может вернуться к предыдущей переменной при условии, что текущая оценка истинности несовместима со всеми оценками истинности в конечных узлах, которые являются потомками узла .
Из-за потенциально большого количества узлов, которые находятся в поддереве , информация, необходимая для безопасного обратного прыжка, собирается во время посещения его поддерева. Поиск безопасного прыжка можно упростить двумя соображениями. Первое заключается в том, что алгоритму нужен безопасный прыжок, но он все равно работает с прыжком, который не является максимально возможным безопасным прыжком.
Второе упрощение заключается в том, что узлы в поддереве , которые были пропущены обратным переходом, можно игнорировать при поиске обратного перехода для . Точнее, все узлы, пропущенные обратным переходом от узла к узлу, не имеют отношения к поддереву с корнем в , а также не имеют отношения к их другим поддеревьям.
Действительно, если алгоритм спустился от узла к через путь, но сделал обратный прыжок на своем пути назад, то он мог бы пойти напрямую от к вместо этого. Действительно, обратный прыжок указывает, что узлы между и не имеют отношения к поддереву с корнем в . Другими словами, обратный прыжок указывает, что посещение области дерева поиска было ошибкой. Поэтому эту часть дерева поиска можно игнорировать при рассмотрении возможного обратного прыжок от или от одного из его предков.
Этот факт можно использовать, собирая в каждом узле набор ранее назначенных переменных, оценка которых достаточна для доказательства того, что в поддереве с корнем в узле не существует решения. Этот набор создается во время выполнения алгоритма. При отводе от узла этот набор удаляется из переменной узла и собирается в наборе назначения возврата или обратного перехода. Поскольку узлы, пропущенные при обратном переходе, никогда не отводятся, их наборы автоматически игнорируются.
Обоснование обратного перехода на основе графа заключается в том, что безопасный переход может быть найден путем проверки того, какие переменные находятся в ограничении с переменными , которые инстанциируются в конечных узлах. Для каждого конечного узла и каждой переменной индекса , инстанцируемой там, индексы, меньшие или равные чьей переменной находится в ограничении с , могут использоваться для поиска безопасных переходов. В частности, когда все значения для были испробованы, этот набор содержит индексы переменных, оценки которых позволяют доказать, что решение не может быть найдено путем посещения поддерева с корнем в . В результате алгоритм может выполнить обратный переход к самому высокому индексу в этом наборе.
Тот факт, что узлы, пропущенные при обратном переходе, могут игнорироваться при рассмотрении дальнейшего обратного перехода, может быть использован следующим алгоритмом. При отходе от листового узла набор переменных, которые находятся в ограничении с ним, создается и «отправляется обратно» его родителю или предку в случае обратного перехода. В каждом внутреннем узле сохраняется набор переменных. Каждый раз, когда набор переменных принимается от одного из его дочерних элементов или потомков, их переменные добавляются в сохраняемый набор. При дальнейшем откате или обратном переходе от узла переменная узла удаляется из этого набора, и набор отправляется в узел, который является местом назначения обратного перехода или обратного перехода. Этот алгоритм работает, поскольку набор, поддерживаемый в узле, собирает все переменные, которые имеют отношение к доказательству невыполнимости в листьях, которые являются потомками этого узла. Поскольку наборы переменных отправляются только при обратном ходе от узлов, наборы, собранные в узлах, пропущенных при обратном переходе, автоматически игнорируются.
Conflict-based backjumping ( он же conflict-directed backjumping) — более совершенный алгоритм, который иногда позволяет достигать больших backjumps. Он основан не только на проверке общего присутствия двух переменных в одном ограничении, но и на проверке того, действительно ли ограничение вызвало какую-либо несогласованность. В частности, этот алгоритм собирает одно из нарушенных ограничений в каждом листе. В каждом узле максимальный индекс переменной, которая находится в одном из ограничений, собранных в листьях, является безопасным переходом.
В то время как нарушенное ограничение, выбранное в каждом листе, не влияет на безопасность результирующего прыжка, выбор ограничений с максимально возможными индексами увеличивает высоту прыжка. По этой причине основанный на конфликтах обратный прыжок упорядочивает ограничения таким образом, что ограничения по переменным с более низкими индексами предпочтительнее ограничений по переменным с более высокими индексами.
Формально ограничение предпочтительнее другого, если наивысший индекс переменной в , но не в , ниже наивысшего индекса переменной в , но не в . Другими словами, исключая общие переменные, ограничение, имеющее все более низкие индексы, является предпочтительным.
В листовом узле алгоритм выбирает наименьший индекс , который несовместим с последней переменной, оцененной в листе. Среди ограничений, которые нарушаются в этой оценке, он выбирает наиболее предпочтительное и собирает все его индексы, меньшие . Таким образом, когда алгоритм возвращается к переменной , наименьший собранный индекс идентифицирует безопасный переход.
На практике этот алгоритм упрощается путем сбора всех индексов в один набор вместо создания набора для каждого значения . В частности, алгоритм собирает в каждом узле все наборы, поступающие от его потомков, которые не были пропущены при обратном переходе. При отходе от этого узла этот набор удаляется из переменной узла и собирается в пункте назначения обратного отслеживания или обратного перехода.
Направленный на конфликт обратный прыжок был предложен для проблем удовлетворения ограничений Патриком Проссером в его основополагающей статье 1993 года [4].
