Главная arrow Поиск arrow Структура задач
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Структура задач Печать

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

В том, что эти подзадачи являются независимыми, можно убедиться, рассматривая "связные компоненты графа ограничений. Каждый компонент соответствует одной подзадаче CSPi. Если присваивание Si является решением CSPi то UiSi является решением UiCSPi. Почему это так важно? Рассмотрим следующее: предположим, что каждая подзадача CSPi имеет с переменных из общего количества п переменных, где c — константа. В таком случае должно быть n/c подзадач, и для решения каждой из них требуется, самое большее, объем работы dc. Поэтому общий объем работы измеряется величиной O(dcn/с), которая линейно зависит от n; без такой декомпозиции общий объем работы измерялся бы величиной O(dn), которая экспоненциально зависит от n. Приведем более конкретный пример: разделение булевой задачи CSP с n=80 на четыре подзадачи с c=2 0 сокращает продолжительность поиска решения в наихудшем случае от такой величины, которая равна сроку существования всей вселенной, до величины меньше одной секунды.

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

  • Выбрать в качестве корня дерева любую переменную и упорядочить переменные от корня до листьев таким образом, чтобы родительский узел каждого узла в дереве предшествовал этому узлу в таком упорядочении. Обозначить эти переменные по порядку как X1, ..., Xn. Теперь каждая переменная, кроме корня, имеет только одну родительскую переменную.

Пример задачи CSP с древовидной структурой: граф ограничений задачи CSP с древовидной структурой (а); линейное упорядочение переменных, совместимых с деревом, корнем которого является переменная А (б)

  • В цикле по j от n до 2 применять проверку совместимости к дугам (Xi, Xj), где Xi — родительский узел узла Xj, удаляя значения из области определения Domain[Xi] по мере необходимости.
  • В цикле по j от 1 до n присваивать Xj любое значение, совместимое со значением, присвоенным Xi где Xi — родительский узел узла Xj.

Следует учитывать два важных соображения. Во-первых, после выполнения этапа 2 задача CSP становится совместимой по дугам с учетом ориентации дуг, поэтому присваивание значений на этапе 3 не требует возврата. Во-вторых, благодаря применению проверок совместимости дуг в обратном порядке на этапе 2 алгоритм гарантирует, что никакие удаленные значения не смогут нарушить совместимость тех дуг, которые уже были обработаны. Весь этот алгоритм выполняется за время O(nd2).

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

Первый подход предусматривает присваивание значений некоторым переменным так, чтобы оставшиеся переменные образовывали дерево. Рассмотрим граф ограничений для карты Австралии, который еще раз показан на рисунке. Если с этой карты можно было бы удалить узел SA, соответствующий Южной Австралии, то граф превратился бы в дерево, как показано на рисунке. К счастью, это можно сделать (в графе, а не на самом континенте), зафиксировав некоторое значение для SA и удалив из областей определения других переменных все значения, несовместимые со значением, выбранным для SA.

Первый способ преобразования графа ограничений в дерево: первоначальный граф ограничений, впервые приведенный на рисунке; граф ограничений после удаления узла SA (б)


Теперь, после удаления узла SA и связанных с ним ограничений, любое решение данной задачи CSP будет совместимым со значением, выбранным для SA. (Такой способ удобен при решении бинарных задач CSP; при наличии ограничений более высокого порядка ситуация усложняется.) Поэтому появляется возможность решить задачу, представленную оставшимся деревом, с помощью приведенного выше алгоритма и таким образом решить всю проблему. Безусловно, в общем случае (в отличие от задачи раскрашивания карты) значение, выбранное для узла SA, может оказаться неподходящим, поэтому придется проверить каждое из возможных значений. Общий алгоритм решения указанным способом описан ниже.

  • Выбрать подмножество S из множества Variables[csp], такое, что граф ограничений после удаления S становится деревом. Подмножество S называется множеством разрыва цикла (cycle cutset).
  • Для каждого возможного присваивания переменным в S, которое удовлетворяет всем ограничениям в S, выполнить следующее:
  1. удалить из областей определения оставшихся переменных любые значения, несовместимые с данным присваиванием для S;
  2. если оставшаяся задача CSP имеет решение, вернуть это решение вместе с рисваиванием для S.

Если множество разрыва цикла имеет размер с, то общее время прогона алгоритма составляет O(dc(n-c)d2). В том случае, если граф по своей форме "очень близок к дереву", то множество с будет небольшим, а экономия времени по сравнению прямым поиском с возвратами окажется огромной. Но в наихудшем случае количество элементов с может достигать (n-2). Задача поиска наименьшего множества азрыва цикла является NP-трудной, но известно несколько эффективных алгоритмов решения этой задачи. В целом данный алгоритмический подход носит название определения условий выбора множества разрыва цикла (cutset conditioning).

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

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

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

Каждая подзадача решается независимо; если какая-либо из них не имеет решения, то известно, что вся задача также не имеет решения. Если удается решить все подзадачи, то может быть предпринята попытка составить глобальное решение следующим образом. Прежде всего, каждая подзадача рассматривается как "мегапеременная", областью определения которой является множество всех решений этой подзадачи. Например, самая левая подзадача на рисунке представляет задачу раскрашивания карты с тремя переменными и поэтому имеет шесть решений; одним из них является {WA=red, SA=blue, NT= green}. Затем решается задача с ограничениями, связывающими подзадачи; для этого используется эффективный алгоритм для деревьев, приведенный выше. Ограничения, связывающие подзадачи, указывают на то, что решения подзадач должны быть согласованными по их общим переменным. Например, если за основу берется решение первой подзадачи {WA=red, SA=blue,NT=green], то единственным совместимым решением для следующей подзадачи становится {SA=blue, NT= green, Q=red].

Древовидная декомпозиция графа ограничений, показанного на рисунке 

Любой конкретный граф ограничений допускает большое количество древовидных декомпозиций; при выборе декомпозиции нужно стремиться к тому, чтобы подзадачи были как можно меньше. Ширина дерева древовидной декомпозиции графа на единицу меньше размера наибольшей подзадачи; ширина дерева самого графа определяется как минимальная ширина дерева среди всех его древовидных декомпозиций. Если граф имеет ширину дерева w и дана соответствующая древовидная декомпозиция, то соответствующая задача может быть решена за время О (ndw+1). Это означает, что задачи CSP с графами ограничений, характеризующимися конечной шириной дерева, могут быть решены за полиномиальное время. К сожалению, задача поиска декомпозиции с минимальной шириной дерева является NP-трудной, но существуют эвристические методы, которые хорошо работают на практике.