Програмирање ограничења

У рачунарству, програмирање ограничења је програмска парадигма у којој су везе између променљивих задате у виду неких ограничења. Разлика између језика ове парадигме и језика императивне парадигме је у томе што се не задају кораци који треба да се изврше, већ особине које треба да задовоље решења проблема. Ово чини програме парадигме ограничења једним обликом декларативне парадигме. Ограничења која се користе могу бити разних врста: она која се користе код испитивања задовољивости исказних формула (нпр. "A или B је тачно"), она која се решавају помоћу симплекс алгоритма и друга. Ограничења су обично уграђена у конкретан програмски језик или су доступна кроз разне софтверске библиотеке.

Програмирање ограничења се може изразити у облику принудног логичког програмирања, које уграђује ограничења у логичко програмирање. За настанак ове варијанте логичког програмирања заслужни су Jaffar и Lassez, који су је 1987. проширили одређеном класом ограничења која је уведена у Prolog II. Прве имплементације принудног логичког програмирања биле су Prolog II, CLP(R), и CHIP.

Уместо логичкоg програмирања, ограничења се могу се мешати са функционалним програмирањем, заменом термовима у логичким изразима и императивним језицима.

Програмски језици са уграђеном подршком за ограничења укључују програмски језик Oz (функционално програмирање) и Kaleidoscope (императивно програмирање). Најчешће се ограничења спроводе у императивним језицима преко алата за решавање проблема ограничења, који су засебне библиотеке у датом програмском језику.

Принудно логичко програмирање

Програмирање ограничења је уградња ограничења на језику домаћина. Први језици домаћина који су коришћени су били језици логичке парадигме, тако да је ова област прв��битно названа принудно логичко програмирање. Ове две парадигме имају многе важне функције, као што су логичке променљиве и бектрекинг. Данас већина имплементација Prolog-а укључује једну или више библиотека за принудно логичко програмирање.

Разлика између њих је у великој мери у њиховим стиловима и приступу моделовању спољашњег света . Неке проблеме је природније (па тиме и једноставније ) описати као логичке програме, док је неке природно описати као програме ограничења.

Приступ програмирању ограничења је потрага за стањем у спољашњем свету у којем велики број ограничења треба да буде задовољено у исто време . Проблем се обично наводи као стање света које садржи велики број непознатих променљивих. Програм ограничења тражи вредности за све променљиве.

Временско конкурентно програмирање ограничења (ТCC) и недетерминистичко временско конкурентно програмирање (NTCC) су варијанте програмирања ограничења које се баве временом.

Perturbation или прецизирање модела

Језици за програмирање ограничења базирају се на једном од два приступа.^[1]

Прецизирање модела: променљивим у проблему у почетку нису додељене вредности, а претпоставља се да свака променљива може да садржи било какву вредност из свог домена. Како рачунање напредује, вредности у домену променљиве су одбачене ако се покаже да су некомпатибилне са могућим вредностима других променљивих, све док се не нађе појединачна вредност за сваку променљиву.
Модел пертурбације: променљивим у проблему се додељује једна почетна вредност. У различитим тренуцима једна или више променљивих примају пертурбације (промене у својим старим вредностима), а систем пропагира промену покушавајући да додели нове вредности и другим променљивим које су у складу са пертурбацијом.

Пропагирање ограничења у проблемима задовољивости исказних формула је типичан пример прецизирања модела, a табеларни приказ је најважнији пример модела пертурбације.

Модел прецизирања је општији, пошто не ограничава пременљиве да имају једну вредност, па то може довести до неколико решења за исти проблем. Међутим, модел пертурбације је више интуитиван за програмере који користе мешавине императивних и објектно - оријентисаних језика са ограничењима.^[2]

Домени

Ограничења која се користе у програмирању ограничења се обично тичу неких посебних области. Неки од популарних домена за програмирање ограничења су :

Буловски домен, где важе само ограничења типа тачно/нетачно (САТ проблем)
Целобројни домен, рационални домен
Линеаран домен, где су само линеарне функције описане и анализиране (иако приступ нелинеарним проблемима постоје)
Коначни домени, где се дефинишу ограничења у коначном скупу и
Мешовити домени, који укључују два или више од горенаведених домена.

Коначни домени су једни од најкориснијих домена програмирања ограничења. У неким областима, као што су операциона истраживања, програмирање ограничења се често поистовећује са програмирањем ограничења преко коначних домена.

Сви горенаведени примери се обично решавају SMT солверима.

Решења коначних домена су корисна за решавање проблема задовољивости исказних формула, а често се заснивају на локалној доследности или некој од њених апроксимација.

Синтакса за изражавање ограничења у коначним доменима зависи од језика домаћина. Следи Prolog програм који решава класичну аритметичку слагалицу са речима (SEND + MORE = MONEY) у контексту програмирања ограничења:

Овај код се може користити и у YAP-у and SWI-Prolog-у користећи CLPFD библиотеку за ограничења.

Може захтевати мање измене како би радио у другим Prolog окружењима.

