{{Predmet|Programování s omezujícími podmínkami|Roman Barták|OPT042}}
== Základní informace ==
Přednáška podává přehled o technikách programování s omezujícími podmínkami. Zaměřena je na algoritmy splňování podmínek a na problematiku řešení příliš omezených systémů podmínek. Zabývá se také praktickým využitím omezujících podmínek při řešení reálných problémů.
[[Wikipedia:Constraint satisfaction problem]]
== Podrobnosti ==
* CSP – problém popsaný pomocí (hyper)grafu; vrcholy = proměnné, hrany = podmínky
* binární CSP – všechny podmínky jsou binární
** unární se dají kódovat v doménách proměnných
** víc-ární se dají řešit prohozením podmínek a proměnných nebo přidáním skrytých proměnných
=== splňování podmínek prohledáváním ===
;systematické
* generuj a testuj – úplně tupé
* [[wen:backtracking|backtracking]]
** [[wen:backjumping|backjumping]] – skáče více dozadu na proměnné, které způsobily konflikt
** dynamický backtracking – jako backjumping, ale přenáší důvod konfliktu a mění pořadí proměnných
** [[wen:backmarking|backmarking]] – testuje konzistenci a u podmínek, které se změnily, si pamatuje nejvzdálenější úroveň konfliktu, čímž odstraňuje zbytečné testy
;nesystematické
*neúplná stromová prohledávání, nějak se omezují (cutoff) a když to nevyjde, omezí se méně (restart)
** bounded backtrack search (BBS) – omezen počet slepých uliček, když to nevyjde zkusí o jednu více
** iterative broadening (IB) – omezený počet alternativ k vyzkoušení v každém uzlu
** depth bounded search (DBS) – do dané hloubky projíždí všechno, pod tím už jen něco neúplného; v případě neúspěchu jde s úplností hlouběji
** credit search (CS) – daný kredit na větvení, když dojdou ve větvi peníze jde vždy jen jednou cestou
* s heuristikami; diskrepance = porušení heuristiky
** limited discrepancy search (LDS) – daný maximální počet diskrepancí v každé cestě
** improved limited discrepancy search (ILDS) – daný přesný počet diskrepancí, takže se při restartu nemusí procházet už prolezlé
** depth-bounded discrepancy search (DDS) – diskrepance povoleny jen do dané hloubky (v níž je diskrepance povinná – tak se nebudou opakovat slepé uličky z přechozí iterace – ta tam šla podle heuristiky)
;lokální
* hill climbing (HC) – začne na náhodném místě a v každém kroku udělá nejlepší možnou změnu jedné proměnné, když už to nejde zase skočí na náhodné místo, aby se vyhnul lokálnímu optimu
* minimalizace konfliktů (MC) – v každém kroku vezme konfliktní proměnou a minimalizuje u ní počet konfliktů; neumí vyskočit z lokálního optima
* náhodná procházka – v každém kroku hodím kostkou a buď jdu podle nějakého normálního lokálního algoritmu, nebo náhodně
** tabu seznam – brání trčení v lokálních optimech a cyklům (do určité délky) obecně
* GSAT – řeší SAT náhodným ohodnocením a postupným překlápěním těch proměnných, kde mu to nejvíc pomůže (heuristiky: random walk, zvyšování váhy těch co jsou dlouho nesplněné, průměrování dosavadních řešení)
* GENET – neuronová síť, neurony se navzájem potlačují tam kde by spolu neměly být aktivní; dobře je to vysvětleno v asi původním článku, viz. [http://sherry.ifi.unizh.ch/tsang92generic.html A Generic Neural Network Approach For Constraint Satisfaction Problems]
* simulované žíhání – na začátku jsme teplí a hodnoty náhodně skáčou, s klesající teplotou pak i jednotlivých hopsajícím proměnným klesá ochota přejít do horšího ohodnocení a celé se to stabilizuje
=== konzistenční techniky ===
vymlacování hodnot proměnných, které nemůžou být v řešení, obecný popis záležitostí viz [[wen:Local consistency]]
* vrcholová konzistence (node consistency, NC) – aplikace unárních podmínek přímo na domény
* hranová konzistence (arc consistency, AC) – každá hodnota z jednoho konce hrany má kamarády na druhém konci tak, aby spolu splňovali podmínky na hraně
*: revize hrany: vyházení hodnot, které na druhé straně nemají podporu
** AC-1: revidujeme hrany, dokud to redukuje nějaké domény
** [[wen:AC-3 algorithm|AC-3]]: máme frontu k revidování, při revizi hrany do ní zase přihodíme ty, které to mohlo rozbít
** AC-4: udržuje si mapy jaké hodnoty mají kde podporu, při vyřazení hodnoty sníží čítač u těch, které podporovala, a pak případně kaskáduje; optimální v nejhorším případě, paměťově hodně náročné
** AC-6: zlepšuje AC-4, pamatuje si jen jednu podporu, když zmizí tak dopočítává
** [http://www.constraint-programming.com/people/regin/papers/aij05-ac2001.pdf AC-2001]: pro každou hodnotu proměnné si pamatuje poslední hodnotu z druhého konce, která ji podporovala; když tam je, je vše ok, když tam není zkouší další v pořadí
* směrová hranová konzistence (DAC) – (při daném uspořádání) nám stačí hranová konzistence u hran v jednom směru
** DAC-1: požadujeme konzistenci hran je v jednom směru, když to uděláme v dobrém pořadí nemusíme revize opakovat
*: aplikujeme-li DAC na stromové CSP v uspořádání od kořene a potom zase zpět, získáme plnou AC
* path consistency (PC) – cesta je konzistentní, když pro každé ohodnocení obou konců splňující binární podmínky na koncích existuje ohodnocení vnitřku tak, že všechny binární podmínky mezi sousedy na cestě jsou splněny
** CSP je PC, právě když každá cesta délky 2 je PC (indukcí od délky 2 dostaneme PC pro všechny cesty)
** reprezentace binární podmínky {0,1}-maticí, pak jejich skládání násobením: zkonzistentnění cesty (i,k,j): R<sub>ij</sub> = R<sub>ij</sub> & (R<sub>ik</sub> * R<sub>kk</sub> * R<sub>kj</sub>), kde R<sub>kk</sub> jsou unární podmínky na k, a ty různé binární podmínky mezi dvěma proměnnými
** PC-1: zkonzistentňuji cesty délky 2, dokud se mění domény
** PC-2: podmínky na cestu stačí jen jednou (jsou symetrické), po revizi se kontrolují jen zasažené cesty (lze revidovat i podmínku (i,i) – to pak zasahuje cesty které mají ten uzel uvnitř)
** PC-4: založen na počítání podpor, opravuje chybný PC-3
** PC-5: pamatuje si jen jednu podporu, při ztrátě hledá další
* directional path consistency (DPC) – stačí konzinstence cest po směru uspořádání
** DPC-1: jdeme od konce, každou cestu procházíme jen jednou
* restricted path consistency (RPC) – testuje PC jen když to může něco vyřadit
** vrchol je RPC když jsou všechny hrany okolo něj AC a zároveň když má nějaká jeho hodnota jen jednu podporu, požadujeme existenci další hodnoty v jiném sousedu, aby to celé tvořilo konzistentní cestu
** RPC (algoritmus): podobně jako AC-4, vedeme si seznam podpor a k němu přidáváme seznam míst kde musí být PC; při běhu se vždy udělá AC a potom testuje vybrané PC, dál zase návrh k AC, atd
* k-konzistence – libovolné konzistentní ohodnocení (k-1) proměnných můžeme rozšířit do libovolné k-té proměnné
** silná k-konzistence – j-konzistence pro každé j<=k
** NC = 1-konzistence; AC = (silná) 2-konzistence; PC = (silná) 3-konzistence
** pro přímé nalezení řešení grafu s n vrcholy je potřeba silná n-konzistence
* řešení CSP bez navracení – při nějakém uspořádání proměnných můžeme pro každou proměnnou najít kompatibilní ohodnocení
*: je-li graf podmínek silně k-konzistentní a k>w, kde w je jeho šířka, existuje upořádání proměnných pro vyřešení CSP bez navracení
*:* AC stačí na stromové grafy
*:* PC přidává nové hrany a tím si to kazí
** směrová k-konzistence
** adaptivní konzistence
* (i,j)-konzistence
* inverzní konzistence (IC)
* neighborhood inverse consistency (NIC)
* bodová A-konzistence
* zobecněná hranová konzistence (GAC) – pro nebinární podmínky, vychází z hodnoty proměnné vzhledem k podmínce (snese se s okolím), pak roztaženo na proměnnou, podmínku a celý problém
** upravené AC-3: podmínka jako sada propagačních metod pro každou proměnnou zvlášť, ty se pak ověřují
** konzistence okrajů (bounds consistency) – jen pro okraje domény
=== prohledávání s konzistencí ===
* prohledávání s navracením – po ohodnocení proměnné testujeme konzistenci
* look back – konzistence mezi již ohodnocenými proměnnými (backtracking)
* forward checking – vyřazování nekompatibilních hodnot budoucích proměnných
* partial look ahead – propagace vybrané hodnoty do všech budoucích proměnných
* full look ahead – rovnou to promlátíme pomocí plné AC
* maintaining arc consistency (MAC): provede AC přes spuštěním hledání a potom po každém kroku
* enumerace
;eliminace cyklů (CC)
* acyklický graf se dá vyřešit bez navracení
* ohodnotíme kružnicový řez a pak je to snadné
* MAC extended:
*# zajistíme AC
*# najdeme kružnicový řez
*# vyhodíme co není v žádném cyklu
*# pak přiřadíme hodnoty se zajišťováním hranové konzistence; co má jednoprvkovou doménu nebo není v žádném cyklu vyhodíme
*# znovu připojíme vyhozené proměnně a zajistíme do nich směrovou hranovou konzistenci
*# vyřešíme prohledáváním bez navracení
=== optimalizace pomocí omezujících podmínek ===
;branch and bound
: ořezávání větví v nichž není (optimální) řešení
;částečné splňování podmínek
* uvolnění zadání
* valued CSP – ocením podmínky, hledáme řešení které poruší co nejlevnější
* pravděpodobnostní CSP / CSP nad polo-okruhy
* hierarchie omezujících podmínek (nutné, preferované, ...); komparátory
** DeltaStar: z dosud nalezených řešení vybere to co nejlépe splňuje podmínky
** DeltaBlue
** Indigo: pro acyklické hierarchie, propaguje okraje domén, postupně přidává podmínky od nejsilnější po nejslabší
** projekční algoritmus
== Zkoušky ==
=== 17.5.2006 ===
Zkouška probíhala ústně. Otázky byly zaměřeny zpravidla na popis různých algoritmů. Jedna otázka zahrnovala přibližně obsah jedné přednášky
Otázky:
*Backtracking, backjumping a spol.
*Konzistenční techniky - hranová k., k. po cestě a další
*Prohledávání s heuristikami
*Lokální prohledávání
*pak ještě jedna, ale tu jsem nezaslechl :)
=== 31.5.2006 ===
Zkouška taktéž ústní, paralelně z automatovou písemkou. Přišli jsme dva takže času bylo dost.
Otázky:
* hranová konzistence, definice, algoritmy na ní, při znalosti principu nechá domyslet, DAC a chyták: DAC v obou směrech je AC, když na něco pustím ve dvou směrech DAC-1 tak to AC být nemusí, neb druhý průchod může rozbít první
* ?
=== 16.6.2006 ===
* Neuplne prohledavani
* Uplne prohledavani
* Duraz na formalni definice. Mit prehled nestaci.
== Odkazy ==
*Propracované [http://kti.ms.mff.cuni.cz/~bartak/podminky/prednaska.html slajdy z přednášky] (na homepage přednášky).
*[http://kti.ms.mff.cuni.cz/~bartak/constraints/ ON-LINE GUIDE TO CONSTRAINT PROGRAMMING] od Dr. Bartáka
[[category:Informatika]]
