Problém spokojenosti s omezením
Tyto problémy omezujícími podmínkami nebo CSP ( Problem spokojenosti s omezujícími podmínkami ), jsou problémy matematika , kde je cílem států nebo předmětů, které splňují celou řadu omezení nebo kritérií. CSP jsou předmětem intenzivního výzkumu v oblasti umělé inteligence i operačního výzkumu . Mnoho CSP vyžaduje, aby kombinace heuristiky a kombinatorických optimalizačních metod byla vyřešena v rozumném čase. Jsou zejména jádrem omezovacího programování , oblasti poskytující jazyky pro modelování problémů a počítačové nástroje k jejich řešení.
Formální definice
Formálně problém splňování je definována triplet , kde je množina proměnných, je soubor domén hodnot tak, že jedna z jejích prvků je doménou proměnné z , a je sada omezení. Každé omezení je zase pár , kde je N-n-tice proměnných a je množinou N-n-tice hodnot; všechny tyto n-tice mají stejný počet prvků; tedy definuje vztah . Vyhodnocení proměnných je funkcí proměnných k polím . Takové hodnocení splňuje omezení, pokud . Řešením je posouzení, které splňuje všechna omezení.
Teoretické aspekty CSP
CSP jsou také studovány v teorii složitosti algoritmů a teorii konečných modelů . Důležitou otázkou je, zda pro každou sadu vztahů je sada všech CSP, které lze reprezentovat pouze vztahy vybranými z této sady, buď třídy P nebo NP-úplné (za předpokladu P ≠ NP). Pokud je taková dichotomie pravdivá, pak CSP poskytují jednu z největších známých sad NP , vyhýbajíc se problémům, které nejsou ani polynomiální, ani NP-úplné řešitelné , jejichž existenci prokázala Ladnerova věta . Dichotomie je známá u CSP, kde hodnotová doména má velikost 2 nebo 3. Dva příspěvky, publikované současně v roce 2017, jeden od Dmitrije Zhuka a druhý od Andreje Bulatova, představují řešení obecného problému.
Většina CSP, o nichž je známo, že se k nim snadno přistupuje, jsou ty, kde hypergraf omezení má omezenou šířku stromu (a kde neexistuje žádné omezení na množinu vztahů představujících omezení), jinak mají omezení libovolnou formu, ale v zásadě existují unární polymorfismy této sady vazebních vztahů.
Aplikace
Některé problémy, které lze modelovat pomocí CSP, zahrnují: problém s osmi dámami, problém se čtyřmi barevnými teorémy , hra sudoku , logická uspokojivost a problém s batohem .
Algoritmy
Algoritmy používané k řešení problémů s uspokojením omezení zahrnují algoritmus šíření omezení , zpětné sledování (a jeho nechronologický vývoj ), učení omezení (en) a algoritmus minimálních konfliktů (en) .
Podívejte se také
- Deklarativní programování
- Omezení programování
- Problém spokojenosti s distribuovaným omezením (DisCSP)
- Unikátní hry hádejte
Bibliografie
- Blaise Madeline, Evoluční algoritmy a řešení problémů uspokojení omezení v konečných doménách (práce, 2002)
- Christine Solnon, Constraint Programming (kurz, 2003)
- Pierre Lopez, Koncept omezení: propagace, spokojenost, programování (prezentace, 2001)
- (en) Edward Tsang (en) , Foundations of Constraint Satisfaction , Londýn / San Diego, Academic Press ,1993( ISBN 978-0-12-701610-8 , online prezentace )
- (en) Rina Dechter , Constraint processing , San Francisco, Morgan Kaufmann (en) ,2003( ISBN 978-1-55860-890-0 , online prezentace , číst online )
- (en) Krzysztof Apt , Principy programování omezení , CUP ,2003, 407 s. ( ISBN 978-0-521-82583-2 , číst online )
- (en) Tomás Feder, spokojenost s omezením: osobní perspektiva (předtisk)
- (in) Archiv omezení
- (en) CSPLib: knihovna problémů pro omezení
- (en) Vynucené uspokojivé referenční hodnoty CSP modelu RB
- (en) Benchmarky - XML reprezentace instancí CSP
Poznámky a odkazy
- Dmitrij Zhuk , „ Důkaz CSP Dichotomy Conjecture “, 58. výroční symposium o základech informatiky (FOCS) , IEEE,2017, str. 319–330 ( DOI 10.1109 / FOCS.2017.38 )
- Andrei A. Bulatov , „ The Dichotomy Theorem for Nonuniform CSPs “, 58. výroční symposium o základech informatiky (FOCS) , IEEE,2017, str. 319–330 ( DOI 10.1109 / FOCS.2017.37 ).