- use_module(library(clpfd)).

sendmore(Digits) :-

  Digits = [S,E,N,D,M,O,R,Y],     % Креира променљиве
  Digits ins 0..9,                % Додељује домене променљивим
  S #\= 0,                        % Ограничење: S мора бити различито од 0
  M #\= 0,
  all_different(Digits),          % сви елементи морају имати различите вредности
               1000*S + 100*E + 10*N + D     % Друга ограничења
             + 1000*M + 100*O + 10*R + E
  #= 10000*M + 1000*O + 100*N + 10*E + Y,
  label(Digits).                  % Започиње се претрага

</source>

Преводилац ствара променљиву за свако слово у слагалици. Оператор ins се користи за спецификацију домена ових променљивих, тако да се крећу кроз скуп вредности {0,1,2,3, ..., 9}. Ограничења S#\=0 и M#\=0 значе да ове две променљиве не могу имати вредност нула. Када преводилац процењује ова ограничења, смањује домене ове две променљиве уклањањем вредности 0 из домена. Затим, ограничење all_different(Digits) не сужава ниједан домен, тако да се једноставно складишти. Последње ограничење наводи да цифре додељене словима морају бити такве да се "SEND+MORE=MONEY" не мења када се свако слово замењује његовоm одговарајућом цифром. Из овог ограничења, солвер закључује да је М = 1. Сва сачувана ограничења која укључују променљиву М се активирају: у овом случају, пропагирање ограничења на all_different ограничење уклања вредност 1 из домена свих преосталих променљивих. Пропагирање ограничења може решити проблем смањивањем свих домена на само једну вредност, може се показати да проблем нема решење сужавањем домена на празан скуп, али такође се може завршити без доказивања задовољивости или незадовољивости. Label литерали се користе за извођење претраге за решењем.

Библиотеке програма ограничења за императивне програмске језике

Програмирање ограничења се често реализује у императивним језицима путем посебних библиотека. Неке популарне библиотеке су:

Artelys Kalis (C++, Java, Python библиотеке, FICO Xpress модул)
Cassowary (софтвер) (Smalltalk, C++, Java, Python, JavaScript, Ruby библиотека, бесплатан софтвер: LGPL, који се више не одржава)
CHIP V5 програмски језик са C++ и C библиотекама
Choco (Јава библиотека, бесплатан софтвер: X11 стил)
Comet (C програмски стил за програмирање ограничења, локалне претраге базиране на ограничењима и математичко програмирање)
Cream Архивирано на сајту Wayback Machine (22. јул 2011) (Јава библиотека, бесплатан софтвер: LGPL)

Неки језици који подржавају програмирање ограничења

AIMMS - језик алгебарског моделовања са подршком за логичко програмирање.^[3]
Alma-0 - мали, строго типизиран језик програмирања ограничења са ограниченим бројем карактеристика инспирисан логичким програмирањем, подржава императивно програмирање.
AMPL - језик алгебарског моделовања са подршком за логичко програмирање.
Babelsberg
Bertrand - програмски језик за грађење система програма ограничења.
Common Lisp - бесплатна софтверска библиотека која омогућава бектрекинг.
Kaleidoscope - објектно - оријентисан императивни језик са ограничењима.
Oz
Claire
Curry - базиран на Haskell-у, са бесплатним имплементацијама.
Wolfram

Референце

^ Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (2013). Constraint Programming. Springer Science & Business Media. стр. 76. ISBN 9783642859830.
^ Lopez, G., Freeman-Benson, B., & Borning, A. (1994, January). Kaleidoscope: A constraint imperative programming language. In Constraint Programming (pp. 313-329). Springer Berlin Heidelberg.
^ Willem-Jan van Hoeve; Hunting, Marcel & Chris Kuip (2012). „The AIMMS Interface to Constraint Programming” (PDF). Архивирано из оригинала (PDF) 17. 06. 2014. г. Приступљено 15. 04. 2016.

Литература

Rossi, Francesca; Peter Van Beek; Walsh, Toby (2006). Handbook of constraint programming. Elsevier. стр. 157. ISBN 978-0-444-52726-4.
Benhamou, Frédéric; Jussien, Narendra; Barry O'Sullivan (2007). Trends in constraint programming. John Wiley and Sons. стр. 45. ISBN 978-1-905209-97-2.

Спољашње везе

Artelys Kalis
Cream Архивирано на сајту Wayback Machine (22. јул 2011)
Babelsberg

[1] Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (2013). Constraint Programming. Springer Science & Business Media. стр. 76. ISBN 9783642859830.

[2] Lopez, G., Freeman-Benson, B., & Borning, A. (1994, January). Kaleidoscope: A constraint imperative programming language. In Constraint Programming (pp. 313-329). Springer Berlin Heidelberg.

[3] Willem-Jan van Hoeve; Hunting, Marcel & Chris Kuip (2012). „The AIMMS Interface to Constraint Programming” (PDF). Архивирано из оригинала (PDF) 17. 06. 2014. г. Приступљено 15. 04. 2016.

[1]