Лекция №14 Constraint-пролог: операционная семантика Программирование в ограничениях

Программирование в ограничениях (constraint programming) – достаточно новое направление в декларативном программировании. Появилось оно во многом в результате развития систем символьных вычислений, искусственного интеллекта и исследования операций.

Программирвание в ограничениях – это программирование в терминах "постановок задач".

Постановка задачи – это конечный набор переменных V = {v[1], ..., v[n]}, соответствующих им конечных (перечислимых) множеств значений D = {D[1], ...,D[n]}, и набор ограничений С = {C[1],...,C[m]}. Ограничения представлены как утверждения, в которые входят в качетсве "параметров" переменные из некоторого подмножества V[j],j=1..m набора V. Решение такой задачи – набор значений переменных, удовлетворяющий всем ограничениям C[j].

Синтаксически такую постановку задачи пожно записать как "правило" для "типизированного" Пролога:

problem(V1:D1, ..., Vn:Dn) :- С1, ... Cm.

Семантически, однако, программирование в ограничениях отличается от традиционного логического программирования в первую очередь тем, что исполнение программы рассматривается не как доказательство утверждения, а нахождение значений переменных. При этом порядок "удовлетворения" отдельных ограничений не имеет значения, и система программирования в ограничениях, как правило, стремится оптимизировать порядок "доказательства" утверждений с целью минимизации отката в случае неуспеха. С этой целью набор ограничений может быть соответствующим образом преобразован – по правилам, аналогичным правилам Пролога. Любую задачу можно рассматривать как ограничение: "значения переменных должны быть решением этой задачи". Часто о программировании в ограничениях говорят исключительно как о "дополнительной" ветви логического программирования.

В качестве примера, мы можем задать системе программирования в ограничениях следующий запрос:

? (X : integer) X>1, member(X, [1,2,3]).

Типичная Пролог-система на таком запросе выдаст ошибку: Х является неинициализированной переменной, и его нельзя сравнивать с числом 1. Система, поддерживающая программирование в ограничениях, воспримет эти "утверждения" как ограничения (а не как цели, которые требуется доказать), и выдаст нам требуемые решения: Х=2 и Х=3.

Это может быть реализовано, например, следующим образом: при "прологовском" доказательстве утверждения Х>1 будет выведено ограничение на переменную Х (естественно, Х>1). Результаты доказательства следующей подцели (member(...)) будут проверяться на удовлетворение этому ограничению (фактически, будет передоказываться утверждение X>1 для конкретных значений Х). Первый вариант (Х=1) не пройдет эту проверку, остальные будут приняты как удовлетворяющие выведенному ограничению.

Задачу в ограничениях можно рассматривать и как задачу о минимальном необходимом наборе ограничений, что позволяет в некоторых случаях описать в явном виде бесконечные множества решений. Так, минимальным необходимым набором ограничений для задачи X:integer, X>2, X<4 будет Х=3; для задачи X,Y:integer, X*2=Y таким набором будет X:integer, Y mod 2 = 0.

Системы символьных вычислений нередко позволяют использовать "допущения" – по сути, те же ограничения. И на следующий (простой) запрос:

assume X>0.

when X+1<10 ?

выдавать ответ:

X in (0..9).

Как правило, такие системы могут доказывать достаточно нетривиальные матичематические утверждения, выводя "минимальными необходимыми ограничениями", и проверяя эти ограничения на совместность.

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

Кроме этого, программирование в ограничениях естественным образом приложимо к задаче автоматического вывода типов: выведенные ограничения на переменные, соответствующие типам подвыражений, будут задавать "минимальный набор требований на типы". Так, удовлетворение ограничения type_correct("lambda x -> x+1") потребует выполнения набора ограничений {number(x.type_of)}, что, буквально, обозначает, что для того, чтобы прибавить к х единицу, х должно быть числом.

Как и логическое программирование, программирование в ограничениях предполагает совершенно аналогичную "естественную" реализацию на параллельных платформах.

Программирование в ограничениях – это удобный подход к формулировке и решению задач, которые могут быть естественным образом представлены в терминах ограничений, заданных в множестве переменных. Решение подобных задач заключается в поиске таких комбинаций значений переменных, которые соответствуют ограничениям. Этот процесс называется удовлетворением ограничений. Логическое программирование в ограничениях (Constraint Logic Programming – CLP) представляет собой сочетание подхода к решению задач в ограничениях с логическим программированием. При использовании метода CLP средства удовлетворения ограничений встраиваются в логический язык программирования, такой как Prolog.

Удовлетворение ограничений и логическое программирование

Удовлетворение ограничений

Проблема удовлетворения ограничений формулируется, как описано ниже.

Дано:

1) множество переменных;

2) области определения, из которых могут выбираться значения переменных;

3) ограничения, которым должны удовлетворять переменные.

Найти:

такие значения, присваиваемые переменным, которые удовлетворяют всем заданным ограничениям.

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

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

Рассмотрим типичный пример из области планирования. Предположим, что имеются четыре задания, а, b, с и d, продолжительности которых составляют соответственно 2, 3, 5 и 4 часа. Между этими заданиями установлены ограничения предшествования: задание а должно предшествовать заданиям b и с, а задание b должно предшествовать заданию d (рис. 14.1). Задача состоит в том, чтобы найти значения времени начала выполнения соответствующих задач Та, Тb, Тс и Td таким образом, чтобы время завершения Tf выполнения всего расписания было минимальным. Допустим, что самым ранним временем запуска является 0.

Рис. 14.1. Ограничения предшествования между заданиями а, b, с, d

Соответствующую задачу удовлетворения ограничений можно формально определить, как описано ниже.

Переменные: Та, Тb, Тс, Td, Tf.

Области определения: все переменные — неотрицательные действительные числа.

Ограничения:

Та + 2 ≤ Тb. Задача а, на выполнение которой требуется 2 часа, предшествует b;

Та +2 ≤ Тс Задача а предшествует задаче с;

Тb + 3 ≤ Td. Задача b предшествует задаче d;

Тс + 5 ≤ Тf. Задача с завершается к моменту времени Tf;

Td + 4 < Tf. Задача d завершается к моменту времени Tf.

Критерий: минимизация значения Tf.

Эта задача удовлетворения ограничений имеет множество решений, причем все они позволяют обеспечить минимальное время завершения. Это множество решений можно определить следующим образом:

Та = 0

Тb = 0

2 ≤ Тс ≤ 4

Тd = 5

Tf = 9

Определены все значения времени начала, за исключением задания с, выполнение которого может начаться в любое время в интервале от 2 до 4.

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

Условия задач удовлетворения ограничений часто изображаются в виде графов, называемых сетями ограничений. Узлы в таком графе соответствуют переменным, а дуги – ограничениям. Для каждого бинарного ограничения 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. Сеть ограничений для задачи составления расписания

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

Расширение Prolog для использования в качестве языка логического программирования в ограничениях

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

Хотя ограничения, установленные между параметрами предикатов, также задаются в терминах других предикатов, эти вызовы предикатов в конечном итоге сводятся к согласованию. Prolog может быть расширен до "настоящего" языка CLP путем введения других типов ограничений, кроме согласования. Безусловно, должен быть также усовершенствован интерпретатор Prolog таким образом, чтобы он мог обрабатывать указанные ограничения других типов. Система CLP, способная обрабатывать арифметические ограничения равенства и неравенства, позволяет непосредственно решать задачи составления расписаний, подобные приведенным выше.

Программа с ограничениями интерпретируется примерно таким образом. Во время выполнения списка целей сопровождается множество текущих ограничений CurrConstr. Первоначально это множество является пустым. Цели в списке целей выполняются одна за другой в обычном порядке. Стандартные цели Prolog обрабатываются как обычно. При обработке цели с ограничениями Constr множества ограничений Constr и CurrConstr сливаются, в результате чего создается множество NewConstr. Затем процедура решения задач в ограничениях, предназначенная для работы с областью определения данного типа, пытается удовлетворить ограничение NewConstr. При этом возможны два основных результата: а) обнаруживается, что ограничения NewConstr удовлетворить невозможно, что соответствует недостижению цели и вызывает перебор с возвратами; б) не обнаруживается такая ситуации, что ограничения NewConstr удовлетворить невозможно, и эти ограничения максимально упрощаются процедурой решения задач в ограничениях. Например, два ограничения, X ≤ 3 и X ≤ 2, упрощаются таким образом, что вместо них вводится одно ограничение – X ≤ 2. Степень упрощения зависит от текущего состояния информации о переменных, а также от возможностей конкретной процедуры решения задач в ограничениях. Остальные цели в списке выполняются с множеством текущих ограничений, обновленным таким образом.

Системы CLP различаются по типам областей определения и типам ограничений, которые они способны обрабатывать. Семейства методов CLP упоминаются под именами в форме CLP(X), где X обозначает область определения. Например, в методах CLP(R) областями определения переменных являются действительные числа, а в качестве ограничений применяются операции проверки на равенство и неравенство, а также операции сравнения действительных чисел. К системам CLP(Z), используемым в других областях определения, относятся следующие: CLP(Z) – целые числа, CLP(Q) – рациональные числа, CLP(B) – логические области определения и CLP(FD) – задаваемые пользователем конечные области определения. Доступные области определения и типы ограничений в фактических реализациях в значительной степени зависят от существующих методов решения конкретных типов ограничений.

Например, в системах CLP(R) обычно доступны линейные равенства и неравенства, поскольку существуют эффективные методы обработки ограничений этих типов. С другой стороны, нелинейные ограничения имеют очень узкую область применения.

Вывод

• Задачи удовлетворения ограничений формулируются в терминах переменных, областей определения переменных и ограничений между переменными.

• Задачи удовлетворения ограничений часто представляются в виде сетей ограничений.

• Алгоритмы обеспечения совместимости применяются к сетям ограничений и сокращают области определения переменных.

• Логическое программирование в ограничениях (Constraint Logic Programming – CLP) представляет собой сочетание подхода, связанного с удовлетворением ограничений, и логического программирования.

• Системы CLP различаются по типам областей определения и ограничений. Системы логического программирования в ограничениях классифицируются по типам ограничений следующим образом: CLP(R) – действительные числа; CLP(Q) – рациональные числа; CLP(Z) – целые числа; CLP(FD) – конечные области определения; CLP(B) – логические значения.

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

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

• К типичным областям практического применения систем CLP относятся планирование, снабжение и управление ресурсами.