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

( Sа + Da =< Sb )

     Кроме того, требуется обеспечить, чтобы  ни одно задание Т; не могло начаться до времени 0, а все задания должны быть выполнены ко времени завершения расписания FinTime следующим образом:

( Si >- 0, Si + Di =< FinTime )

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

tasks( [Taskl/Durationl, Task2/Duration2, ...])

Приведенный ниже предикат задает список всех имен заданий и значений их продолжительности: prec( Taskl, Task2). Этот предикат определяет отношение предшествования между заданиями Taskl и Task.2.

resource( Task, [ Procl, Proc2, . . . ] ) - Данный предикат указывает, что задание Task может быть выполнено любым из процессоров Procl, Proc2, ... .

     Рассмотрим простой случай без ограничений на ресурсы. Один из способов решения задачи планирования. В этой программе подразумевается использование некоторого определения конкретной. Основным предикатом является schedule ( Schedule, FinTime), где Schedule — наилучшее расписание для задачи, которая определена с помощью предикатов tasks и prec, a FinTime — время завершения расписания. Расписание имеет следующее представление:

Schedule = [ Taskl / Start l / Durationl , Task2 / Start2 / Duration2 , . . . ]

     Планирование  с помощью метода CLP С неограниченными  ресурсами 

     Процедура schedule, по сути, выполняет описанные ниже действия:

• Формирует ограничения неравенства между значениями времени начала в расписании, соответствующие отношениям предшествования между заданиями.
• Минимизирует время завершения с учетом сформированных ограничений неравенства.

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

     Предикат precedence_constr( TasksDuraticns, Schedule, FinTime) формирует  ограничения между значениями времени  начала заданий в расписании Schedule и значением времени завершения расписания FinTime.

     Предикат  prec_constr( Task/Start/Duration, RestofSchedule) формирует ограничения между значением времени начала Start задания Task и значениями времени начала заданий в списке RestOfSchedule таким образом, чтобы эти ограничения на значения времени начала соответствовали ограничениям предшествования между заданиями.

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

?- schedule( Schedule, FinTime).

FinTime = 22,

Schedule = [tl/0/5,t2/5/7;t3/12/10,t4/S4/2,tS/S5/9],

(SS =< 13)

(S4 >= 5}

(S4-S5 =< -2)

Для заданий t4 и t5 предусмотрена определенная степень свободы в отношении времени их начала. При всех значениях времени начала S4 и S5 для заданий t4 и t5 в пределах указанных интервалов достигается оптимальное время завершения расписания. Три другие задания ( tl , t2 и t3) находятся на критическом пути, и время их начала не может сдвигаться.

 

4. МОДЕЛИРОВАНИЕ В ОГРАНИЧЕНИЯХ

 

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

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

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

5. ПРИМЕНЕНИЕ  МЕТОДА CLP ДЛЯ ПОДДЕРЖКИ КОНЕКИЗ ОБЛАСТЕЙ ОПРЕДЕЛЕНИЯ - CLP(FD)

 

     Система CLP, предназначенная для работы с  конечными областями определения, реализована на основе некоторых специальных механизмов. Их работа будет показана на типичных примерах с использованием синтаксиса и некоторых предикатов из библиотеки CLP(FD) версии SICStus Prolog. В качестве областей определения переменных будут использоваться множества целых чисел. Для указания области определения переменной применяется предикат in/2, что записывается следующим образом:

х in Set

В данном случае Set может быть одним из следующих.

• ( Integer1 Integer2,…), Множество заданных целых чисел.
• Terml, Term2. Множество целых чисел между Terml и Term2.
• Setl \/ Set2. Объединение множеств Setl и Set2.
• Setl A Set2. Пересечение множеств Setl и Set2.
• \Setl. Дополнение множества Setl.

Арифметические  ограничения имеют следующую  форму: Expl Relation Ехр2,

где Expl и Ехр2 — арифметические выражения, a Relation может представлять собой одно из следующих:

• #=. Равно.
• #\=. Не равно.
• #<. Меньше.
• #>. Больше.
• #=<, Меньше или равно.
• #>=. Больше или равно.

     Предикат  indomain (X) назначает с помощью перебора с возвратами возможные значения переменной X. Далее приведены некоторые полезные предикаты, которые определены на списках переменных:

• Domain( L, Min, Max) . Этот предикат означает, что все переменные в списке L имеют области определения Min, Max,
• all_dif f etent ( L). Этот предикат означает, что все переменные в списке L должны иметь разные значения.
• labeling( Options, L) . Этот предикат вырабатывает возможные конкретные значения переменных в списке L. Параметр Options представляет собой список опций, касающихся того порядка, в каком осуществляется разметка переменных в списке L. Если параметр Options = [ ], то по умолчанию переменные размечаются слева направо; при этом возможные значения берутся из списка один за другим, от меньшего к большему.

     Далее приведена программа CLP(FD) для решения задачи с восемью ферзями. В качестве указания по составлению подобных программ следует отметить, что программа имеет следующую основную структуру: вначале задаются области определения переменных, затем налагаются определенные ограничения и в конечном итоге предикат разметки находит конкретные решения. Это — обычная структура программ CLP(FD).

     Так же с помощью системы CLP(FD)можно решать различные задачи оптимизации, таких как минимизация времени завершения при составлении расписаний. Для решения подобных задач удобно применять следующие встроенные предикаты CLP(FD): minimize( Goal, X) и maximize(Goal, X). Эти предикаты находят такое решение Goal, которое минимизирует (максимизирует) значение X.

 

ЗАКЛЮЧЕНИЕ 

     Современные логическое программирование и программирование в ограничениях представляют декларативный  взгляд на программирование и рассматривают решение задачи как объект, а не как процесс (чем характеризуется императивное программирование).В логическом программировании выполнение программы соответствует конструктивному выводу логической формулы из заданных аксиом. Для программирования в ограничениях характерно систематическое использование инвариантов, математических свойств и законов, которые присутствуют в решаемой задаче.

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

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

     В настоящее время методы программирования в ограничениях активно используются в рамках двух парадигм: объектно-ориентированной и логической. Более органичным сочетанием, в силу декларативности обеих его составляющих, представляется логическое программирование в ограничениях. Однако все известные системы логического программирования в ограничениях изначально ориентированы на строго определенные классы задач. Актуальным является создание систем логического программирования в ограничениях, настраиваемых на предметную область решаемой задачи, и разработка соответствующих методов.