Программирование в ограничениях

 

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

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

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

     Система CLP, способная обрабатывать арифметические ограничения равенства и неравенства, позволяет непосредственно решать задачи составления расписаний, подобные приведенным выше. Программа с ограничениями интерпретируется примерно таким образом. Во время выполнения списка целей сопровождается множество текущих ограничений CurrConstr. Первоначально это множество является пустым. Цели в списке целей выполняются одна за другой в обычном порядке. Стандартные цели Prolog обрабатываются как обычно. При обработке цели с ограничениями Constr множества ограничений Constr и CurrConstr сливаются, в результате чего создается множество NewConstr. Затем процедура решения задач в ограничениях, предназначенная для работы с областью определения данного типа, пытается удовлетворить ограничение MewConstr. При этом возможны два основных результата:

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

     Например, два ограничения, X < 3 и X < 2, упрощаются таким образом, что вместо них вводится одно ограничение — X < 2. Степень упрощения зависит от текущего состояния информации о переменных, а также от возможностей конкретной процедуры решения задач в ограничениях. Остальные цели в списке выполняются с множеством текущих ограничений, обновленным таким образом.

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

2. ПРИМЕНЕНИЕ  МЕТОДА CLP ДЛЯ ОБРАБОТКИ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ — CLP(R)

 

     Рассмотрим  следующий запрос:

     ?- 1 + х = 5.

     В языке Prolog такое согласование оканчивается неудачей, поэтому ответом системы Prolog является "nо". Но если пользователь имел в виду, что X — число, а знаком "+" обозначена операция арифметического сложения, то ответ X = 4 был бы более приемлемым. Использование вместо знака "=" встроенного предиката is не позволяет полностью добиться такой интерпретации, а система CLP(R) позволяет. В соответствии с применяемыми синтаксическими соглашениями (версии SICStus Prolog) этот запрос CLP(R) может быть записан следующим образом:

?- (1 + X = 5 ). % Числовое ограничение

X = 4

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

     Каждое  ограничение задается в следующей  форме: Exprl Operator Expr2. И Exprl, и Ехрг2 представляют собой обычные арифметические выражения. Они могут также, в зависимости от конкретной системы CLP(R), включать вызовы некоторых стандартных функций. В качестве Operator может быть задан один из следующих операторов, в зависимости от типа ограничения:

• =. Проверка на равенство.
• =\=. Проверка на неравенство.
• <, =<, >, >=. Арифметическое сравнение.

     Теперь  рассмотрим некоторые простые примеры  использования этих ограничений  и, в частности, определим, насколько  более гибкими они являются по сравнению с обычными встроенными  средствами языка Prolog.

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

convert( Centigrade, Fahrenheit) :- Centigrade is (Fahrenheit - 32)*5/9.

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

convert( Centigrade, Fahrenheit) :- { Centigrade » [Fahrenheit - 321*5/9 ).

?- convert( 35, F).

F = 95

?- convert( C, 95) .

С - 35

     Такая программа CLP(R) работает, даже если не конкретизирован ни один из двух параметров:

? - convert ( С , F ) .

F = 3 2 . 0 + 1.8*С

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

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

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

• Minimize(Expr)
• Maximize(Expr)

В этих двух предикатах Expr — это линейное выражение в терминах переменных, которые появляются в линейных ограничениях. Указанные предикаты находят  значения переменных, удовлетворяющих  этим ограничениям, и соответственно минимизируют или максимизируют значение выражения, как показано ниже.

? - { X =< 5 } , maximize ( X ) .

X - 5 . 0

?- { X =< 5, 2 =< X}, minimize ( 2*X + 3 ) .

X = 2 . 0

? - { X =< b ) , minimize ( X ) .

no

     В последнем примере значение X не имеет нижней границы, поэтому цель минимизации не достигается.

     Следующие предикаты CLP(R) находят супремум (наименьшую верхнюю грань) или инфимум (наибольшую нижнюю грань) любого выражения: sup( Expr, MaxVal), inf( Expr, MinVal), где Expr — это линейное выражение в терминах переменных с линейными ограничениями, a MaxVal и MinVal — максимальное и минимальное значения, которые принимает это выражение в той области, в которой удовлетворяются ограничения. В отличие от предикатов maximize и minimize, переменные в выражении Ехрr не конкретизируются крайними значениями.

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

Соответствующий пример приведен ниже.

?- ( X=2*Y, Y=l-X ).

Процедура решения CLP(Q) дает следующий ответ: X = 2/3, Y = 1/3.

Процедура решения CLP(R) сообщает приблизительно такой ответ: X

0.666666666,Y - 0.333333333.  

3. ПЛАНИРОВАНИЕ  С ПОМОЩЬЮ МЕТОДА CLP

 

     Задачи  составления расписаний, которые  рассматриваются в этом разделе, состоят из перечисленных ниже элементов.

• Множество задач Ti, ..., Т-.
• Продолжительности Di, .... Dn задач.
• Ограничения предшествования, заданные как отношения, следующим образом:
• prec( Ti, Tj).Такое ограничение указывает, что выполнение задания Ti должно закончиться до того времени, как может начаться выполнение задания Tj.
• Множество процессоров г., которые могут применяться для выполнения заданий.
• Ограничения на ресурсы: какие задания могут выполняться теми или иными процессорами (какие процессоры являются подходящими для выполнения конкретного задания).

     Задача  состоит в том, чтобы составить  расписание, время завершения которого является минимальным. В расписании назначается процессор для каждого задания и задается время начала выполнения каждого задания. Безусловно, расписание должно удовлетворять всем ограничениям предшествования и распределения ресурсов: каждое задание должно быть выполнено подходящим процессором, причем ни один процессор не может выполнять два задания одновременно. В соответствующей формулировке CLP задачи составления расписания применяются следующие переменные: значение времени начала, S1, ..., Sn, и имена процессоров, назначенных для каждого задания, P1, ,,., Рn.

     Простым частным случаем этой задачи составления расписания является отсутствие ограничений на ресурсы. В таком случае предполагается, что ресурсы не ограничены, поэтому в любое время всегда имеется свободный процессор для выполнения любого задания. Таким образом, достаточно добиться удовлетворения ограничений, соответствующих отношениям предшествования между заданиями. Как уже было показано во вступительном разделе данной главы, подобная задача может быть сформулирована очень просто. Предположим, что имеется следующее ограничение предшествования, касающееся заданий а и Ь, — prec ( a, b). Допустим, что продолжительность задания а равна Da, а значения времени начала выполнения заданий а и b равны Sa и Sb. Чтобы было удовлетворено ограничение предшествования, значения Sa и Sb должны соответствовать следующему ограничению: