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

 

 

СОДЕРЖАНИЕ 
 

ВВЕДЕНИЕ……………………………………………………………………….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 – Трассировка выполнения алгоритма обеспечения совместимости дуг