Omezení programování - Constraint programming

Programování omezení (CP)^[1] je paradigma pro řešení kombinační problémy, které vycházejí z široké škály technik umělá inteligence, počítačová věda, a operační výzkum. V programování omezení uživatelé deklarativně uvedou omezení o proveditelných řešeních pro soubor rozhodovacích proměnných. Omezení se liší od běžných primitiv z imperativní programování jazyky v tom, že neurčují krok nebo posloupnost kroků, které se mají provést, ale spíše vlastnosti řešení, které se má najít. Kromě omezení musí uživatelé také určit metodu řešení těchto omezení. Toto obvykle vychází ze standardních metod, jako je chronologická ustoupit a šíření omezení, ale může používat přizpůsobený kód jako větvení specifické pro konkrétní problém heuristický.

Omezení programování má svůj kořen a může být vyjádřeno ve formě logické programování omezení, který vloží omezení do a logický program. Tato varianta logického programování je způsobena Jaffarem a Lassezem,^[2] který v roce 1987 rozšířil zvláštní třídu omezení, která byla zavedena v roce Prolog II. První implementace logického programování omezení byly Prolog III, CLP (R), a ČIP.

Namísto logického programování je možné kombinovat omezení Funkcionální programování, přepis termínu, a imperativní jazyky Mezi programovací jazyky s integrovanou podporou omezení patří Oz (funkční programování) a Kaleidoskop (imperativní programování). Omezení jsou většinou implementována v imperativních jazycích prostřednictvím sady nástrojů pro řešení omezení, což jsou samostatné knihovny pro existující imperativní jazyk.

Logické programování omezení

Omezení programování je vložení omezení v hostitelském jazyce. První použité hostitelské jazyky byly logické programování jazyky, tak se pole původně volalo logické programování omezení. Dvě paradigmata sdílejí mnoho důležitých funkcí, jako jsou logické proměnné a ustoupit. Dnes nejvíce Prolog implementace zahrnují jednu nebo více knihoven pro programování logiky omezení.

Rozdíl mezi nimi je do značné míry v jejich stylech a přístupech k modelování světa. Některé problémy jsou přirozenější (a tedy jednodušší) psát jako logické programy, zatímco jiné jsou přirozenější psát jako omezující programy.

Přístup programování omezení je hledat stav světa, ve kterém je současně splněno velké množství omezení. Problém se obvykle uvádí jako stav světa obsahující řadu neznámých proměnných. Omezovací program hledá hodnoty pro všechny proměnné.

Časové programování souběžných omezení (TCC) a nedeterministické programování časových souběžných omezení (MJV) jsou varianty programování omezení, které si poradí s časem.

Problém spokojenosti s omezením

Omezení je vztah mezi více proměnnými, který omezuje hodnoty, které mohou tyto proměnné nabývat současně.

Definice — Problém uspokojení omezení na konečných doménách (nebo CSP) je definován tripletem ${ displaystyle ({ mathcal {X}}, { mathcal {D}}, { mathcal {C}})}$ kde:

${ displaystyle { mathcal {X}} = {x_ {1}, tečky, x_ {n} }}$ je sada proměnných problému;
${ displaystyle { mathcal {D}} = {{ mathcal {D}} _ {1}, dots, { mathcal {D}} _ {n} }}$ je sada domén proměnných, tj. pro všechny ${ displaystyle k v [1; n]}$ my máme ${ displaystyle x_ {k} in { mathcal {D}} _ {k}}$ ;
${ displaystyle { mathcal {C}} = {C_ {1}, tečky, C_ {m} }}$ je soubor omezení. Omezení ${ displaystyle C_ {i} = ({ mathcal {X}} _ {i}, { mathcal {R}} _ {i})}$ je definována množinou ${ displaystyle { mathcal {X}} _ {i} = {x_ {i_ {1}}, tečky, x_ {i_ {k}} }}$ proměnných a relace ${ displaystyle { mathcal {R}} _ {i} podmnožina { mathcal {D}} _ {i_ {1}} times dots times { mathcal {D}} _ {i_ {k}} }$ který definuje sadu hodnot povolených současně pro proměnné ${ displaystyle { mathcal {X}} _ {i}}$ :

Existují tři kategorie omezení:

Extensional Constraints: Constraints are defined by enumerating the set of values that would meet them;
aritmetická omezení: omezení jsou definována aritmetickým výrazem, tj. použitím ${ displaystyle <,>, leq, geq, =, neq, ...}$ ;
logická omezení: omezení jsou definována explicitní sémantikou, tj. Vše různé, Nejvíce,...

Definice — Úkol (nebo model) ${ displaystyle { mathcal {A}}}$ CSP ${ displaystyle P = ({ mathcal {X}}, { mathcal {D}}, { mathcal {C}})}$ je definován párem ${ displaystyle { mathcal {A}} = ({ mathcal {X _ { mathcal {A}}}}, { mathcal {V _ { mathcal {A}}}})}$ kde:

${ displaystyle { mathcal {X _ { mathcal {A}}}} podmnožina { mathcal {X}}}$ je podmnožinou proměnné;
${ displaystyle { mathcal {V _ { mathcal {A}}}} = {v _ {{ mathcal {A}} _ {1}}, dots, v _ {{ mathcal {A}} _ {k }} } in {{ mathcal {D}} _ {{ mathcal {A}} _ {1}}, dots, { mathcal {D}} _ {{ mathcal {A}} _ {k}} }}$ je n-tice hodnot získaných přiřazenými proměnnými.

Přiřazení je přidružení proměnné k hodnotě z její domény. Částečné přiřazení je, když byla přiřazena podmnožina proměnných problému. Úplné přiřazení je, když byly přiřazeny všechny proměnné problému.

Vlastnictví — Dáno ${ displaystyle { mathcal {A}} = ({ mathcal {X _ { mathcal {A}}}}, { mathcal {V _ { mathcal {A}}}})}$ přiřazení (částečné nebo úplné) CSP ${ displaystyle P = ({ mathcal {X}}, { mathcal {D}}, { mathcal {C}})}$ , a ${ displaystyle C_ {i} = ({ mathcal {X}} _ {i}, { mathcal {R}} _ {i})}$ omezení ${ displaystyle P}$ jako ${ displaystyle { mathcal {X}} _ {i} podmnožina { mathcal {X _ { mathcal {A}}}}}$ , přiřazení ${ displaystyle { mathcal {A}}}$ vyhovuje omezení ${ displaystyle C_ {i}}$ právě když všechny hodnoty ${ displaystyle { mathcal {V}} _ {{ mathcal {A}} _ {i}} = {v_ {i} v { mathcal {V}} _ { mathcal {A}} { mbox {tel que}} x_ {i} v { mathcal {X}} _ {i} }}$ proměnných omezení ${ displaystyle C_ {i}}$ patří ${ displaystyle { mathcal {R}} _ {i}}$ .

Definice — Řešením CSP je totální přiřazení, které splnilo všechna omezení problému.

Během hledání řešení CSP si uživatel může přát:

nalezení řešení (splnění všech omezení);
nalezení všech řešení problému;
prokazující neuspokojivost problému.

Problém s optimalizací omezení

Problém optimalizace omezení (COP) je problém uspokojení omezení spojený s objektivní funkcí.

An optimální řešení na minimalizaci (maximalizaci) COP je řešení, které minimalizuje (maximalizuje) hodnotu Objektivní funkce.

Během hledání řešení CSP si uživatel může přát:

nalezení řešení (splnění všech omezení);

nalezení nejlepšího řešení s ohledem na cíl;
prokázání optimality nejlépe nalezeného řešení;
prokazující neuspokojivost problému.

Perturbation vs. refinement models

Jazyky pro programování založené na omezeních sledují jeden ze dvou přístupů:^[3]

Model upřesnění: proměnné v problému jsou zpočátku nepřiřazené a předpokládá se, že každá proměnná může obsahovat jakoukoli hodnotu obsaženou v jejím rozsahu nebo doméně. Jak postupuje výpočet, hodnoty v doméně proměnné se prořezávají, pokud se ukáže, že jsou nekompatibilní s možnými hodnotami jiných proměnných, dokud pro každou proměnnou nenajdete jednu hodnotu.
Poruchový model: proměnným v úloze je přiřazena jedna počáteční hodnota. V různých časech dostává jedna nebo více proměnných poruchy (změny jejich staré hodnoty) a systém šíří změnu a snaží se přiřadit nové hodnoty jiným proměnným, které jsou v souladu s poruchami.

Šíření omezení v problémy s uspokojením omezení je typickým příkladem modelu upřesnění a tabulky jsou typickým příkladem poruchového modelu.

Model upřesnění je obecnější, protože neomezuje proměnné na jedinou hodnotu, může vést k několika řešením stejného problému. Model poruchy je však intuitivnější pro programátory používající smíšené imperativové omezení objektově orientovaných jazyků.^[4]

Domény

Omezení použitá v programování omezení jsou obvykle nad některými konkrétními doménami. Některé populární domény pro programování omezení jsou:

booleovský domény, kde platí pouze omezení true / false (SAT problém )
celé číslo domény, Racionální domén
interval domény, zejména pro problémy s plánováním
lineární domén, kde pouze lineární jsou popsány a analyzovány funkce (i když přístupy k nelineární problémy existují)
konečný domény, kde jsou definována omezení konečné množiny
smíšené domény zahrnující dvě nebo více výše uvedených domén

Konečné domény jsou jednou z nejúspěšnějších domén programování omezení. V některých oblastech (např operační výzkum ) programování omezení je často identifikováno s programováním omezení přes konečné domény.

Šíření omezení

Místní konzistence podmínky jsou vlastnosti problémy s uspokojením omezení související s konzistence podmnožin proměnných nebo omezení. Mohou být použity ke zmenšení prostoru pro vyhledávání a snazšímu řešení problému. Využívají se různé druhy místních podmínek konzistence, včetně konzistence uzlů, konzistence oblouku, a konzistence cesty.

Každou podmínku místní konzistence lze vynutit transformací, která změní problém, aniž by se změnila jeho řešení. Taková transformace se nazývá šíření omezení.^[5] Propagace omezení funguje snížením domén proměnných, posílením omezení nebo vytvořením nových. To vede ke zmenšení prostoru pro vyhledávání, což usnadňuje řešení problému pomocí některých algoritmů. Šíření omezení lze také použít jako kontrolu neuspokojivosti, obecně neúplnou, ale v některých konkrétních případech úplnou.

Řešení omezení

Existují tři hlavní algoritmické techniky pro řešení problémů s uspokojením omezení: zpětné vyhledávání, místní vyhledávání a dynamické programování.^[1]

Zpětné vyhledávání

Zpětné vyhledávání je generál algoritmus za nalezení všech (nebo některých) řešení některých výpočetní problémy, zejména problémy s uspokojením omezení, který postupně sestavuje kandidáty na řešení a opouští kandidáta („backtracks“), jakmile zjistí, že kandidáta nelze dokončit na platné řešení.

Místní vyhledávání

Místní vyhledávání je neúplná metoda pro nalezení řešení a problém. Je založen na iterativním vylepšování přiřazení proměnných, dokud nejsou splněna všechna omezení. Zejména místní vyhledávací algoritmy obvykle mění hodnotu proměnné v přiřazení v každém kroku. Nový úkol je v prostoru úkolu blízký předchozímu, odtud název místní vyhledávání.

Dynamické programování

Dynamické programování je obojí matematická optimalizace metoda a metoda počítačového programování. Odkazuje na zjednodušení komplikovaného problému rozdělením na jednodušší dílčí problémy v a rekurzivní způsob. Zatímco některé problémy s rozhodováním nelze takto rozebrat, rozhodnutí, která pokrývají několik bodů v čase, se často rekurzivně rozpadají. Podobně v počítačové vědě, pokud lze problém optimálně vyřešit rozdělením na dílčí problémy a následným rekurzivním nalezením optimálního řešení dílčích problémů, pak se říká, že optimální spodní konstrukce.

Příklad

Syntaxe pro vyjádření omezení přes konečné domény závisí na hostitelském jazyce. Toto je a Prolog program, který řeší klasický alfametický hádanka ODESLAT + DALŠÍ = PENÍZE v logickém programování omezení:

% Tento kód funguje v prostředí YAP i SWI-Prolog pomocí dodaného prostředíKnihovna řešení omezení CLPFD%. Může to vyžadovat drobné úpravy% v jiných prostředích Prologu nebo s použitím jiných řešení omezení.:- use_module(knihovna(clpfd)).Pošli více(Číslice) :-   Číslice = [S,E,N,D,M,Ó,R,N,Y],   % Vytvořit proměnné   Číslice ins 0..9,                % Přidružení domén k proměnným   S #\= 0,                        Omezení%: S se musí lišit od 0   M #\= 0,   all_different(Číslice),          % všechny prvky musí mít různé hodnoty                1000*S + 100*E + 10*N + D     % Další omezení              + 1000*M + 100*Ó + 10*R + E   #= 10000*M + 1000*Ó + 100*N + 10*E + Y,   označení(Číslice).                  % Zahajte hledání

Tlumočník vytvoří proměnnou pro každé písmeno v skládačce. Operátor ins se používá k určení domén těchto proměnných tak, aby se pohybovaly nad množinou hodnot {0,1,2,3, ..., 9}. Omezení S # = 0 a M # = 0 znamená, že tyto dvě proměnné nemohou nabývat hodnoty nula. Když interpret vyhodnotí tato omezení, sníží domény těchto dvou proměnných odstraněním hodnoty 0 z nich. Potom omezení all_different (číslice) je považován; nesnižuje žádnou doménu, takže je jednoduše uložen. Poslední omezení určuje, že číslice přiřazené písmenům musí být takové, aby platilo „ODESLAT + DALŠÍ = PENÍZE“, když je každé písmeno nahrazeno odpovídající číslicí. Z tohoto omezení odvodí řešitel, že M = 1. Jsou probuzena všechna uložená omezení zahrnující proměnnou M: v tomto případě šíření omezení na all_different omezení odstraní hodnotu 1 z domény všech zbývajících proměnných. Šíření omezení může problém vyřešit snížením všech domén na jednu hodnotu, může dokázat, že problém nemá řešení snížením domény na prázdnou množinu, ale může také skončit bez prokázání uspokojivosti nebo neuspokojivosti. The označení literály se používají ke skutečnému hledání řešení.

Viz také

Reference

^ ^A ^b Rossi, Francesca; Beek, Peter van; Walsh, Toby (18. 8. 2006). Příručka programování omezení. Elsevier. ISBN 9780080463803.
^ Jaffar, Joxan a J-L. Lassez. "Logické programování omezení "Sborník 14. sympozia ACM SIGACT-SIGPLAN o zásadách programovacích jazyků. ACM, 1987.
^ Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (1993). Programování omezení. Springer Science + Business Media. str. 76. ISBN 9783642859830.
^ Lopez, G., Freeman-Benson, B., & Borning, A. (1994, leden). Kaleidoskop: Omezující imperativní programovací jazyk. v Programování omezení (str. 313-329). Springer Berlin Heidelberg.
^ Bessiere, Christian (2006), „Omezení šíření“, Příručka programování omezeníZáklady umělé inteligence, 2, Elsevier, s. 29–83, doi:10.1016 / s1574-6526 (06) 80007-6, ISBN 9780444527264

externí odkazy

Sdružení pro programování omezení
Konferenční seriál CP
Průvodce programováním omezení
Programovací systém Mozart na Archiv. Dnes (archivováno 5. prosince 2012), an Oz -založený svobodný software (X11 -styl)
Výpočtové středisko omezení Cork na Archiv. Dnes (archivováno 7. ledna 2013)
Globální katalog omezení

[:0-1] A ^b Rossi, Francesca; Beek, Peter van; Walsh, Toby (18. 8. 2006). Příručka programování omezení. Elsevier. ISBN 9780080463803.

[2] Jaffar, Joxan a J-L. Lassez. "Logické programování omezení "Sborník 14. sympozia ACM SIGACT-SIGPLAN o zásadách programovacích jazyků. ACM, 1987.

[3] Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (1993). Programování omezení. Springer Science + Business Media. str. 76. ISBN 9783642859830.

[4] Lopez, G., Freeman-Benson, B., & Borning, A. (1994, leden). Kaleidoskop: Omezující imperativní programovací jazyk. v Programování omezení (str. 313-329). Springer Berlin Heidelberg.

[5] Bessiere, Christian (2006), „Omezení šíření“, Příručka programování omezeníZáklady umělé inteligence, 2, Elsevier, s. 29–83, doi:10.1016 / s1574-6526 (06) 80007-6, ISBN 9780444527264

[1]

[2]

[3]

[4]

[5]

Druhy programovacích jazyků
Paradigma	Podle herce Pole Orientovaný na aspekt Na základě třídy Zřetězující Souběžně Datový tok Deklarativní Specifické pro doménu Dynamický Esoterický Událost řízena Rozšiřitelný Funkční Rozkazovací způsob Logika Makro Metaprogramování Objektově založené Objektově orientovaný Potrubí Procesní Prototypové Reflexní Na základě pravidel Skriptování Stohově orientovaný Synchronní Taktilní Šablona
Úroveň	Shromáždění Sestaven Interpretováno Stroj Nízká úroveň Vysoká úroveň Velmi vysoká úroveň
Generace	za prvé Druhý Třetí Čtvrtý Pátý
Příbuzný	Není založeno na angličtině Vizuální