Гибридный алгоритм (удовлетворение ограничений)

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

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

Алгоритм вывода/поиска циклического разреза

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

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

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

find a cycle cutset of the graph of the problem
run search on the variables of the cutset
  when a consistent partial assignment to all variables are found,
    replace each variable of the cutset with a new variable for each constraint;
    set the domains of these new variables to the value of the old variable in the partial assignment
    solve the problem using inference

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

Другой альтернативой сокращению времени поиска является увеличение нагрузки на часть вывода. В частности, вывод может быть относительно эффективным, даже если граф задачи представляет собой не лес, а граф небольшой индуцированной ширины. Это можно использовать, выполняя поиск по набору переменных, который не является циклическим разрезом, но после устранения проблемы оставляет индуцированную ширину, ограниченную некоторым значением. $b$ . ^{[ нужны разъяснения ]} Такой набор переменных называется $b$ - срез проблемы.

Индуцированная ширина графика после удаления набора переменных называется скорректированной индуцированной шириной . Таким образом, индуцированная ширина, скорректированная относительно $b$ вырезка всегда есть $b$ . Находим минимальный размер $b$ -cutset вообще сложный. Тем не менее, $b$ -множество неминимального размера можно легко найти при фиксированном порядке переменных. В частности, такой разрез оставит оставшийся граф ширины, ограниченной $b$ в соответствии с этим конкретным порядком переменных.

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

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

Гибридный алгоритм декомпозиции дерева

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

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

Когда все ограничения передаются от листьев к корню и обратно к корню, все узлы содержат все ограничения, которые к ним относятся. Таким образом, проблема может быть решена в каждом узле.

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

Ссылки

Дектер, Рина (2003). Обработка ограничений . Морган Кауфманн. ISBN 1-55860-890-7 .