{{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é

    • – 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

    • – 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. 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

    • : 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á

    • 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): Rij = Rij & (Rik * Rkk * Rkj), kde Rkk 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:

    1. zajistíme AC

    2. najdeme kružnicový řez

    3. vyhodíme co není v žádném cyklu

    4. 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

    5. znovu připojíme vyhozené proměnně a zajistíme do nich směrovou hranovou konzistenci

    6. 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é slajdy z přednášky (na homepage přednášky). *ON-LINE GUIDE TO CONSTRAINT PROGRAMMING od Dr. Bartáka

category:Informatika