Omezení spokojenosti - Constraint satisfaction - Wikipedia

v umělá inteligence a operační výzkum, omezení spokojenosti je proces hledání řešení sady omezení které ukládají podmínky, které proměnné musí uspokojit.^[1] Řešení je tedy sada hodnot proměnných, která splňuje všechna omezení - tj. Bod v proveditelný region.

Techniky používané k uspokojení omezení závisí na druhu omezení, o kterém se uvažuje. Často se používají omezení na konečnou doménu, do té míry, že problémy s uspokojením omezení jsou obvykle identifikovány s problémy na základě omezení na konečné doméně. Takové problémy jsou obvykle řešeny prostřednictvím Vyhledávání, zejména forma ustoupit nebo místní vyhledávání. Šíření omezení jsou další metody používané při řešení těchto problémů; většina z nich je obecně neúplná, to znamená, že mohou problém vyřešit nebo dokázat, že je neuspokojivý, ale ne vždy. Metody šíření omezení se také používají ve spojení s vyhledáváním, aby se daný problém snáze vyřešil. Jiné uvažované druhy omezení jsou na reálných nebo racionálních číslech; řešení problémů s těmito omezeními se provádí pomocí variabilní eliminace nebo simplexní algoritmus.

Omezení spokojenosti vzniklo v oblasti umělá inteligence v 70. letech (viz např. (Laurière 1978 )). V průběhu 80. a 90. let 20. století došlo k zavedení omezení do a programovací jazyk byly vyvinuty. Jazyky často používané pro programování omezení jsou Prolog a C ++.

Problém spokojenosti s omezením

Jak bylo původně definováno v umělé inteligenci, omezení vyčíslují možné hodnoty, které může mít sada proměnných v daném světě. Možným světem je celkové přiřazení hodnot proměnným představujícím způsob, jakým by svět mohl být (skutečný nebo imaginární).^[2] Konečně je konečná doména konečnou sadou libovolných prvků. Problém spokojenosti s omezeními na takové doméně obsahuje sadu proměnných, jejichž hodnoty lze převzít pouze z domény, a sadu omezení, přičemž každé omezení specifikuje povolené hodnoty pro skupinu proměnných. Řešením tohoto problému je vyhodnocení proměnných, které splňuje všechna omezení. Jinými slovy, řešení je způsob přiřazení hodnoty každé proměnné takovým způsobem, aby tyto hodnoty splňovaly všechna omezení.

Za určitých okolností mohou existovat další požadavky: jeden může mít zájem nejen o řešení (a nejrychlejší nebo výpočetně nejefektivnější způsob, jak ho dosáhnout), ale také o to, jak bylo dosaženo; např. jeden může chtít „nejjednodušší“ řešení („nejjednodušší“ v logickém, nevýpočtovém smyslu, které musí být přesně definováno). To se často stává u logických her, jako je Sudoku.

V praxi jsou omezení často vyjádřena v kompaktní formě, místo výčtu všech hodnot proměnných, které by omezení splňovaly. Jedním z nejpoužívanějších omezení je (zřejmé), které stanoví, že hodnoty ovlivněných proměnných musí být všechny odlišné.

Problémy, které lze vyjádřit jako problémy s uspokojením omezení, jsou osm královen puzzle, Sudoku řešení problému a mnoho dalších logických hádanek, Booleovský problém uspokojivosti, plánování problémy, odhad omezené chyby problémy a různé problémy na grafech, jako je zbarvení grafu problém.

I když to obvykle není zahrnuto ve výše uvedené definici problému uspokojení omezení, aritmetické rovnice a nerovnosti vázaly hodnoty proměnných, které obsahují, a lze je proto považovat za formu omezení. Jejich doménou je množina čísel (ať už celých, racionálních nebo reálných), která je nekonečná: proto i vztahy těchto omezení mohou být nekonečné; například, ${ displaystyle X = Y + 1}$ má nekonečný počet párů uspokojujících hodnot. Aritmetické rovnice a nerovnosti často nejsou brány v úvahu v rámci definice „problému uspokojení omezení“, který je omezen na konečné domény. Často se však používají v programování omezení.

Je možné ukázat, že aritmetické nerovnice nebo rovnice přítomné v některých typech konečných logických hádanek, jako je Futoshiki nebo Kakuro (známé také jako Cross Sums) lze považovat za nearitmetická omezení (viz Spokojenost založená na vzorcích a logické hádanky^[3]).

Řešení

Problémy s uspokojením omezení na konečných doménách se obvykle řeší pomocí formy Vyhledávání. Nejpoužívanějšími technikami jsou varianty ustoupit, šíření omezení, a místní vyhledávání. Tyto techniky se používají při problémech s nelineární omezení.

Variabilní eliminace a simplexní algoritmus se používají k řešení lineární a polynomiální rovnice a nerovnice a problémy obsahující proměnné s nekonečnou doménou. Ty jsou obvykle řešeny jako optimalizace problémy, ve kterých je optimalizovanou funkcí počet porušených omezení.

Složitost

Řešení problému uspokojení omezení na konečné doméně je NP kompletní problém s ohledem na velikost domény. Výzkum ukázal řadu povolný subkasy, některé omezují povolené vazební vztahy, jiné vyžadují rozsah omezení, aby vytvořily strom, případně v přeformulované verzi problému. Výzkum také prokázal vztah problému omezení spokojenosti s problémy v jiných oblastech, jako je teorie konečných modelů.

Omezení programování

Omezení programování je použití omezení jako programovacího jazyka pro kódování a řešení problémů. To se často provádí vložením omezení do a programovací jazyk, který se nazývá hostitelský jazyk. Omezovací programování vzniklo z formalizace rovnosti výrazů v Prolog II, což vede k obecnému rámci pro vkládání omezení do a logické programování Jazyk. Nejběžnější hostitelské jazyky jsou Prolog, C ++, a Jáva, ale byly použity i jiné jazyky.

Logické programování omezení

Logický program omezení je a logický program který obsahuje omezení v tělech vět. Jako příklad klauzule A (X): - X> 0, B (X) je klauzule obsahující omezení X> 0 v těle. V cíli mohou být také omezení. Omezení v cíli a v klauzulích použitých k prokázání cíle se hromadí do sady zvané omezení obchodu. Tato sada obsahuje omezení, která tlumočník považoval za uspokojivá, aby mohl pokračovat v hodnocení. Výsledkem je, že pokud je tato sada zjištěna jako neuspokojivá, tlumočník ustoupí. Termíny, které se používají v logickém programování, se považují za zvláštní formu omezení, která lze zjednodušit pomocí unifikace. Výsledkem je, že úložiště omezení lze považovat za rozšíření konceptu substituce který se používá v běžném logickém programování. Nejběžnějšími druhy omezení používaných v logickém programování omezení jsou omezení nad celými čísly / racionálními / reálnými čísly a omezení nad konečnými doménami.

Souběžné programování logiky omezení jazyky byly také vyvinuty. Výrazně se liší od logického programování nesouběžného omezení v tom, že jsou zaměřeny na programování souběžné procesy které nemusí skončit. Pravidla zpracování omezení lze nahlížet jako na formu souběžného omezení logického programování, ale někdy se také používají v nekonkurenčním logickém programovacím jazyce omezení. Umožňují přepisovat omezení nebo odvodit nová na základě pravdivosti podmínek.

Soupravy nástrojů spokojenosti s omezeními

Soubory nástrojů spokojenosti s omezeními jsou softwarové knihovny pro imperativní programovací jazyky které se používají k zakódování a řešení problému uspokojení omezení.

• Řešitel omezení Cassowary, an otevřený zdroj projekt pro uspokojení omezení (přístupný z jazyků C, Java, Python a dalších jazyků).
• Kometa, komerční programovací jazyk a sada nástrojů
• Gecode, open source přenosná sada nástrojů napsaná v C ++ vyvinutá jako produktivní a vysoce efektivní implementace kompletního teoretického základu.
• Gelisp, open source přenosný obal z Gecode na Lisp. ^[4] http://gelisp.sourceforge.net/
• IBM ILOG Optimalizátor CP: C ++, Krajta, Java, .NET knihovny (proprietární, zdarma pro akademické použití ).^[5] Nástupce společnosti ILOG Solver / Scheduler, která byla od roku 2006 považována za lídra na trhu softwaru pro komerční omezení^[6]
• JaCoP, open source řešitel omezení Java.
• OptaPlanner, další řešič omezení Java s otevřeným zdrojovým kódem.
• Koalog, komerční řešení omezení založené na Javě.
• logilab-omezení, řešič omezení otevřeného zdroje napsaný v čistém Pythonu s algoritmy šíření omezení.
• Oblíbenec, open-source omezovač řešitel napsaný v C ++, s malým jazykem pro účely specifikování modelů / problémů.
• ZDC, open source program vyvinutý v Počítačem podporovaný projekt spokojenosti s omezeními pro modelování a řešení problémů s uspokojením omezení.

Další programovací jazyky omezení

Sada nástrojů omezení je způsob, jak vložit omezení do souboru imperativní programovací jazyk. Používají se však pouze jako externí knihovny pro kódování a řešení problémů. Přístup, ve kterém jsou omezení integrována do imperativního programovacího jazyka, je přijat v Programovací jazyk kaleidoskop.

Byla také začleněna omezení funkční programovací jazyky.

Viz také

• Problém spokojenosti s omezením
• Omezení (matematika)
• Řešení kandidáta
• Booleovský problém uspokojivosti
• Teorie rozhodování
• Teorie modulo uspokojivosti
• Konfigurace založená na znalostech

Reference

• Apt, Krzysztof (2003). Zásady programování omezení. Cambridge University Press. ISBN  978-0-521-82583-2.
• Dechter, Rina (2003). Zpracování omezení. Morgan Kaufmann. ISBN  978-1-55860-890-0.
• Dincbas, M .; Simonis, H .; Van Hentenryck, P. (1990). "Řešení velkých kombinačních problémů v logickém programování". Journal of Logic Programming. 8 (1–2): 75–93. doi:10.1016/0743-1066(90)90052-7.
• Freuder, Eugene; Alan Mackworth, eds. (1994). Odůvodnění založené na omezeních. MIT Stiskněte.
• Frühwirth, Thom; Slim Abdennadher (2003). Základy programování omezení. Springer. ISBN  978-3-540-67623-2.
• Guesguen, Hans; Hertzberg Joachim (1992). Perspektiva uvažování na základě omezení. Springer. ISBN  978-3-540-55510-0.
• Jaffar, Joxan; Michael J. Maher (1994). "Logické programování omezení: průzkum". Journal of Logic Programming. 19/20: 503–581. doi:10.1016/0743-1066(94)90033-7.
• Laurière, Jean-Louis (1978). „Jazyk a program pro konstatování a řešení kombinatorických problémů“. Umělá inteligence. 10 (1): 29–127. doi:10.1016/0004-3702(78)90029-2.
• Lecoutre, Christophe (2009). Omezené sítě: Techniky a algoritmy. ISTE / Wiley. ISBN  978-1-84821-106-3.
• Marriott, Kim; Peter J. Stuckey (1998). Programování s omezeními: Úvod. MIT Stiskněte. ISBN  978-0-262-13341-8.
• Rossi, Francesca; Peter van Beek; Toby Walsh, eds. (2006). Příručka programování omezení. Elsevier. ISBN  978-0-444-52726-4. Archivovány od originál dne 04.10.2012. Citováno 2006-10-13.
• Tsang, Edward (1993). Základy spokojenosti omezení. Akademický tisk. ISBN  978-0-12-701610-8.
• Van Hentenryck, Pascal (1989). Omezení spokojenosti v logickém programování. MIT Stiskněte. ISBN  978-0-262-08181-8.
• Rashidi, Hassan .; Tsang, Edward. (2012). „Nové modely omezení spokojenosti pro optimalizační problémy v kontejnerových terminálech“. Journal of Applied Mathematical Modeling. 37 (6): 3601–3634. doi:10.1016 / j.apm.2012.07.042.

externí odkazy

• Výukový program CSP

Videa

• Přednáška spokojenosti s omezením Dr. Madhu Sharma (3:47)
• Zavedení problémů s uspokojením omezení Edwardem Tsangem (7:34)
• Problémy s omezenou spokojeností od Wheelera Rumla (9:18)
• Přednáška o problémech spokojenosti omezení Indian Institute of Technology Madras (51:59)
• Přednáška o CSP (1:16:39)
• Přednáška o problémech spokojenosti s omezeními od Berkeley AI (1:17:38)
• Absolventský kurz AI 5: Spokojenost s omezením od prof Mausama (1:34:29)