СТРУКТУРА ЗАДАЧ

В данном разделе рассматриваются способы, позволяющие использовать для быстрого поиска решений структуру самой задачи, представленную в виде графа ограничений. Большинство описанных здесь подходов являются очень общими и применимыми для решения других задач, кроме CSP, например задач вероятностного формирования рассуждений. В конечном итоге единственный способ, с применением которого можно надеяться справиться с задачами реального мира, состоит в том, чтобы разложить их на множество подзадач. Еще раз обратившись к рис. 5.1, б с целью определить структуру задачи, можно обнаружить еще один факт: Тасмания не связана с материком3. Интуитивно ясно, что задачи раскрашивания Тасмании и раскрашивания материка представляют собой независимые подзадачи — любое решение для материка, скомбинированное с любым решением для Тасмании, приводит к получению решения для всей карты. В том, что эти подзадачи являются независимыми, можно убедиться, рассматривая связные компоненты графа ограничений. Каждый компонент соответствует одной подзадаче CSPL. Если присваивание Si является решением CSPi, то (JiSi является решением UiCSPi. Почему это так важно? Рассмотрим следующее: предположим, что каждая подзадача CSPi имеет с переменных из общего количества л переменных, где с — константа. В таком случае должно быть л / с подзадач, и для решения каждой из них требуется, самое большее, объем работы dc. Поэтому общий объем работы измеряется величиной О (d°n/ с), которая линейно зависит от л; без такой декомпозиции общий объем работы измерялся бы величиной О (сГ), которая экспоненциально зависит от л. Приведем более конкретный пример: разделение булевой задачи CSP с л=80 на четыре подзадачи с с=20 сокращает продолжительность поиска решения в наихудшем случае от такой величины, которая равна сроку существования всей вселенной, до величины меньше одной секунды.
Поэтому полностью независимые подзадачи являются привлекательными, но встречаются редко. В большинстве случаев подзадачи любой задачи CSP связаны друг с другом. Простейшим случаем является тот, в котором граф ограничений образует дерево: любые две переменные связаны не больше чем одним путем. На рис. 5.6, а показан один из примеров в схематическом виде4. Ниже будет показано, что любая задана CSP с древовидной структурой может быть решена за время, линейно зависящее от количества переменных. Этот алгоритм имеет перечисленные ниже этапы.
• Выбрать в качестве корня дерева любую переменную и упорядочить переменные от корня до листьев таким образом, чтобы родительский узел каждого узла в дереве предшествовал этому узлу в таком упорядочении (см. рис. 5.6, б). Обозначить эти переменные по порядку как xl9 ...,хп. Теперь каждая переменная, кроме корня, имеет только одну родительскую переменную.
• В цикле по j от л до 2 применять проверку совместимости к дугам (XL, xd), где Xi — родительский узел узла Xj, удаляя значения из области определения Domain [Xi] по мере необходимости.
• В цикле по j от 1 до л присваивать Xj любое значение, совместимое со значением, присвоенным хь где XL — родительский узел узлах,-.
Следует учитывать два важных соображения. Во-первых, после выполнения этапа 2 задача CSP становится совместимой по дугам с учетом ориентации дуг, поэтому присваивание значений на этапе 3 не требует возврата. (См. описание понятия k-совместимости на с. 222.) Во-вторых, благодаря применению проверок совместимости дуг в обратном порядке на этапе 2 алгоритм гарантирует, что никакие удаленные значения не смогут нарушить совместимость тех дуг, которые уже были обработаны. Весь этот алгоритм выполняется за время О (по?).
Теперь, после создания эффективного алгоритма для деревьев, следует рассмотреть вопрос о том, можно ли каким-то образом приводить к древовидным структурам более общие графы ограничений. Существуют два основных способа выполнения этой задачи; один из них основан на удалении узлов, а другой — на слиянии узлов друг с другом.
Первый подход предусматривает присваивание значений некоторым переменным так, чтобы оставшиеся переменные образовывали дерево. Рассмотрим граф ограничений для карты Австралии, который еще раз показан на рис. 5.7, а. Если с этой карты можно было бы удалить узел SA, соответствующий Южной Австралии, то граф превратился бы в дерево, как показано на рис. 5.7, б. К счастью, это можно сделать (в графе, а не на самом континенте), зафиксировав некоторое значение для SA и удалив из областей определения других переменных все значения, несовместимые со значением, выбранным для SA.
Теперь, после удаления узла SA и связанных с ним ограничений, любое решение данной задачи CSP будет совместимым со значением, выбранным для SA. (Такой способ удобен при решении бинарных задач CSP; при наличии ограничений более высокого порядка ситуация усложняется.) Поэтому появляется возможность решить задачу, представленную оставшимся деревом, с помощью приведенного выше алгоритма и таким образом решить всю проблему. Безусловно, в общем случае (в отличие от задачи раскрашивания карты) значение, выбранное для узла SA, может оказаться неподходящим, поэтому придется проверить каждое из возможных значений. Общий алгоритм решения указанным способом описан ниже.
• Выбрать подмножество S из множества Variables [ csp], такое, что граф ограничений после удаления Остановится деревом. Подмножество Sназывается множеством разрыва цикла (cycle cutset).
• Для каждого возможного присваивания переменным в 5, которое удовлетворяет всем ограничениям в 5, выполнить следующее:
• удалить из областей определения оставшихся переменных любые значения, несовместимые с данным присваиванием для S;
• если оставшаяся задача CSP имеет решение, вернуть это решение вместе с присваиванием для S.
Если множество разрыва цикла имеет размер с, то общее время прогона алгоритма составляет О (с?- (л-с) d2). В том случае, если граф по своей форме "очень близок к дереву", то множество с будет небольшим, а экономия времени по сравнению с прямым поиском с возвратами окажется огромной. Но в наихудшем случае количество элементов с может достигать (л-2). Задача поиска наименьшего множества разрыва цикла является NP-трудной, но известно несколько эффективных алгоритмов решения этой задачи. В целом данный алгоритмический подход носит название .определения условий выбора множества разрыва цикла (cutset conditioning); мы снова столкнемся с этим понятием в главе 14, где оно используется при формировании рассуждений о вероятностях.
Второй подход основан на формировании древовидной декомпозиции (tree decomposition) графа ограничений и создании множества связанных подзадач. Каждая подзадача решается независимо, а затем итоговые решения комбинируются. Как и большинство алгоритмов, действующих по принципу "разделяй и властвуй", этот алгоритм работает успешно, если подзадачи не слишком велики. На рис. 5.8 показана древовидная декомпозиция задачи раскрашивания карты на пять подзадач. Любая древовидная декомпозиция должна удовлетворять трем приведенным ниже требованиям.
• Каждая переменная из первоначальной задачи появляется по меньшей мере в одной из подзадач.
• Если две переменные первоначальной задачи связаны ограничением, то должны появиться вместе (наряду с этим ограничением) по меньшей мере в одной из подзадач.
• Если какая-то переменная появляется в двух подзадачах в дереве, то должна появляться в каждой подзадаче вдоль пути, соединяющего эти подзадачи.
Первые два условия гарантируют, что в декомпозиции будут представлены все переменные и ограничения. Третье условие на первый взгляд кажется довольно формальным, но просто отражает то ограничение, что любая конкретная переменная должна иметь одно и то же значение в каждой подзадаче, в которой появляется; соблюдение этого ограничения гарантируют связи, соединяющие подзадачи в дереве. Например, переменная SA появляется во всех четырех связанных подзадачах на рис. 5.8. На основании рис. 5.7 можно убедиться, что эта декомпозиция имеет смысл.
Каждая подзадача решается независимо; если какая-либо из них не имеет решения, то известно, что вся задача также не имеет решения. Если удается решить все подзадачи, то может быть предпринята попытка составить глобальное решение следующим образом. Прежде всего, каждая подзадача рассматривается как "мегапеременная", областью определения которой является множество всех решений этой подзадачи. Например, самая левая подзадача на рис. 5.8 представляет задачу раскрашивания карты с тремя переменными и поэтому имеет шесть решений; одним из них является {WA=red, SA-blие,NT= green}. Затем решается задача с ограничениями, связывающими подзадачи; для этого используется эффективный алгоритм для деревьев, приведенный выше. Ограничения, связывающие подзадачи, указывают на то, что решения подзадач должны быть согласованными по их общим переменным. Например, если за основу берется решение первой подзадачи {WA=red, SA-bl и е, NT= green}, то единственным совместимым решением для следующей подзадачи становится {SA=blue, NT= green, Q=red}.
Любой конкретный граф ограничений допускает большое количество древовидных декомпозиций; при выборе декомпозиции нужно стремиться к тому, чтобы подзадачи были как можно меньше. Ширина дерева древовидной декомпозиции графа на единицу меньше размера наибольшей подзадачи; ширина дерева самого графа определяется как минимальная ширина дерева среди всех его древовидных декомпозиций. Если граф имеет ширину дерева w и дана соответствующая древовидная декомпозиция, то соответствующая задача может быть решена за время 0( nd"+1). Это означает, что с3 задачи CSP с графами ограничений, характеризующимися конечной шириной дерева, могут быть решены за полиномиальное время. К сожалению, задача поиска декомпозиции с минимальной шириной дерева является NP-трудной, но существуют эвристические методы, которые хорошо работают на практике.
• Задачи удовлетворения ограничений (Constraint Satisfaction Problems — CSP) состоят из переменных с налагаемыми на них ограничениями. В виде задач CSP могут быть описаны многие важные задачи реального мира. Структуру любой задачи CSP можно представить в виде ее графа ограничений.
• Для решения задач CSP обычно применяется поиск с возвратами — одна из форм поиска в глубину.
• Независимыми от области определения методами выявления того, какая переменная должна быть выбрана следующей в ходе поиска с возвратами, являются эвристики, основанные на определении минимального количества оставшихся значений, и степешше эвристики. Для упорядочения значений переменной может применяться эвристика с наименее ограничительным значением.
• В алгоритме поиска с возвратами можно намного сократить коэффициент ветвления задачи, распространяя последствия частичных присваиваний, сформированных в ходе работы этого алгоритма. Простейшим методом такого распространения является предварительная проверка. Более мощным методом является обеспечение совместимости дуг, но применение этого метода может оказаться более дорогостоящим.
• Возврат происходит после того, как для переменной нельзя больше найти допустимое присваивание. При использовании обратного перехода, управляемого конфликтами, возврат происходит непосредственно к источнику проблемы, возникшей в процессе поиска.
• Для решения задач с ограничениями весьма успешно используется локальный поиск на основе эвристики с минимальными конфликтами.
• Сложность решения задачи CSP в значительной степени зависит от структуры ее графа ограничений. Задачи с древовидной структурой могут быть решены за линейное время. Метод определения условий формирования множества разрыва цикла позволяет преобразовать задачу CSP общего вида в задачу с древовидной структурой и является очень эффективным, если существует возможность найти небольшое множество разрыва цикла. Методы древовидной декомпозиции предусматривают преобразование задачи CSP в дерево подзадач и являются эффективными, если ширина дерева графа ограничений мала.







Материалы

Яндекс.Метрика