Главная arrow книги arrow Копия Глава 5. Задачи удовлетворения ограничений arrow Структура задач
Структура задач

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

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

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

• В цикле по j от 1 до n присваивать Xj любое значение, совместимое со значением, присвоенным хi, где Xi — родительский узел узлах,

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

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