Programování s omezujícími podmínkami

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
Programování s omezujícími podmínkami
Kód předmětu: NOPT042
Přednáší: Roman Barták

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é
  • backtracking
    • 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
    • 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. 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
    • 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á
    • 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

Citováno z „http://wiki.matfyz.cz/index.php?title=Programování_s_omezujícími_podmínkami&oldid=19063“