Общий алгоритм частичного поиска с возвратом

Поиск с возвратом — это хорошо известный метод решения проблем, который повторяется через все возможные комбинации назначений переменных в поисках действительного решения. Общий алгоритм абстрагируется в краткую функцию высшего порядка: https://en.wikipedia.org/wiki/Backtracking

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

Рассмотрим, например, логическую проблему выполнимости, которую можно решить с помощью алгоритма DPLL. Если вы попытаетесь представить это с помощью общего алгоритма поиска с возвратом, результат будет повторяться не только через все 2 ^ N присвоений переменных (что, к сожалению, необходимо в общем случае), но и через все N! порядок проверки переменных (совершенно ненужный и безнадежно неэффективный).

Существует ли общий алгоритм частичного возврата? Краткая функция высшего порядка, которая принимает параметры функции как для вариантов не знаю, так и для безразлично?


search algorithm backtracking recursive-backtracking
person rwallace    schedule 06.09.2020    source источник
comment
Будет ли DPLL действительно выполнять все перестановки переменных? У меня сложилось впечатление, что он выбирал какую-то одну переменную на каждом шаге, используя эвристику, а затем пробовал обе ветви, чтобы увидеть, выполнима ли формула. Если обе ветви терпят неудачу, то формула в данной точке определенно невыполнима и нет причин пробовать другую переменную.   -  person templatetypedef    schedule 06.09.2020
comment
@templatetypedef Действительно, сам алгоритм DPLL в этом отношении хорош. Но что, если вы уберете часть поиска с возвратом из DPLL в пользу использования общего алгоритма поиска с возвратом (просто задав ему параметры для частей, специфичных для предметной области)? Общий алгоритм поиска с возвратом не будет работать так хорошо; он пройдет через все перестановки переменных. (В некотором смысле он не будет знать, что выбор порядка переменных — это такой выбор, от которого не нужно отступать.)   -  person rwallace    schedule 06.09.2020
comment
Мне не нравится, как псевдокод Википедии имитирует итератор/ленивый список с двумя разными функциями — это усложняет реализацию интересной эвристики ветвления по сравнению с одной функцией, которая возвращает ленивый список дочерних элементов дерева поиска для открытия по порядку (и даже в этом случае выбор стратегии исследования дерева имеет большое значение, сравнивая что-то вроде поиска в глубину с поиском в глубину с поиском в первую очередь с возвратом).   -  person David Eisenstat    schedule 07.09.2020
comment
Я обычно использую эвристику, которая обобщает лучшее, это сначала наиболее ограниченное. В частности, для решения SAT с помощью DPLL сокращение предложений до единичных предложений является огромной победой, потому что это позволяет вам выполнять единичное распространение, поэтому я бы сосредоточил свое эвристическое внимание на самых коротких предложениях. Это должно дать вам разделы единиц раньше.   -  person Davislor    schedule 07.09.2020
comment
Однако существует множество бесплатных высокооптимизированных SAT-решателей. Если это не учебное упражнение, рассмотрите возможность использования одного из них.   -  person Davislor    schedule 07.09.2020

Ответы (1)


arrow_upward
3
arrow_downward

Если я вас правильно понял, вы спрашиваете о нарушении симметрии при поиске по дереву. В конкретном примере, который вы привели, все перестановки списка присвоений переменных эквивалентны.

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

Один из них — поиск проблемного пространства в каноническом порядке. Если ветвь, которая устанавливает переменную 10, пытается использовать только переменные 11, 12 и выше, а не переменные 9, 8 или 7, она не будет искать какие-либо перестановки того же решения. Он будет тестировать только те решения, которые уникальны вплоть до перестановки. (В конкретном случае SAT-решения это может исключить оптимальный порядок поиска, хотя вы можете произвольно изменить порядок переменных.)

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

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

person Davislor    schedule 06.09.2020