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

Условия задач удовлетворения ограничений часто изображаются в виде графов, называемых сетями ограничений. Узлы в таком графе соответствуют переменным, а дуги – ограничениям. Для каждого бинарного ограничения 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,Y) перестает быть совместимой. Например, для X = 7 в области Dy нет значения Y, удовлетворяющего условию p(7,Y). Для того чтобы дуга (X,Y) стала совместимой, область определения Dx необходимо сократить до Dx = 0..6. Аналогичным образом, дугу (Y,X) можно сделать совместимой, сократив Dy таким образом: Dy = 4..10. Но в результате такого сокращения областей Dx и Dу мы не теряем ни одного решения этой задачи удовлетворения ограничений, поскольку отброшенные значения, безусловно, не должны были войти в состав какого-либо решения.

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

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

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

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

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

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

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

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