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

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): R_ij = R_ij & (R_ik * R_kk * R_kj), kde R_kk 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