Метод отката с перескоком в алгоритмах поиска с возвратом

Введение

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

Определение

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

Отскакивание назад в узлах листьев

Простейшее условие, при котором возможен возврат (backjumping), – это когда все значения переменной были доказаны несовместимыми без дальнейшего ветвления. В задаче об удовлетворении ограничений, частичная оценка считается согласованной тогда и только тогда, когда она удовлетворяет всем ограничениям, включающим назначенные переменные, и несогласованной – в противном случае. Может случиться так, что согласованное частичное решение нельзя расширить до согласованного полного решения, поскольку некоторые из неназначенных переменных не могут быть назначены без нарушения других ограничений. Условие, при котором все значения данной переменной несовместимы с текущим частичным решением, называется тупиком-листом. Это происходит точно тогда, когда переменная является листом дерева поиска (что соответствует узлам, имеющим только листья в качестве потомков на рисунках в этой статье). Алгоритм возврата (backjumping) Джона Гашнига выполняет возврат только в тупиках-листах. Иными словами, он работает иначе, чем возврат (backtracking), только когда каждое возможное значение переменной было протестировано и оказалось несовместимым без необходимости ветвления по другой переменной. Безопасный возврат можно найти, просто оценивая для каждого значения кратчайший префикс, несовместимый с . Другими словами, если является возможным значением для , алгоритм проверяет согласованность следующих оценок:

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

Отскакивание на внутренних узлах

Предыдущий алгоритм выполняет возврат только тогда, когда значения переменной можно показать несовместимыми с текущим частичным решением без дальнейшего ветвления. Иными словами, он позволяет выполнять возврат к предыдущему уровню (backjump) только в листовых узлах дерева поиска. Внутренний узел дерева поиска представляет собой присваивание переменной, которое согласуется с предыдущими. Если ни одно решение не может быть построено на основе этого присваивания, предыдущий алгоритм всегда откатывается: в этом случае возврат к предыдущему уровню не выполняется. Возврат к предыдущему уровню в внутренних узлах невозможен, как и в листовых узлах. Действительно, если некоторые проверки требуют ветвления, это потому, что они согласованы с текущим присваиванием. В результате, поиск префикса, несовместимого с этими значениями последней переменной, не увенчивается успехом. В таких случаях, доказательством того, что проверка не является частью решения с текущей частичной оценкой, является рекурсивный поиск. В частности, алгоритм "знает", что решения от этой точки не существует, поскольку он возвращается в этот узел вместо того, чтобы остановиться после нахождения решения. Этот возврат обусловлен рядом тупиков – точек, в которых алгоритм доказал несовместимость частичного решения. Чтобы выполнить дальнейший возврат к предыдущему уровню, алгоритм должен учитывать, что невозможность найти решения связана с этими тупиками. В частности, безопасные возвраты к предыдущему уровню – это индексы префиксов, которые по-прежнему делают эти тупики несовместимыми частичными решениями. В этом примере алгоритм возвращается к , после того как были опробованы все его возможные значения, из-за трех обнаруженных точек несовместимости. Вторая точка остается несовместимой, даже если значения и удалены из ее частичной оценки (обратите внимание, что значения переменной находятся в ее дочерних узлах). Другие несовместимые проверки остаются таковыми даже без , , и . Алгоритм может вернуться к , поскольку это самая нижняя переменная, которая сохраняет все несовместимости. Будет опробовано новое значение для . Другими словами, когда все значения были опробованы, алгоритм может вернуться к предыдущей переменной при условии, что текущая оценка истинности несовместима со всеми оценками истинности в листовых узлах, являющихся потомками узла .

Упрощения

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

Задние прыжки на основе графика

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

Конфликтный прыжок назад (также известный как конфликтный прыжок назад (cbj))

Еще более усовершенствованный алгоритм обратного перехода, иногда способный достигать больших шагов обратного перехода, основан на проверке не только общего присутствия двух переменных в одном и том же ограничении, но и на том, действительно ли это ограничение привело к возникновению противоречия. В частности, этот алгоритм собирает одно из нарушенных ограничений в каждом листе. На каждом узле наивысший индекс переменной, входящей в одно из ограничений, собранных в листьях, определяет безопасный шаг. Хотя выбор конкретного нарушенного ограничения в каждом листе не влияет на безопасность полученного шага, выбор ограничений с максимально возможными индексами увеличивает высоту этого шага. Поэтому алгоритмы обратного перехода, основанные на анализе конфликтов, упорядочивают ограничения таким образом, чтобы ограничения, содержащие переменные с меньшими индексами, были предпочтительнее ограничений, содержащих переменные с большими индексами. Формально, ограничение предпочтительнее ограничения , если наивысший индекс переменной, входящей в но не входящей в , меньше, чем наивысший индекс переменной, входящей в но не входящей в . Иными словами, исключая общие переменные, предпочтение отдается ограничению, содержащему только переменные с меньшими индексами. В листовом узле алгоритм выбирает наименьший индекс такой, что противоречит последней оцененной в этом листе переменной. Среди нарушенных в ходе этой оценки ограничений выбирается наиболее предпочтительное, и собираются все его индексы, меньшие чем . Таким образом, когда алгоритм возвращается к переменной , собранный наименьший индекс определяет безопасный шаг. На практике этот алгоритм упрощается путем сбора всех индексов в единое множество, вместо создания множества для каждого значения . В частности, алгоритм собирает в каждом узле все множества, полученные от его потомков, которые не были пропущены при обратном переходе. При откате от этого узла это множество удаляется из переменной узла и добавляется в пункт назначения отката или обратного перехода. Алгоритм обратного перехода, направляемый конфликтами, был предложен Патриком Проссером в его основополагающей работе 1993 года для задач удовлетворения ограничений.