Решение задачи удовлетворения ограничений

Условия задач удовлетворения ограничений часто изображаются в виде графов, называемых сепиями ограничений. Узлы в таком графе соответствуют переменным, а дуги — ограничениям. Для каждого бинарного ограничения p(x,Y) между перемен­ными X и Y в этом ориентированном графе имеются две дуги, (X,Y) и (Y,X). Для поиска решения задачи удовлетворения ограничений могут использоваться различ­ные алгоритмы обеспечения совместимости. Эти алгоритмы лучше всего рассматри­вать как действующие в сетях ограничений. Они проверяют совместимость областей определения переменных с ограничениями. Основные принципы функционирования таких алгоритмов будут описаны ниже. Следует отметить, что в данной главе рас­сматриваются методы обеспечения совместимости, применяемые к бинарным огра­ничениям, но в общем ограничения могут связывать между собой любое количество переменных (иметь любую арность).

Рассмотрим переменные X и Y, которые имеют области определения Dx и Dy. Предположим, что между переменными X и Y задано бинарное ограничение p(X,Y). Дуга (X,Y) называется совместимой с определяемым ограничением, или просто со- вместимой, если для каждого значения X в области определения Dx существует не­которое значение для Y в области определения Dy, удовлетворяющее ограничению р (X, Y), Если (X, Y) не является совместимой, то все значения в области Dx, для ко­торых отсутствует соответствующее значение в области Dy, могут быть удалены из Dx. В результате [X Y) становится совместимой.

Напри-мер, рассмотрим переменные X и Y, областями определения которых явля­ются множества всех целых чисел от 0 до 10 включительно, что можно записать сле­дующим образом:

Dx = 0.. 10, Dy = 0..10

Допустим, что задано ограничение p(X,Y) следующим образом: X + 4 < Y В та­ком случае дуга::, ■ перестает быть совместимой. Например, для X = 7 в области Dy нет значения Y, удовлетворяющего условию р{7,у]. Для того чтобы дуга (X,Y) стала совместимой, область определения Dx необходимо сократить до Dx = 0..6. Аналогичным образом, дугу (Y,X) можно сделать совместимой, сократив Dy таким образом: Dy - 4..10. Но в результате такого сокращения областей Dx и Dy мы не теряем ни одного решения этой задачи удовлетворения ограничений, поскольку отбро­шенные значения, безусловно, не должны были войти в состав какого-либо решения.

После сокращения области Dx могут стать несовместимыми некоторые другие ду­ги. Например, для дуги, заданной как (Z,X), могут существовать такие значения Z, для которых после сокращения Dx больше не будет ни одного соответствующего зна­чения в области I:-:. После этого, в свою очередь, можно сделать дугу;z,X) совмес­тимой, уменьшив соответствующим образом область Dz. Итак, эффект подобного дей­ствия может в течение определенного времени распространяться по всей сети, воз­можно, циклически, до тех пор, пока все дуги не станут совместимыми или некоторая область определения не станет пустой. В последнем случае, безусловно, ограничения не могут быть удовлетворены. А в случае, если все дуги являются со­вместимыми, могут возникать еще две ситуации.

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

2. Все области определения непусты, и по меньшей мере одна область определе­ния содержит несколько значений.

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

Глава 14. Логическое программирование в ограничениях

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

В качестве иллюстрации рассмотрим, как может действовать этот алгоритм в приведенном выше примере составления расписания. Предположим, что области оп­ределения всех переменных представляют собой целые числа от 0 до 10. На рис. 14.2 показана сеть ограничений, а в табл. 14.1 приведена трассировка выполнения алго­ритма удовлетворения ограничений. Первоначально, в шаге "Start", все области оп­ределения равны 0..10. В каждом шаге выполнения одна из дуг в сети становится совместимой. В шаге 1 рассматривается дуга (ТЬ.Та), которая сокращает область ТЬ до 2..10. Затем рассматривается дуга (Td,Tb), которая сокращает область Td до 5..10, и т.д. После выполнения шага S все дуги становятся совместимыми и все со­кращенные области являются многозначными. Поскольку мы заинтересованы в по­лучении минимального времени завершения, теперь можно попытаться присвоить значение Tf = 9. После этого снова выполняется алгоритм обеспечения совместимо­сти дуг, в результате чего все области определения сокращаются до однозначной, кроме области определения Гс, которая становится равной 2.. 4.

Таблица 14.1. Трассировка выполнения алгоритма обеспечения совместимости дуг

Шаг

Дуга

 

Start
I	(Tb,Ta)
	(Td,Tb)
	(Tf,Td)
/	(Td,Tf)
	<TbrTd)
	(Ta,Tb)
	<Tc,Ta)
	<Tc,Tf)

Та

0..10

0..1

ТЬ

0..10 2..10

2..3

Тс

0..10

2.. И

2..5

Td

0..10

5..10

5..6

Tf

0..10

Э,.10

ГЫ- 3 £ TV

Те+г й ть

 

Рис. 14.2. Сеть ограничений для задачи составления расписания

304 Часть I!. Применение языка Prolog В области искусственного интеллекта

 

■ Обратите внимание на то, как в методе обеспечения совместимости используются ограничения для сокращения областей определения переменных после получения но­вой информации. Поступление новой информации активизирует соответствующие ограничения, что приводит к сокращению областей определения рассматриваемых переменных. Подобное выполнение алгоритма может рассматриваться как управляе­мое данными. Ограничения являются активными в том смысле, что не ожидают яв­ного вызова программистом, но активизируются автоматически при появлении соот­ветствующей информации. Такой принцип вычисления, управляемого данными, до­полнительно рассматривается в главе 23, в разделе "Программирование, управляемое шаблонами".