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

СОДЕРЖАНИЕ 
 

ВВЕДЕНИЕ……………………………………………………………………….3

1. УДОВЛЕТВОРЕНИЕ ОГРАНИЧЕНИЙ И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ………………………………………………….…4
1. Удовлетворение ограничений…………………………………………...4
2. Решение задачи удовлетворения ограничений…………………………6
3. Расширение Prolog для использования в качестве языка логического программирования в ограничениях…………………………………...10
2. ПРИМЕНЕНИЕ МЕТОДА CLP ДЛЯ ОБРАБОТКИ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ – CLP(R)…………………………………………………………....12
3. ПЛАНИРОВАНИЕ С ПОМОЩЬЮ МЕТОДА CLP…………..…………15
4. МОДЕЛИРОВАНИЕ В ОРАНИЧЕНИЯХ…………………………………19
5. ПРИМЕНЕНИЕ МЕТОДА CLP ДЛЯ ПОДДЕРЖКИ КОНЕЧНЫХ ОБЛАСТЕЙ ОПРЕДЕЛЕНИЯ – CLP(FD)…………………………………20

ЗАКЛЮЧЕНИЕ…………………………………………………………………24

СПИСОК  ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ………………….……….26 
 

ВВЕДЕНИЕ

     Многие  практически важные задачи представляют собой задачи на удовлетворение ограничениям. Для их решения придумано множество  алгоритмов, начиная с классического  метода Гаусса и кончая сложными методами применяемыми в системах доказательства теорем и в системах символьных вычислений. Возникло даже целое направление в программировании - программирование в ограничениях (constraint programming). Идея его чрезвычайно проста - программист определяет некоторое множество переменных и описывает ограничения, которым они должны удовлетворять, а система находит подходящие значения.

     Впервые ограничения были применены в  графическом пакете Sketchpad в начале 1960-х. В 1970 появился первый язык программирования, который поддерживал эту парадигму -УТОПИСТ (Универсальные Текстовые ОПИСания Терминов) Энна Тыугу. Но систематическое использование ограничений в программировании началось только в 1980-х. С тех пор они успешно применялись во многих областях, таких как компьютерная графика, синтаксический анализ естественных языков, системы управления базами данных, исследование операций, молекулярная биология, электротехника, проектирование интегральных микросхем и т.д. В настоящее время многие крупные компании проявляют интерес к программированию в ограничениях, а ACM признала его одним из стратегических направлений исследований.

     Программирование  в ограничениях тесно связано  с традиционным логическим программированием, в недрах которого оно и сформировалось. Большинство систем программирования в ограничениях представляют собой обычный интерпретатор Пролога со встроенным механизмом для решения определенного класса задач удовлетворения ограничениям. Программирование в таких системах назsвают логическим программированием в ограничениях (Constraint Logic Programming или CLP³), а большинство языков или библиотек называются CLP(X), где X указывает на класс решаемых задач.

1. УДОВЛЕТВОРЕНИЕ ОГРАНИЧЕНИЙ И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

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

     Дано:

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

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

всем  заданным ограничениям.

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

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

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

Рисунок 1 – Ограничение предшествования  между заданиями a,b,c,d

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

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

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

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

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

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

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

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

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

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

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

Та = О 

ТЬ = О

2 ≤ Тс ≤ А

Тй = 5

Tf = 9

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

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

     Условия задач удовлетворения ограничений  часто изображаются в виде графов, называемых сепиями ограничений. Узлы в таком графе соответствуют  переменным, а дуги — ограничениям. Для каждого бинарного ограничения 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) становится совместимой. D результате такого сокращения областей Dx и Су мы не теряем ни одного решения задачи удовлетворения ограничений, поскольку отброшенные значения, безусловно, не должны были войти в состав какого-либо решения. После сокращения области Dx могут стать несовместимыми некоторые другие дуги. Итак, эффект подобного действия может в течение определенного времени распространяться по всей сети, возможно, циклически, до тех пор, пока все дуги не станут совместимыми или некоторая область определения не станет пустой. В последнем случае, безусловно, ограничения не могут быть удовлетворены. А в случае, если все дуги являются совместимыми, могут возникать еще две ситуации.

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

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

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

Рисунок 1 – Сеть ограничений для задачи составления расписания

ТАБЛИЦА 1 – Трассировка выполнения алгоритма обеспечения совместимости дуг

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

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 должны соответствовать следующему ограничению: