Spokojenost s omezením

Úvod

Jedním z důležitých úkolů umělé inteligence (AI) je problém uspokojení omezení . Teorie UR nabízí pohodlný aparát a jednoduché formální schéma pro reprezentaci a řešení kombinatorických problémů umělé inteligence.

Cílem řešení problému RO je najít hodnoty proměnných, které splňují daná omezení.

Problém existence řešení problému PR je NP-úplný .

S teorií RO úzce souvisí programování s omezením , což je programovací paradigma pro deklarativní popis a efektivní řešení kombinatorických problémů. Mnoho klasických kombinatorických problémů, jako je slavný Fermatův teorém , problém splnitelnosti (SAT) z výrokové logiky, problém zbarvení grafu a problém izomorfismu grafu z teorie grafů, lze formulovat jako problémy VR (SLT). Zastavme se podrobněji u jednoho z dlouhodobých problémů v matematice - problému vybarvování grafu , jehož speciálním případem je známý problém vybarvování mapy . Formulace problému barvení ve formě problému RO přiřazuje proměnné k vrcholům grafu, které mají být obarveny, možné barvy jsou domény (domény) proměnných a omezení nerovnosti mezi sousedními vrcholy jsou omezeními problému.

Samozřejmě zde nelze podrobně popsat všechny aspekty a směry teorie uspokojení restrikcí a programování v omezeních, proto úplnější informace a bibliografii lze nalézt v přeložené monografii Russella S., Norvig P., který pokrývá problematiku SR a v recenzi O.A. Shcherbina .

Přehled hlavních oblastí omezeného programování před rokem 2000 podávají Ushakov a Telerman (2000).

Historie

Nejprve se dotkněme terminologie a historie vzniku metod UR. Montanari navrhl používat modely VR k popisu řady kombinatorických problémů, které vznikají při počítačovém zpracování obrazu, a nazval tyto problémy VR „networks of constraints“ (sítě omezení). To je způsobeno skutečností, že omezovací systém může být reprezentován jako neorientovaný graf s proměnnými vrcholy a hranami odpovídajícími omezením mezi dvěma proměnnými. Podle Dechtera jsou omezující sítě grafová reprezentace používaná k nalezení strategií pro řešení LR problémů. Poměrně rychle byl tento přístup použit k řešení mnohem širší třídy problémů. Odborná literatura používá oba tyto termíny omezující sítě a problémy s uspokojením omezujících podmínek.

Více formálně, problém uspokojení omezení (CR) je n-tice , kde je množina proměnných, je množina domén proměnných hodnot a je množina omezení.

Příklady problémů se splněním omezení

Uveďme několik příkladů ilustrujících formulaci problémů ER v jiných oblastech matematiky.

Problémy s optimalizací a problémy s RO

Řešení optimalizačního problému lze redukovat na řešení posloupnosti problémů OE následovně. Najde se proveditelné řešení, po kterém se přidá omezení odpovídající účelové funkci, které vyjadřuje podmínku, že hodnota účelové funkce by měla být lepší než u tohoto řešení. Postupné úpravy této prahové hodnoty, prováděné tak dlouho, dokud se problém nestane neřešitelným, nám umožňují najít optimální řešení.

Příklad 1. Nejtriviálnějším algebraickým příkladem EC problému je problém řešení soustavy rovnic. Daný systém lineárních rovnic přes konečné pole . Má řešení? Je jasné, že v tomto příkladu je každá jednotlivá rovnice omezením, přičemž proměnné rovnice tvoří rozsah a množina všech n-tic odpovídajících řešením rovnice tvoří omezující vztah.

Příklad 2. Standardní problém výrokové 3-splnitelnosti (3-SAT) je definován zadáním výrokové logické formule sestávající z konjunkce klauzulí, přičemž každá klauzule obsahuje 3 literály (literál je proměnná nebo její negace), a zodpovězením otázky zda existují hodnoty proměnných, které činí vzorec pravdivým. Dovolit být takový vzorec, kde jsou věty . Problém proveditelnosti pro lze vyjádřit jako SR problém , kde je množina všech proměnných ve vzorci a je množina omezení , kde každé omezení je konstruováno následovně: je seznam proměnných zahrnutých v , a skládá se ze všech n-tice, díky kterým je klauzule pravdivá .

Řešením tohoto problému RO je přiřazení hodnot proměnným, díky nimž je vzorec pravdivý. Jakýkoli problém 3-splnitelnosti lze tedy vyjádřit jako SR problém.

Problém RO lze také převést na problém proveditelnosti SAT. Pro daný ZUO sestrojíme problém splnitelnosti SAT následovně. Pojďme si představit proměnné. Proměnné jsou nastaveny na hodnotu true tehdy a pouze tehdy, je-li hodnota přiřazena proměnné. Pro každou proměnnou jsou přidány klauzule (disjunkty) pro všechny dvojice hodnot stejné proměnné, aby bylo zajištěno, že proměnná nemůže mít dvě různé hodnoty současně. Je přidána klauzule, která zajistí, že bude proměnné přiřazena alespoň jedna hodnota.

Příklad 3. Jakýkoli konkrétní úkol ŘO lze vyjádřit v logické formě. S použitím standardní korespondence mezi vztahy a predikáty lze přepsat problém RO jako formuli prvního řádu , kde predikáty na a znamená predikát aplikovaný na n-tici proměnných . Otázkou je, zda je tento vzorec proveditelný. Tato úloha se běžně používá v teorii databází, protože odpovídá vyhodnocení konjunktivního dotazu, jak ukazuje následující příklad.

Příklad 4 Na relační databázi lze nahlížet jako na konečnou množinu tabulek. Tabulka se skládá ze schématu a specifických dat, kde schéma je konečná množina atributů, přičemž každý atribut má odpovídající sadu možných hodnot, nazývanou doména. Konkrétní data jsou konečnou množinou řádků, kde každý řádek představuje mapování, které mapuje každý atribut schématu na hodnotu z jeho domény. Standardní úlohou pro relační databáze je problém vyhodnocení konjunktivního dotazu, který se ptá, zda řešení má konjunktivní dotaz, tzn. dotaz na formulář , kde jsou atomické vzorce. Konjunktivní dotaz nad relační databází odpovídá konkrétnímu příkladu problému LR, kterého je dosaženo jednoduchým nahrazením pojmů: „atributy“ jsou nahrazeny „proměnnými“, „tabulky“ „omezeními“, „schéma“ výrazem „ rozsah", "specifická data" podle "restrikčního vztahu" a "řetězce" na "n-tice". Konjunktivní dotaz je tedy ekvivalentní konkrétnímu příkladu úlohy RO, jejíž proměnné jsou atributy dotazu. Pro každý atomární vzorec v dotazu existuje takové omezení, že rozsah omezení je seznam proměnných vzorce a vztah omezení je sada modelů.

Literatura