PA163 Programovaní s omezujícími podmínkami podzim 201 8 Základní informace Web předmětu: na IS průsvitky průběžně na ISu (interaktivní osnova, učební materiály) 3 vzorové příklady z řešeními: ukázky pro písemku i domácí úkoly Ukončení předmětu: písemná práce až 100 bodů ±> cca 7 otázek: přehledové, srovnávací, algoritmy, pojmy, příklady (model) cca 30 bodů: příklad(y) návrhu modelu problému - probíráno ve cvičení ±> vzory písemné práce dostupné na webu předmětu M 2 domácí úkoly X> za jednu domácí úlohu lze získat až 1 0 bodů -L podmínkou je získání alespoň 8 bodů z celkového počtu 20 bodů za D.Ú. M hodnocení: A 1 00 a více, B 90-99, C 80-89, D 70-79, E 60-69 M Omezující podmínky v navazujících přednáškách: M PA1 67 Rozvrhování Hana Rudová, Omezující podmínky, 4. prosince 2018 2 Organizace předmětu Literatura & Dechter, R. Constraint processing. Morgan Kaufmann Publishers, 2003. 3 http://www.ics.uci.edu/~dechter/books/ Tsang, E. Foundations of Constraint Satisfaction. Academic Press, 1993. na webu dostupný plný text knihy http://cswww.essex.ac.uk/Research/CSP/edward/FCS.html I Barták, R. On-line guide to constraint programming. http://ktilinux.ms.mff.cuni.cz/~bartak/constraints/ & Barták, R. Programovaní s omezujícími podmínkami, přednáška na MFF UK. M http://kti.ms.mff.cuni.cz/~bartak/podminky/index.html Elektronické materiály viz web předmětu Hana Rudová, Omezující podmínky, 4. prosince 2018 3 Organizace předmětu Přehled přednášky Úvod Konzistenční algoritmy Prohledávací algoritmy Optimalizační problémy a řešení Opakování v příkladech I Hana Rudová, Omezující podmínky, 4. prosince 201 8 4 Organizace předmětu Cvičení Účast na cvičeních povinná M v případě více než jedné absence nutné zpracovat doplňující příklady M při vysokém počtu absencí na cvičení předmět absolvovat nelze Cíl praktické procvičení příkladů s omezujícími podmínkami u počítačů 3 Obsah Úvod do programovacího jazyka OPL ILOG od firmy IBM * Řešení problémů: globální podmínky, modelování, rozvrhování, prohledávání Hana Rudová, Omezující podmínky, 4. prosince 201 8 5 Organizace předmětu Software: IBM ILOG CPLEX Optimization Studio Dostupné ke stažení ve Studijních materiálech Licence dostupná výhradně pro studenty předmětu! Šířením porušíte licenci. Optimization Programming Language (OPL) přirozený matematický popis optimalizačních modelů M vysoko-úrovňová syntaxe s jednoduchým a stručným kódem řešení problémů nejen s omezujícími podmínkami ale i pro matematické programování M http://www-01.i bm.com/software/commerce/opti mi zati on/model i ng/ Tutoriály a dokumentace ve Studijních materiálech https://i s.muni.cz/auth/el/1433/podzi m2018/PA163/i1og/IL0G02_cou rse.zi p Hana Rudová, Omezující podmínky, 4. prosince 201 8 6 Organizace předmětu Optimization Programming Language (OPL) Společnost Volsay vyrábí sloučeniny NH3 (amoniak) a NH4CI (chlorid amonný). Volsay má k dispozici 50 jednotek dusíku (N), 1 80 jednotek vodíku (H) a 40 jednotek chloru (Cl). Volsay má zisk 40 EUR za prodej jednotky NH3 a 50 EUR za jednotku NH4CI.Jak Volsay maximalizuje zisk na základě skladových zásob? I using CP; dvar int+ gas; dvar int+ chloride; I maxi mi ze 40 * gas + 50 * chloride I subject to { gas + chloride <= 50; 3 * gas + 4 * chloride <= 180; chloride <= 40; }; I Hana Rudová, Omezující podmínky, 4. prosince 201 8 7 Organizace předmětu Úvod do programování s omezujícími podmínkami Obsah přednášky Ukázkový příklad: sudoku Základní pojmy: omezení, ... Jak řešíme problémy s omezujícími podmínkami Příklady a aplikace & Složitost a úplnost Hana Rudová, Omezující podmínky, 4. prosince 201 8 9 Úvod do CP Sudoku: problém 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Přiřaď prázdným polím čísla tak, že: čísla odlišná na řádku, ve sloupci a v bloku Příklad převzat z přednášky Ch.Schulte, University of Uppsala Hana Rudová, Omezující podmínky, 4. prosince 2018 10 Úvod do CP Sudoku: řádky 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Přiřaď prázdným polím čísla tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 4. prosince 201 8 Úvod do CP Sudoku: sloupce 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Přiřaď prázdným polím čísla tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 4. prosince 201 8 12 Úvod do CP Sudoku: bloky 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Přiřaď prázdným polím čísla tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 4. prosince 201 8 13 Úvod do CP Propagace v bloku: vstup 8 co 3 Žádné pole v bloku nemůže obsahovat čísla 3,6,8 Hana Rudová, Omezující podmínky, 4. prosince 201 8 14 Úvod do CP Propagace v bloku: promazání hodnot 1,2,4,5,7,9 8 1,2,4,5,7,9 1,2,4,5,7,9 6 3 1,2,4,5,7,9 1,2,4,5,7,9 1,2,4,5,7,9 3 Žádné pole v bloku nemůže obsahovat čísla 3,6,8 3 propagace do dalších polí v bloku Řádky a sloupce: podobně Hana Rudová, Omezující podmínky, 4. prosince 2018 15 Úvod do CP Propagace: jedno pole 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Odstranění čísel z polí tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 4. prosince 201 8 16 1,2,3,4,5,6,7,8,9 Úvod do CP Propagace: jedno pole a řádek 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Odstranění čísel z polí tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 4. prosince 201 8 17 Úvod do CP Propagace: jedno pole a sloupec 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Odstranění čísel z polí tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 4. prosince 201 8 18 Úvod do CP Propagace: jedno pole a blok 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Odstranění čísel z polí tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 4. prosince 201 8 19 Úvod do CP Iterativní propagace 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Iterování propagací pro řádky, sloupce, bloky Pokud stále zůstává více možností: prohledávání Hana Rudová, Omezující podmínky, 4. prosince 2018 20 Úvod do CP Sudoku a programování s omezujícími podmínkami 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Proměnné: pro každé pole mají hodnoty: čísla ' udržování množiny možných čísel Omezení: vyjadřují odlišnosti 3 relace mezi proměnnými Modelování: proměnné, hodnoty, omezení Řešení: propagace, prohledávání Hana Rudová, Omezující podmínky, 4. prosince 201 8 21 Úvod do CP Dána Omezení (constraint) 3 množina (doménových) proměnných Y = {yi,... ,yk} 3 konečná množina hodnot (doména) D = D\ u ... u Dk Omezení (podmínka) c na Y je podmnožina D\ x ... x Dk tj. relace «• omezuje hodnoty, kterých mohou proměnné nabývat současně I 3 Příklad: I 3 proměnné: A,B domény: {0,1} pro A {1,2} pro B -•omezení: A^B nebo (A,B) e {(0,1 ),(0,2),(1,2)} I Omezení c definováno na proměnných yi,.. .y^ je splněno, pokud pro hodnoty d\ e Di, ...dk^Dk platí (di,... dk) ^ c 3 příklad (pokračování): omezení splněno pro (0,1), (0,2), (1, 2), není splněno pro (1,1) Hana Rudová, Omezující podmínky, 4. prosince 201 8 22 Úvod do CP Problém splňování podmínek (CSP) Dána M konečná množina proměnných X = {x\,..., xn} M konečná množina hodnot (doména) D = D\ u ... u D 3 konečná množina omezení C = {ci,..., cm} 3 omezení je definováno na podmnožině X Problém splňování podmínek je trojice (X,D,C) (constraint satisfaction problem) I 3 Příklad: 3 proměnné: A,B, C -•domény: A e {0,1} B = l C e {0,1,2} M omezení: A =/= B B =/= C Hana Rudová, Omezující podmínky, 4. prosince 201 8 23 Úvod do CP Řešení CSP & Částečné ohodnocení (přiřazení) proměnných (d\,..., dk),k < n M některé proměnné mají přiřazenu hodnotu Úplné ohodnocení (přiřazení) proměnných (di,..., dn) 3 všechny proměnné mají přiřazenu hodnotu I Řešení CSP I úplné ohodnocení proměnných, které splňuje všechna omezení (di,...,dn) g Di x ... x Dn je řešení (X,D,C) ±> pro každé a e C na x^,.. .Xik platí (d^,... dik) e a I Hledáme: jedno řešení nebo všechna řešení nebo optimální řešení vzhledem k účelové funkci, tj. řešíme optimalizační problém s podmínkami (constraint optimization problem) Hana Rudová, Omezující podmínky, 4. prosince 2018 24 Úvod do CP Přístup CP k programování Formulace daného problému pomocí omezení: modelování Řešení vybrané reprezentace pomocí M doménově specifických metod M obecných metod Hana Rudová, Omezující podmínky, 4. prosince 201 8 25 Úvod do CP Obecné metody Algoritmy propagace omezení (konzistenční algoritmy) umožňují odstranit nekonzistentní hodnoty z domén proměnných M zjednodušují problém 3 udržují ekvivalenci mezi původním a zjednodušeným problémem používají se pro výpočet lokální konzistence I 3 aproximují tak globální konzistenci A e {0,1}, B = 1, C g {0,1,2}, A + B, A + Cl po propagaci: A = 0, B = 1, C g {1,2} I Prohledávací algoritmy M prohledávání stavového prostoru řešení příklady: backtracking, metoda větví a mezí Hana Rudová, Omezující podmínky, 4. prosince 201 8 26 Úvod do CP Prohledávání: příklad Prohledávání pomocí větvení vytvoření podproblému s dodatečnou informací umožní další propagaci omezení X: {4,5}, Y: {4,5} X >=Y I X=4 X£4 X = 4, Y = 4 X >=Y X = 5, Y: {4,5} X >=Y Hana Rudová, Omezující podmínky, 4. prosince 201 8 27 Úvod do CP Doménově specifické metody Specializované algoritmy 3 Nazývány řešiče omezení (constraint solvers) 3 Příklady: program pro řešení systému lineárních rovnic 3 knihovny pro lineární programování 3 implementace unifikačního algoritmu I Programování s omezujícími podmínkami 3 široký pojem zahrnující řadu oblastí 3 lineární algebra, globální optimalizace, lineární a celočíselné programování, ... 3 Existence doménově specifických metod => použití místo obecných metod hledání doménově specifických metod tak, aby mohly být použity místo obecných metod Hana Rudová, Omezující podmínky, 4. prosince 2018 28 Úvod do CP Algebrogram Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilc 3 SEND + MORE MONEY M různá písmena mají přiřazena různé cifry M S a M nejsou 0 Jediné řešení: 9567 + 1085 10652 I 3 Proměnné: S,E,N,D,M,O,R,Y 3 Domény: 1 ..9 pro S,M 0..9 pro E,N,D,0,R,Y Hana Rudová, Omezující podmínky, 4. prosince 201 8 29 Algebrogram: alternativy pro omezení rovnosti 1 omezení rovnosti 1000*S + 100*E + 10*N + D SEND + 1000*M + 100*0 + 10*R + E + MORE = 10000*M + 1000*0 + 100*N + 10*E + Y MONEY 5 omezení rovnosti použití „přenosových" proměnných P1,P2,P3,P4 s doménami 0..1 D + E = 10*P1 + Y, PI + N + R = 10*P2 + E, P2 + E + 0 = 10*P3 + N, P3 + S + M = 10*P4 + 0 P4 M Hana Rudová, Omezující podmínky, 4. prosince 201 8 30 Úvod do CP Algebrogram: alternativy pro omezení nerovnosti 28 omezení nerovnosti: X + Y pro X,Y e {S,E,N,D,M,0,R,Y} I 1 omezení pro nerovnost ' pro proměnné xi,...,xn s doménami Di,... ,Dn: al l_di fferent (x\,... ,xn) := {(di,..., dn) , di =/= d j pro i =/= j} Hana Rudová, Omezující podmínky, 4. prosince 201 8 31 Úvod do CP Optimalizační problém s podmínkami (COP) Problém splňování podmínek (X, D, C) Účelová funkce obj : Sol — W M Optimalizační problém s podmínkami (constraint optimization problem) M nalezení řešení d pro (X,D, C) takové, že obj(d) je optimálni ± optimální = maximální nebo minimálni Hana Rudová, Omezující podmínky, 4. prosince 201 8 32 Úvod do CP Problém batohu (knapsack problem) Je dán batoh velikosti man předmětů různé velikosti a ceny. Vyberte takové předměty, aby se vešly do batohu a jejich celková cena byla maximální. Batoh velikosti m Předměty velikosti Vi,..., vn a ceny ci,..., cnl Proměnné: Xi,... ,xn I Domény: 0..1 I M Omezení: ^Ví.Xí ConstSize identifikátory místností uspořádány podle velikosti M ConstSize: nejmenší identifikátor místnosti s velikostí Size I v jedné místnosti v každém čase nejvýše jeden předmět jeden vyučující učí nejvýše jeden předmět v každém čase Hana Rudová, Omezující podmínky, 4. prosince 2018 36 Úvod do CP Univerzitní rozvrhování: optimalizace Optimalizační kritéria výuka v preferovaných časech cena za výuku předmětu I ve vybraném čase: CostTimel CostTime = CostTimel + CostTime2 + ■ ■ ■ I 3 výuka v preferovaných místnostech I cena za výuku předmětu I ve vybraném čase: CostRooml M CostRoom = CostRooml + CostRoom2 + ■ ■ ■ I dva předměty jednoho studenta by se neměly překrývat dva předměty IJ zároveň navštěvuje SIJ studentů M CostOverlap = ^ SIJ I IJ:Timel=TimeJ minimize (WTime * CostTime + WRoom * CostRoom + WOverlap * CostOverlap) Hana Rudová, Omezující podmínky, 4. prosince 201 8 37 Úvod do CP Polynomiální a NP-úplné problémy Polynomiální problémy M existuje algoritmus polynomiální složitosti pro řešení problému NP-úplné problémy 3 řešitelné nedeterministickým polynomiálním algoritmem potenciální řešení lze ověřit v polynomiálním čase M v nejhorším případě exponenciální složitost (pokud neplatí P=NP) Hana Rudová, Omezující podmínky, 4. prosince 201 8 38 Úvod do CP Složitost: polynomiální problémy Lineární rovnice nad reálnými čísly S proměnné nad doménami z R, omezení: lineární rovnice M Gaussova eliminace polynomiální složitost I Lineární nerovnice nad reálnými čísly 3 lineární programování, simplexová metoda často stačí polynomiální složitost Hana Rudová, Omezující podmínky, 4. prosince 201 8 39 Úvod do CP Složitost: NP-úplné problémy Boolean omezení 0/1 proměnné omezení = Boolean formule (konjunkce, disjunkce, implikace, ...) ±> příklad: proměnné A,B, C, omezení (A v B), (C => A), CSP problém (A v B) a (C => A) I M problém splnitelnosti Boolean formule (SAT problém): NP-úplný n proměnných: 2n možností I Omezení nad konečnými doménami obecný CSP problém 3 problém splnitelnosti nad obecnými relacemi 3 NP-úplný problém 3 n proměnných, d maximální velikost domény: dn možností Hana Rudová, Omezující podmínky, 4. prosince 201 8 40 Úvod do CP Složitost a úplnost 3 Úplné vs. neúplné algoritmy 3 úplný algoritmus prozkoumává množinu všech řešení neúplný algoritmus: neprozkoumává celou množinu řešení 3 nevím jako možná odpověď, ziskem může být efektivita 3 příklad: neúplný polynomiální algoritmus pro NP-úplný problém I 3 Složitost řešiče I Gaussova eliminace (P), SAT řešiče (NP), obecný CSP řešič (NP) Složitost algoritmů propagace omezení většinou polynomiální neúplné algoritmy I 3 Složitost prohledávacích algoritmů 3 úplné algoritmy, příklady: backtracking, generuj & testuj neúplné algoritmy, neprohledávají celý prostor řešení, příklad: omezení času prohledávání Hana Rudová, Omezující podmínky, 4. prosince 2018 41 Úvod do CP Grafová reprezentace CSP Reprezentace podmínek 3 intenzionální (matematická/logická formule) 3 extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) I 3 Graf: vrcholy, hrany (hrana spojuje dva vrcholy) 3 Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholů) Reprezentace CSP pomocí hypergrafu podmínek 3 vrchol = proměnná, hyperhrana = podmínka I 3 Příklad 3 omezení c\ : X\ + x 2 + Xq = 1 proměnné X\ Xq s doménou {0,1} Hana Rudová, Omezující podmínky, 4. prosince 201 8 Binární CSP Binární CSP CSP, ve kterém jsou pouze binární podmínky 3 unární podmínky zakódovány do domény proměnné Graf podmínek pro binární CSP 3 není nutné uvažovat hypergraf, stačí graf (podmínka spojuje pouze dva vrcholy) I CSP lze transformovat na binární CSP Ekvivalence CSP dva CSP problémy jsou ekvivalentní, pokud mají stejnou množinu řešení Rozšířená ekvivalence CSP 3 řešení problémů lze mezi sebou „syntakticky" převést 3 např: obecný CSP převedeme na binární CSP a porovnáme tyto binární CSP Hana Rudová, Omezující podmínky, 4. prosince 2018 43 Úvod do CP Duální problém Duální problém: původním omezením odpovídají nové duální proměnné proměnné: fc-ární podmínku q převedeme na duální proměnnou Ví s doménou obsahující konzistentní fc-tice ^ omezení: pro každou dvojici podmínek q a Cj sdílející proměnné zavedeme binární podmínku Ríj mezi Ví a Vj omezující duální proměnné na fc-tice, ve kterých mají sdílené proměnné stejnou hodnotu (0,0,1), (0,1,0), R21 & R33 (0,0,0), (0,1,1), 3 Příklad (1,0,0) (1,0,1) M proměnné Xi,...,X6 s doménou {0,1} omezení c\ : X\ + X2 + Xq = 1... v\ R11 \R33 R22 & R33 C2 : X\ - X3 + X4 = 1... V2 C3 : X4 + Xs - Xq > 0 . . . V3 (0,0,1), (1,0,0), (0,1,0), (1,0,0), C4 : X2 + Xs - Xq = 0 . . . V4 (1,1,1) R31 (1,1,0), (1,1,1) V2 Hana Rudová, Omezující podmínky, 4. prosince 201 8 44 Úvod do CP Použití binarizace 3 Konstrukce duálního problému M jedna z možných metod binarizace Výhody binarizace 3 získáváme unifikovaný tvar CSP problému řada algoritmů navržena pro binární CSP M pro výukové účely je vysvětlení na binárních CSP vhodné -i* algoritmy jsou přehlednější a jednodušší na pochopení -i* verze pro nebinární podmínky je často přímým rozšířením obecné verze ±* a tyto algoritmy jsou i aplikovatelné s pomocí binarizace na obecné CSP Ale: značné zvětšení velikosti problému I Nebinární podmínky M složitější propagační algoritmy 3 lze využít jejich sémantiky pro lepší propagaci příklad: al l_di f f erent vs. množina binárních nerovností Hana Rudová, Omezující podmínky, 4. prosince 2018 45 Úvod do CP Hranová konzistence Propagace omezení Příklad: S proměnné: A,B,C .•domény: A g {0,1} B=0 C g {0,1,2,3} M omezení: A^B, B^C, A^C =^> A=l, B=0, C g {2,3} Algoritmy pro propagaci omezení (konzistenční algoritmy) umožňují odstranit nekonzistentní hodnoty z domén proměnných zjednodušují problém udržují ekvivalenci mezi původním a zjednodušeným problémem Hana Rudová, Omezující podmínky, 4. prosince 201 8 47 Hranová konzistence Vrcholová konzistence Vrcholová konzistence (node consistency) NC S unární podmínky převedeme do domén proměnných Vrchol reprezentující Vije vrcholově konzistentní: M každá hodnota z aktuální domény proměnné Ví splňuje všechny unární podmínky s proměnnou Ví I CSP problém je vrcholově konzistentní: M každý jeho vrchol je vrcholově konzistentní Hana Rudová, Omezující podmínky, 4. prosince 201 8 48 Hranová konzistence Hranová konzistence (Arc Consistency AC) Pouze pro binární CSP (až její rozšíření jsou pro nebinární CSP) podmínka odpovídá hraně v grafu podmínek více podmínek najedná hraně převedeme dojedná podmínky Hrana (Ví, V}) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Dí existuje hodnota y v D j tak, že ohodnocení [Ví = x,Vj = y] splňuje všechny binární podmínky nad Ví, V/. I | Hranová konzistence je směrová konzistence hrany (Ví,Vj) nezaručuje konzistenci hrany (Vj,Ví) A již zrevidované hrany opět nekonzistentní Revize hrany opakujeme, dokud dochází ke zmenšení nějaké domény 3 procedure AC-l(G) repeat Changed := false for V hranu (í, j) G G do Changed := revise((í,j)) or Changed until not(Changed) end AC-1 I => AB, BA, BC, CB, lAB, BA, BC, CB, lAB, BA, BC, CB Hana Rudová, Omezující podmínky, 4. prosince 2018 51 Hranová konzistence Složitost AC-1 proceduře AC-l(G) repeat Changed := false for V hranu (í,j) G G do Changed := revi se((í, j)) or Changed until not(Changed) end AC-1 k maximální velikost domény, e počet hran, n počet proměnných I ' M Složitost 0(enk3) I 3 cyklus přes všechny hrany 0(e) I revi se 0(k2) I 3 jeden cyklus smaže (v nejhorším případě) právě jednu hodnotu z domény proměnné, celkem nk hodnot (každá proměnná má v doméně až k hodnot) => O(nk) Hana Rudová, Omezující podmínky, 4. prosince 2018 52 Hranová konzistence Neefektivita AC-1 I když zmenšíme jedinou doménu, provádí se revize všech hran. Tyto hrany ale revizí nemusí být vůbec zasaženy. Jaké hrany tedy revidovat po zmenšení domény? I ty, jejichž konzistence může být zmenšením domény proměnné narušena jsou to hrany (í, k), které vedou do proměnné Vk se zmenšenou doménou ti'V (k,m) I Vk ... proměnná se zmenšenou doménou (i2,k) (m,k) při revizi (k,m) došlo ke zmenšení domény Vk 3 hranu (m, k) vedoucí z proměnné Vm, která zmenšení domény způsobila, není třeba revidovat (změna se jí nedotkne) I M příklad: Vk < Vm, Vk in 1 ..1 0, Vm in 2..11, smazání 11 z Vm, tj. Vk in 1 ..1 0, Vm in 2..1 0, důsledek: doména Vk se změní, smaže se 1 0, tj. Vk in 1 ..9, Vm in 2..1 0, a teď reaguji na změnu Vk revizemi (Ví, Vk)'. je tedy zbytečné dělat revizi (Vm, Vk) Hana Rudová, Omezující podmínky, 4. prosince 2018 53 Hranová konzistence Algoritmus AC-3 Opakování revizí můžeme dělat pomocí fronty stačí jediná fronta hran, které je potřeba (znova) zrevidovat přidáváme tam jen hrany, jejichž konzistence mohla být narušena zmenšením domény I V procedure AC-3(G) Q := {(í,j) I (í,j) g hrany(G), i ± j] while Q non empty do vyber a smaž (fc,m) z Q if revise((fc,m)) then Q := Q u {(í, k) e hrany(G), i ± k, i ± m} end while . _ A O (k) 3 jakmile je omezení přidáno do fronty, doména (fc) jedné z jeho dvou proměnných (2) byla redukována alespoň o jednu hodnotu 3 Technika AC-3 je dnes asi nejpoužívánější, ale stále není optimální Hana Rudová, Omezující podmínky, 4. prosince 201 8 55 Hranová konzistence Podpora hodnoty AC-3: při každé revizi hrany testujeme množství dvojic hodnot na konzistenci vzhledem k podmínce. Tyto testy znova opakujeme při každé další revizi hrany. I 3 Při revizi hrany (V2,Vi) vyřadíme hodnotu a z domény proměnné V2. M Nyní musíme prozkoumat doménu V3, zda některá z hodnot a, b, c, d neztratila svoji podporu ve V2.1 «• Hodnoty a, b, c není třeba znova kontrolovat <= mají ve V2 také jinou podporu než a. I Podpora (support) pro a e Di = {(j,b) \ b e D j, (a, b) e Cíj} M a e D2 má podpory {(3, a), (3, b), (3, d)} M d e d3 má pouze jedinou podporu {{2, a)} M b g D2 má podpory {(1,a), (1, c), (3, a), (3, c)} I Podpory spočítáme jen jednou. Při opakovaných revizích je budeme používat. Hana Rudová, Omezující podmínky, 4. prosince 2018 56 Hranová konzistence Algoritmus na inicializaci podpor 3 Udržujeme seznam hodnot, které sami podporujeme (víme komu říct, když zmizíme). S j y. množina dvojic (í, a), pro které je (j,b) podporou 3 Udržujeme počet vlastních podpor (víme, co nám chybí). counter[(í, j), a]: počet podpor, které má hodnota a e Di u proměnné V j procedure initial i ze (G) Q := {}, S := {} // vyprázdněni datových struktur for each (VuVj~) e h rany (G) do for each a e Di do total := 0 for each b e D j do if (a,b) konzistentní' vzhledem k aj then total := total+1 Sj,fc := Sjtb u {{í,a)} counter [(í, j), a] := total if counter[(í,j),a] = 0 then smaž a z Di Q := Q u i(í,a)} return Q // Q je fronta se smazanými hodnotami Hana Rudová, Omezující podmínky, 4. prosince 2018 57 Hranová konzistence Aktualizace podpor během výpočtu Situace po zpracování hrany (Ví, V}) algoritmem initialize counter^ j} 2 2 1 , , I Využití struktur s podporami: 1. Předpokládejme, že b3 je vyřazena z domény V). 2. Zjistíme v Sj,^, pro které hodnoty je b3 podporou (tj. (í, a2), (í, a3>). 3. Snížíme counter u těchto hodnot (odstraníme jim jednu podporu). 4. Pokud je některý counter vynulován (a3), potom příslušnou hodnotu vyřadíme z domény a pokračujeme s ní od kroku (1). counter(j $ i 2 a1 — 1 a2= 0 , í<^a3> I __j Hana Rudová, Omezující podmínky, 4. prosince 201 8 58 Hranová konzistence Algoritmus AC-4 proceduře AC-4(G) Q := initialize(G) while not empty(Q) do vyber a smaž libovolný (j,b) gQ for each (í, a) e Sjtb do counter[(í,j),a] : = counter[(í,j),a] - 1 if (counter[(í,j),a] = 0) a (a e D{) then smaž a z Dt Q := Q u {<í,a>} I ^ Složitost 0(ek2) => algoritmus optimální v nejhorším případě složitost initialize 0(ek2) <= (Ví, V}) g hrany(G), a e Dif b e Dj M složitost while cyklu 0(ek2): postupně musím odebrat všechny podpory a těch je 0(ek2) I Paměťová náročnost, není nejlepší v průměrném případě (inicializace zůstává) Hana Rudová, Omezující podmínky, 4. prosince 201 8 59 Hranová konzistence Další AC algoritmy Existuje řada dalších algoritmů pro zajištění hranové konzistence 3 AC-5, AC-6, AC-7, ... M AC-6 (Bessiěre, Cordier) 3 zlepšuje paměťovou náročnost a průměrný čas AC-4 drží si pouze jednu podporu, další podpory hledá až při ztrátě aktuální podpory I M AC-3.1: AC-3 hledá podpory vždy od začátku, jak to vylepšit? AC-2001: AC-3 s frontou proměnných místo fronty omezení Porovnání: «• AC-3 není (teoreticky) optimální AC-4 je (teoreticky) optimální, ale (prakticky) pomalý AC-6/7 jsou (prakticky) rychlejší než AC-4, ale složité 3 AC-2001: v praxi je časté využití fronty proměnných Hana Rudová, Omezující podmínky, 4. prosince 2018 60 Hranová konzistence AC-3.1: optimální algoritmus AC-3 3 Co je na AC-3 neefektivní? hledání podpor v REVISE, které vždy začíná od nuly! if „neexistuje y e D j takové, že (x, y) je konzistentní" then AC-3.1 (Zhang, Yap) M běh stejný jako u AC-3 pro každou hodnotu si pamatuje poslední nalezenou podporu (last) v každém směru a hledání začíná u ní ' procedúre EXIST((i,x),j) y := last{{í,x),j) if y G Dj then return true while y := next(y,Dj) a y ± níl do i f (x, y) e a j then % aj omezeni s proměnými í, j last{{í,x),j) := y return true return false Hana Rudová, Omezující podmínky, 4. prosince 2018 61 Hranová konzistence AC-2001: jiný optimální algoritmus AC-3 procedure AC-2001(g) Používá verzi AC-3 s frontou proměnných Q := {í\ í e vrcholy (G)} % seznam vrcholů pro revizi while neprazdna(Q) do vyber a smaž j z Q for Ví g vrcholy (G) takové, že (í, j) e hrany (G) do if REVISE2001 (í,j) then if Di = 0 then return fail Q := Q u {í} return true I procedure REVISE2001 (i, j) DELETED := false for Vx g Di do if last((í,x),j) é D j then \f3yeDj a y > las t {{í, x), j) a (x,;y)ecij then last((í,x),j) := y else smaž x z Dí; DELETED := true return DELETED Algoritmus fakticky pracuje s rozdílovými množinami, tj. pro každou proměnnou si pamatuje, jaké hodnoty byly smazány z domény od poslední revize (podobně jako AC-3.1) I Hana Rudová, Omezující podmínky, 4. prosince 201 8 62 Hranová konzistence Je hranová konzistence dostatečná (úplná)? Použitím AC odstraníme mnoho nekompatibilních hodnot 3 Dostaneme potom řešení problému? NE 3 Víme alespoň zda řešení existuje? NE I 3 X,Y,Z e {1,2}, X+Y, Y + Z, Z + X 3 hranově konzistentní 3 nemá žádné řešení I Jaký je tedy význam AC? 3 někdy dá řešení přímo i* nějaká doména se vyprázdní => řešení neexistuje všechny domény jsou jednoprvkové => máme řešení 3 v obecném případě se alespoň zmenší prohledávaný prostor Hana Rudová, Omezující podmínky, 4. prosince 201 8 63 Hranová konzistence Konzistence po cestě Konzistence po cestě (PC path consistency) M Příklad: X,Y,Z e {1,2}, X ± Y, Y ±Z, Z±X M Jak posílit konzistenci? Budeme se zabývat několika podmínkami najednou. Cesta (Vo, Vi,..., Vm) je konzistentní právě tehdy, když pro každou dvojici hodnot x e Do a y e Dm splňující binární podmínky na hraně Vo, Vm existuje ohodnocení proměnných Ví,... Vm-i takové, že všechny binární podmínky mezi sousedy Vj, yJ+i jsou splněny. CSP je konzistentní po cestě, právě když jsou všechny cesty konzistentní.l Definice PC nezaručuje, že jsou splněny všechny podmínky nad vrcholy cesty, zabývá se pouze podmínkami mezi sousedy l Hana Rudová, Omezující podmínky, 4. prosince 201 8 65 Konzistence po cestě PC a cesty délky 2 3 Zjišťování konzistence všech cest není efektivní Stačí ověřit konzistenci cest délky 2 Věta: CSPje PC právě tehdy, když každá cesta délky 2 je PCI Důkaz: 1) PC => cesty délky 2 jsou PC I 2) cesty délky 2 jsou PC => V n cesty délky n jsou PC => PC indukcí podle délky cesty a) n = 2 platí triviálně b) n + 1 (za předpokladu, že platí pro n) i) vezmeme libovolných n+ 2 vrcholů Vo, V\,..., Vn+\ ii) vezmeme libovolné dvě kompatibilní hodnoty xq e Do a xn+\ e D (kompatibilní = splňující všechny bin.podmínky mezi Xo a xn+\) iii) podle a) jsou všechny cesty délky 2 PC, a tedy i Vo, Vn, Vn+\ je PC najdeme tedy xn e Dn tak, že (xo,xn) a (xn, xn+\) jsou konzistentní iv) podle indukčního kroku najdeme zbylé hodnoty na cestě Vo, V\,..., Vni M Definici PC lze tedy upravit tak, že vyžadujeme pouze konzistenci cest délky 21 Hana Rudová, Omezující podmínky, 4. prosince 2018 66 Konzistence po cestě Vztah PC a AC PC => AC M pokud je cesta (í,j,í) konzistentní (PC), pak je i hrana (í, j) konzistentní (AC), tj. z PC tedy plyne AC 3 PC: ke každé „dvojici hodnot" pro í, i najdu hodnotu v j => AC: ke každé hodnotě v i tedy najdu hodnotu v ji M AC 4> PC 3 příklad: X,Y, Z e {1,2}, X^Y, Y^Z, Z^X 1 .0 je AC, ale není PC, X=0, Y=l nelze rozšířit po cestě (X,Z,Y)I AC vyřazuje nekompatibilní prvky z domény proměnných. Co dělá PC? 3 PC vyřazuje dvojice hodnot PC si pamatuje podmínky explicitně PC si pamatuje, které dvojice hodnot jsou v relaci 3 PC dělá všechny relace nad dvojicemi implicitní (A A+1 již zrevidované cesty opět nekonzistentní Revize cesty opakujeme dokud jsou nějaké dvojice smazány Princip je podobný jako u AC-1 Před spuštěním algoritmu nutno inicializovat relace Rij pomocí existujících binárních (i unárních) podmínek ' & proceduře PC-l(G) repeat Changed := falše f or m : = 1 to n for í : = 1 to n for j := 1 to n Changed := revise-3(í,m,j) or Changed until not(Changed) end PC-1 Hana Rudová, Omezující podmínky, 4. prosince 2018 70 Konzistence po cestě Složitost algoritmu PC-1 M Celková složitost 0(n5k5) odvození podobné jako pro AC-1 <= 3 cykly pro trojice hodnot 0(n3) revise-3 0(k3) <= 0(n2k2) počet opakování repeat cyklu <= jeden cyklus smaže (v nejhorším případě) právě jednu dvojici hodnot celkem n2k2 hodnot (n2 dvojic proměnných, k2 dvojic hodnot pro každou dvojici proměnných)! Neefektivita PC-1 opakovaná revize všech cest, i když pro ně nedošlo k žádné změně 3 při revizi stačí kontrolovat jen zasažené cesty podobně jako pro PC-il M cesty stačí brát pouze s jednou orientací ... Rij je totéž co Rjt * příklad: VltV2 e {a,b},V3 e {a,b,c},V1 ŕ V2,V2 ŕ V,3Vi ŕ V3 důsledek revi se-3(l, 2, 3) a revi se-3(3, 2,1) je totožný <= ke každé dvojici hodnot z V\, V3 (V3, V\) hledám kompatibilní hodnotu z V2 Hana Rudová, Omezující podmínky, 4. prosince 2018 71 Konzistence po cestě Algoritmus PC-2 Cesty beru pouze s jednou orientací aktualizuji pouze jednu z R^, Rjí 3 Do fronty dávám pouze zasažené cesty podobná modifikace jako AC-3 * revi se-3 (í, m, j) mění R^, stačí tedy aktualizovat Ru přes j a Rij přes íl Před spuštěním algoritmu M inicializovat relace Ríj pomocí existujících binárních (i unárních) podmínek 3 proceduře PC-2(G) Q := {(í,m, j) | 1 < i < j < n, 1 < m < n, m ± í, m ± j} //seznam cest pro revizi while Q non empty do vyber a smaž trojici (í,m,j) z Q i f revi se-3 (í, m, j) then Q := Q u {(l,í,j)(l,j,í) I 1 < l 0(k2) <= když je (í,m,j) přidáno do fronty, Ríj bylo redukováno alespoň o jednu hodnotu M celkem n3 trojic (í,m,j) => 0{n3) 3 revise-3 0(k?)\ M Algoritmus není optimální podobně jako AC-3 3 existuje algoritmus PC-4 založen na počítání podpor složitost PC-4 je 0(n3k3), což už je optimálníl Cvičení: řešte následující problém pomocí PC-2 algoritmu VI g {0,1,2,3},V2 g {0,1},V3 g {1,2} V3 = vi + i,V2 ± V3,V1 + V2I Nápověda: zkonstruuj iniciální relace iniciálně přidej do fronty (VI, V2, V3), (VI, V3, V2), (V2, VI, V3) Hana Rudová, Omezující podmínky, 4. prosince 2018 73 Konzistence po cestě Omezení PC algoritmů Paměťové nároky M protože PC eliminuje dvojice hodnot z omezení, potřebuje používat extenzionální reprezentaci omezení (pro každou dvojici hodnot si pamatuji, zdaje/není v doméně) Poměr výkon/cena PC eliminuje více (nebo stejně) nekonzistencí jako AC poměr výkonu ke zjednodušení problému je ale mnohem horší než u AC Změny grafu omezení PC přidává hrany (omezení) i tam, kde původně nebyly a mění tak konektivitu grafu to vadí při dalším řešení problému, kdy se nemohou používat heuristiky odvozené od grafu (resp. dané původním problémem) PC stále není dostatečné M V,X,Y,Z e {1,2,3}, XŕY, Y ŕ Z, Z ŕ X, V ŕ X, V ŕ Y, V^Z je PC a přesto nemá řešení Hana Rudová, Omezující podmínky, 4. prosince 2018 74 Konzistence po cestě Na půli cesty od AC k PC Jak oslabit PC, aby algoritmus: 3 neměl paměťové nároky PC neměnil graf podmínek byl silnější než AC?I I Omezená konzistence po cestě - Restricted Path Consistency (RPC) 3 testujeme PC jen v případě, když je šance, že to povede k vyřazení hodnoty z domény proměnné Příklad: Vi,V2e {a,b},V3e {a,b,c},Vľ^ V2,V2 ± V3,Vi ± V3 je AC ale není PC RPC odstraní z domény V3 hodnoty a, b Hana Rudová, Omezující podmínky, 4. prosince 201 8 75 Konzistence po cestě Omezená konzistence po cestě (RPC) PC hrany se testuje pouze tehdy, pokud vyřazení dvojice může vést k vyřazení některého z prvků z domény příslušné proměnné & Jak to poznáme? Jedná se o jedinou vzájemnou podporu. Proměnná Vije omezeně konzistentní po cestě (Restricted Path Consistent, RPC): M každá hrana vedoucí z Vt je hranově konzistentní M pro každé a e Dt platí: je-li b jediná podpora a ve vrcholu j, potom v každém vrcholu k (spojeném s i a j) existuje hodnota c tak, že (a,c) a (b,c) jsou kompatibilní s příslušnými podmínkami Algoritmus: založen na AC-4 + seznam cest pro PC (viz Barták přednáška) Hana Rudová, Omezující podmínky, 4. prosince 2018 76 Konzistence po cestě Propagace pro nebinární omezení Nebinární omezení 3 Zobecnění principů NC, AC, a PC směrem ke k-konzistenci 3 zajímavé z pohledu složitosti řešení problémů pracuje se s libovolnými k-ticemi proměnných v praxi se vzhledem k paměťové a časové složitosti nevyužíval Obecné typy konzistence pro nebinární podmínky 3 pracuje se přímo s n-árními podmínkami M příklad: obecná hranová konzistence, konzistence mezil Globální omezení: specifické typy konzistencí 3 využívá se sémantika omezení, zaměřené opět na konkrétní omezení speciální typy konzistence pro globální omezení (př. al l_di sti nct)l Pro různé podmínky lze použít různý druh konzistence 3 A k-konzistence Silná k-konzistence => j-konzistence V j < k k-konzistence ^> silná k-konzistence I NC = silná 1-konzistence = 1-konzistence AC = (silná) 2-konzistence PC = (silná) 3-konzistence 3 Cvičení: uveďte příklad problému, který je 4-konzistentní, ale není 3-konzistentní Hana Rudová, Omezující podmínky, 4. prosince 2018 81 Propagace pro nebinární omezení Konzistence pro nalezení řešení 3 Máme-li graf s n vrcholy, jak silnou konzistenci potřebujeme, abychom přímo našli řešení? CSP vyřešíme bez navracení vzhledem k uspořádání proměnných (xi,... ,xn), jestliže pro každé i < n může být každé částečné řešení (xi,..., Xi) konzistentně rozšířeno o proměnnou Xi+i. I Nalezení řešení bez navracení pro libovolné uspořádání proměnných? I silná n-konzistence je nutná pro graf s n vrcholy ±> n-konzistence nestačí (viz předchozí příklad) silná k-konzistence pro k CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (xi,... ,xn), právě když je každá hrana (Xj,Xt) hranově konzistentní pro každé j < i. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC for i = n to 1 by -1 do for V j < i takové, že existuje hrana (xj,Xí) do revise ((j, í))) end DACl Příklad: X\ = X2, X\ = X3, X3 = X4 0white blue * black red x3 )white blue ©green white A black 1 = T\recl XI ) white black I M Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} 3 Po DAC: t)4={white,blue,black}, t)3={white,blue}, t)2={green,white,black}, Dl = {white}, I není AC, ale máme řešení bez navracení vzhledem k|xi, x2, x3, ^4)! Opakování revizí není nutné, doména revidované proměnné se v dalších cyklech nemění 3 Složitost 0(ek2) Hana Rudová, Omezující podmínky, 4. prosince 201 8 každá hrana se reviduje jednou se složitostí 0(k2) 85 Směrová konzistence Směrová í-konzistence Algoritmus pro DAC byl pouze pro binární CSP í-konzistence vyžaduje uvažování omezení s větším rozsahem proměnných musíme aktualizovat relace až nad (í - 1) proměnnými => uvažujeme obecné CSP (tedy i nebinární podmínky)l CSP je směrově í-konzistentní vzhledem k uspořádání proměnných (x\,...,xn) právě tehdy, když každých (í- 1) proměnných je í-konzistentní vzhledem ke všem proměnným, které je následují v uspořádání. CSP je silně směrově i-konzistentní (DIC-í) právě tehdy, když je směrově j-konzistentní pro každé j < i Hana Rudová, Omezující podmínky, 4. prosince 201 8 86 Směrová konzistence Vlastnosti DIC-i Opakování AC = silná 2-konzistence 3 PC = silná 3-konzistence DIC-2 je ekvivalentní DAC 3 u obou uvažujeme unární a binární omezení M DAC je definován pouze na binární CSP DIC-2 je sice definován pro obecné CSP, ale je pouze schopen k dané hodnotě proměnné hledat konzistentní hodnotu v doméně další proměnné, nezachytí tedy omezení s více než dvěmi proměnnými DIC-3 lze podobně srovnat se směrovou konzistencí po cestě (directed path consistency, DPC) 3 Algoritmus pro silnou směrovou konzistenci viz [Dechter, Constraint Processing] Hana Rudová, Omezující podmínky, 4. prosince 2018 87 Směrová konzistence Řešení bez navracení pomocí DIC-í 3 Opakování: CSP vyřešíme bez navracení vzhledem k uspořádání proměnných (xi,... ,xn), jestliže pro každé i < n může být každé částečné řešení (x\,..., X\) konzistentně rozšířeno o proměnnou Xí+i.I Proměnná musí být kompatibilní s již ohodnocenými proměnnými, tj. s tolika proměnnými, kolik má „zpětných" hran 3 Pro i zpětných hran potřebujeme směrovou (i + l)-konzistenci Je-li m maximum počtu zpětných hran pro všechny vrcholy, stačí nám silná směrovou (m + l)-konzistence 3 Při různém uspořádání vrcholů je počet zpětných hran různý => hledáme uspořádání vrcholů s nejmenším počtem zpětných hran m Hana Rudová, Omezující podmínky, 4. prosince 201 8 88 Směrová konzistence Šířka grafu Uspořádaný graf je graf s lineárním uspořádáním vrcholů. Šířka vrcholu v uspořádaném grafu je počet hran vedoucích z tohoto vrcholu do předchozích vrcholů. 3 Šířka uspořádaného grafu je maximum z šířek jeho vrcholů. Šířka grafu je minimum z šířek všech jeho uspořádaných grafů. 3 proceduře MinWidthOrdering((V,E)) (konstruujeme od konce) Q := {} (do vybraného uzlu povede nejméně zpětných hran) while V not empty do N := vyber a smaž uzel s nejmenšim počtem hran z (V,E) zařaď N do Q return Q Hana Rudová, Omezující podmínky, 4. prosince 2018 89 Směrová konzistence Graf podmínek s šířkou 1 = strom Tvrzení: Graf je strom právě tehdy, když má šířku 1 J Důkaz: 3 Předpoklad: Strom neobsahuje cyklus! <= Mějme graf šířky 1. Pokud by obsahoval cyklus, tak bychom pro libovolné uspořádání proměnných měli proměnnou se dvěma rodiči, tj. spor. I => Mějme graf bez cyklů. Pak lze vytvořit orientovaný strom s kořenem tak, že všechny hranVj směřují z kořenového uzlu. V tomto stromu má každý uzel nejvýše jednoho rodiče. Libovolné uspořádání, ve kterém rodič předchází potomky ve stromě, má šířku 1. 1 Hana Rudová, Omezující podmínky, 4. prosince 201 8 90 Směrová konzistence Konzistence pro stromové CSP Tvrzení: Nechť d = (x\,... ,xn) je uspořádání stromového grafu podmínek T pro daný CSP. Jestliže T je směrově hranově konzistentní vzhledem k d, pak má CSP řešení bez navracení vzhledem k dl M Důkaz: 3 Uvažujme uspořádání proměnných d = (x\,..., xn) s šířkou 1. 3 Předpokládejme, že X\,..., Xt jsou konzistentně nainstanciovány. «• Snažíme se nainstanciovat Xi+\\ d je uspořádaní šířky 1, tedy existuje pouze jeden rodič x j (j < í) proměnné xt+i, který může omezovat xt+i ± {Xj,Xi+i) je hranově konzistentní (z DAC), tedy a existuje hodnota konzistentní se současným přiřazením Xj ±> tuto hodnotu přiřadíme xt+i 10 Hana Rudová, Omezující podmínky, 4. prosince 201 8 91 Směrová konzistence Algoritmus zajištění DAC pro stromové CSP proceduře TreeSolving(T) nalezeni uspořádáni (xi,...,xn) s šířkou 1 pomoci stromu T (rodič předchází potomky) nechť Xp{i) označuje rodiče xt v uspořádaném stromu for i = n to 1 by -1 do ^ revise((Xp(i),Xí)) 2 r ^3 if DP(i) = 0 exit (řešeni neexistuje) end TreeSolvlng A. Složitost algoritmu 0(nk2) 3 Algoritmus zajistí DAC pro stromové CSP, tj. bude možné nalézt řešení bez navracení Pokud aplikujeme DAC vzhledem k uspořádání šířky 1, a pak v opačném směru, tak dosáhneme plné hranové konzistence. viz Barták, přednáška Hana Rudová, Omezující podmínky, 4. prosince 2018 92 Směrová konzistence Šířka grafu a stupeň konzistence Tvrzení: Nechť je dán CSP, jehož uspořádaný graf podmínek s uspořádáním d má šířku i - 1. Jestliže je problém silně směrově í-konzistentní, pak je problém řešitelný bez navracení vzhledem k d\ 3 Důkaz: M existuje uspořádaný graf s uspořádáním d a šířkou i - 1 M speciálně, počet zpětných hran pro každou proměnnou je maximálně i - 1 3 proměnné ohodnocujeme v pořadí uspořádání grafu nyní, pokud ohodnocujeme proměnnou: X musíme najít hodnotu kompatibilní se všemi již ohodnocenými proměnnými, které jsou s proměnnou spojené podmínkou (hranou) nechť takových proměnných je m, potom m < (í - 1) (<= graf má šířku (í - 1)) X* graf je směrově í-konzistentní, tedy taková hodnota musí existovat (<= z definice) 1 i ... j i maximálná w Hana Rudová, Omezující podmínky, 4. prosince 2018 93 Směrová konzistence Adaptivní konzistence 3 Původní intuice: proměnná musí být kompatibilní s již ohodnocenými proměnnými, tj. s tolika proměnnými, kolik má „zpětných" hran. 3 Je tedy nutná směrová í-konzistence odpovídající šířce grafu? Problém: algoritmy silné směrové í-konzistence pro i > 3 mění graf podmínek přidáváním hran, nutná úroveň i se může zvětšovatl 3 Algoritmus adaptivní konzistence ADC pro nalezení řešení bez navracení 3 uvažujme uspořádání proměnných d M rekurzivně vytváříme směrovou í-konzistenci (od poslední k první proměnné v d) M měníme úroveň í od uzlu k uzlu tak, abychom se adaptovali aktuální šířce uzlu v momentě zpracování Proč algoritmus funguje? M v momentě zpracování uzlu je určena finální šířka uzlu 3 víme tedy, jakou úroveň směrové í-konzistence musíme dosáhnout Hana Rudová, Omezující podmínky, 4. prosince 2018 94 Směrová konzistence Polynomiální CSP w šířka grafu, n počet proměnných, k horní mez velikosti domén Složitost DIC-í 0(nwl ■ (2k)1) důkaz viz Dechter, Constraint Processing Časová a prostorová složitost algoritmu adaptivní konzistence je 0(n ■ (2k)w+1) a 0(n ■ kw) důkaz viz Dechter, Constraint Processingl Věta: Třída CSP problémů, jejichž šířka grafu je ohraničena konstantou b je řešitelná v polynomiálním čase a prostoru.l Použitelnost algoritmu ADC 3 ADC není jen procedura pro rozhodnutí konzistence M ADC může sloužit i ke kompilaci ±> ADC transformuje problém na ekvivalentní graf, ze kterého může být každé řešení odvozeno v lineárním čase M prostorová složitost ale zůstává Hana Rudová, Omezující podmínky, 4. prosince 2018 95 Směrová konzistence Pojmy a značení Rozsah omezení scope(c) množina proměnných, na kterých je c definováno příklad: A,B,C e {0,1,2} scope(A < B) = {A,B}i I k-tice t hodnot patřících do c: t e c M příklad (pokračování): (0,1) e (A < B)i Proměnná x e scope(c), k-tice tec t[x] je hodnota proměnné x v t M příklad (pokračování): (0,1) [A] = 0 Hana Rudová, Omezující podmínky, 4. prosince 201 8 96 Směrová konzistence Definice obecné hranové konzistence (GAC) Generalized arc consistency (někdy nazývána doménová konzistence) 3 pro každou proměnnou z podmínky a každou její hodnotu existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí A + B = C, A g {1,2, 3}, B g {2, 3,4}, C g {3,..., 7} je obecně hranově konzistentní Omezení c je obecně hranově konzistentní, jestliže má každá hodnota a každé proměnné x e scope(c) doménovou podporu v c Hodnota a proměnné x e scope(c) má doménovou podporu ívc, jestliže I t g c a platí a = t[x] M pro každé y e scope(c) platí t[y] e Dy M Příklad: A g {0,1}, Bg {0,1}, C g {1, 2}, A = B+C, 0 u A nemá podporu, 1 u A Iná podporu (1,0,1) I 3 CSP je obecně hranově konzistentní <=> všechna jeho omezení jsou obecně hranově konzistentní 3 Příklad (pokračování): po GAC dostaneme ^=1, B=0, C=l Hana Rudová, Omezující podmínky, 4. prosince 2018 97 Směrová konzistence Konzistence mezí 3 Bounds consistency BC: slabší než obecná hranová konzistence 3 propagace pouze při změně minimální nebo maximální hodnoty v doméně proměnné tedy došlo ke změně mezí domény proměnnél M Konzistence mezí pro nerovnice M A > B => min(A) > min(B)+l, max(B) < max(A)-l 3 příklad: A g {4,..., 10}, Be {6,... 18}, A > B min(A) > 6+1 => A e {7,..., 10} max(B) < 10-1 => B e{6,...,9}l Cvičer napište pravidla pro konzistenci mezí pro uvedená omezení ^AB, A min(A) > min(B)+min(C), max(A) < max(B)+max(C) min(B) > mi n(A)-max(C), max(B) < max(A)-min(C) min(C) > min(A)-max(B), max(C) < max(A)-min(B)l M změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) změna max(A)vyvolá pouze změnu max(B) amax(C), ...I Příklad: A g {1,..., 6,9,10}, B g {1,..., 10}, A = B + 2 1 A = B + 2 => min(A)>l+2, max(A)<10+2 => A g {3,..., 6,9,10} => min(B)>l-2, max(B)<10-2 => B g{1,...,8}I tj. doména B má pouze změněny meze a hodnoty 5, 6 zůstanou v doméně A g {3,..., 6, 9,10}, B g {1,..., 8}, A = B + 2 je BC, není GAC, není ACl Cvičení: napište pravidla pro konzistenci mezí pro uvedená omezení A = B - 3, A = B-C, A=B + C, A všechna jeho omezení mají konzistentní meze Hana Rudová, Omezující podmínky, 4. prosince 2018 100 Směrová konzistence Globální podmínky Globální podmínka: definována pro libovolný konečný počet proměnných Global Constraint Catalog http://www.emn.fr/x-info/sdemasse/gccat Nicolas Beldiceanu, Mats Carlsson and Jean-Xavier Rampon 3 Popis omezení dostupných v literatuře a v systémech s omezujícími podmínkami „The catalog presents a list of 423 global constraints issued from the literature in constraint programming and from popular constraint systems. The semantic of each constraint is given together with some typical usage and filtering algorithms, and with reformulations in terms of graph properties, automata, and/or logical formulae. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms." PDF dokument, srpen 2014, cca 4 000 stran Hana Rudová, Omezující podmínky, 4. prosince 2018 101 Směrová konzistence (Globální podmínky a) rozvrhování Všechny proměnné různé M all Different 3 Disjunktivní zdroj/rozvrhování M dvar interval, dvar sequence «• noOverlap 3 Kumulativní zdroj/rozvrhování M cumuFunction, pulse Alternativní zdroje * alternative Hana Rudová, Omezující podmínky, 4. prosince 201 8 102 Směrová konzistence Všechny proměnné různé Proměnné v poli Array jsou různé M dvar int Array[Interval]; M globální podmínka: al 1 Different(Array) ; M binární podmínky: for (i, j in Interval : i ! = 3 allDifferent vs. binární podmínky M allDifferent má úplnou propagaci binární podmínky mají slabší (neúplnou) propagaci Příklad: učitelé musí učit v různé hodiny I M globální podmínka: Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr e{3,4}, Eva e {3,4} I M binární podmínky: Jan e{3,...,6}, Petr e{3,4}, Annae {2,..., 5}, Ota g {2,3,4}, Eva e{3,4}, Marie e{l,...,6} Hana Rudová, Omezující podmínky, 4. prosince 201 8 103 j) Array[i] != ArrayEj] ;l I učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Směrová konzistence Naivní propagace pro all Different U = {Petr, Ota, Eva}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro Jan, Anna, Mariel Jan g {5,6}, Anna = 5, Marie e {1,5,6} Konzistence: musí platit: V{Xi,.. .,Xk} c V : card{Di u ■ ■ ■ u Dk} > k 3 Inferenční pravidlo 3 V: množina všech proměnných 3 U = {Xi,...,Xk}, dom(U) = {Di u ■ ■ ■ u Dk} M card(U) = card(dom(U)) ^Vvg dom(U), VX g (V - U),X + v 3 hodnoty v dom(U) jsou pro ostatní proměnné nedostupné Složitost hledání všech podmnožin množiny n proměnných (naivní) 0(2n) Hana Rudová, Omezující podmínky, 4. prosince 2018 104 Směrová konzistence učitel min max Jan 3 6 Petr Anna 2 5 Ota 4 Eva Marie 1 6 I Párování v bipartitních grafech Efektivní propagaci pro allDifferent lze založit na párování v bipartitních grafech (Regin 94) 3 Bipartitní graf uzly grafu rozdělené do dvou množin 3 neexistují hrany mezi uzly jedné množiny Párování v bipartitních grafech M v grafu neexistují dvě hrany, které by měly společný vrchol Maximální párování párování, které má maximální počet hraní M CSP jako bipartitní graf M jedna množina vrcholů reprezentuje proměnné druhá množina vrcholů reprezentuje hodnoty proměnných 3 hrana z proměnné X do hodnoty a říká, že proměnná X může nabývat hodnoty al Hana Rudová, Omezující podmínky, 4. prosince 2018 105 Směrová konzistence all Different - párování v bipartitních grafech II Inicializace sjednocení domén proměnné proměnných 3 vypočti maximální párování M odstraň všechny hrany, které nepatří do žádného maximálního párováníl Propagace zmenšené domény odstraň odpovídající hrany 3 vypočti nové maximální párování M odstraň všechny hrany, které nepatří do žádného maximálního párováníl Algoritmus založen na doménové konzistenci 3 každé maximální párování definuje doménovou podporu M složitost 0(n2k2), n... počet proměnných, k... maximální velikost doményl 3 efektivnější algoritmus využívá konzistenci mezí - složitost O(nlogn) (Puget 1 998) Hana Rudová, Omezující podmínky, 4. prosince 2018 106 Směrová konzistence Intervalové proměnné Intervalová proměnná: pro modelování časového intervalu (úlohy, aktivity) 3 hodnotou intervalové proměnné je celočíselný interval [start, end) * příklad: dvar interval x in 0..1000000 size 100..200; 0 [100,200] 1000000 [.........i i '......] I— —I Time Volitelná intervalová proměnná: pro modelování časového intervalu, který může ale nemusí být přítomen v řešení (přítomný vs. nepřítomný interval) např. pro modelování volitelných aktivit, které v řešení nemusí být příklad: dvar interval x optional in 0..1000000 size in 100..200; Dom(x) c {_l} u {[start, end)\start, end e Z,start < end} ± značí, že interval není přítomen v řešení Hana Rudová, Omezující podmínky, 4. prosince 2018 107 Směrová konzistence Disjunktní/unární rozvrhování Sekvenční proměnná p definována na množině intervalových proměnných x dvar interval x[i in l..n] dvar sequence p in x; M hodnota intervalové proměnné p je permutace přítomných intervalů pozor, permutace t ještě neimplikuje žádné uspořádání v časell I Omezení noOverlap(p) vyjadřuje, že sekvenční proměnná p reprezentuje řetězec nepřekrývajících se intervalových proměnných pro vyjádření rozvrhování na unárním/disjunktivním zdroji, kde se intervaly/úlohy/aktivity nepřekrývají 3 poznámka: nepřítomné intervaly v řetězci zahrnuty nejsou Hana Rudová, Omezující podmínky, 4. prosince 2018 108 Směrová konzistence Disjunktivní rozvrhování: princip algoritmu Hledání hran (edge finding) - Baptisté & Le Pape, 1 996 Hledáme úlohu, která předchází nebo následuje množinu jiných úloh dvar interval A in 4..16 size 2; dvar interval B in 6..16 size 4; dvar interval C in 7..15 size 5; Co se stane, pokud nebude aktivita A zpracována jako první? 16 A( I B(4) 16 C(5) 15 Pro A,B,C není dost času, a tedy aktivita A musí být první 4h A(2) "I 7 6h B(4) 16 Hana Rudová, Omezující podmínky, 4. prosince 201 8 C(5) 109 15 Směrová konzistence Další podmínky: precedence Mezi intervalovými proměnnými můžeme definovat precedenční podmínky: dvar i nterval i; dvar i nterval j ; endBeforeStart(i , j); endBeforeEnd(i, j); endAtStart(i, j) ; endAtEnd(i, j) ; startBeforeStart(i, j); startBeforeEnd(i, j); startAtStart(i, j); startAtEnd(i , j) ; Poznámka: tyto podmínky platí, pokud jsou oba intervaly přítomné Hana Rudová, Omezující podmínky, 4. prosince 201 8 110 Směrová konzistence A dále: logické podmínky Unární podmínka pro přítomnost intervalu x: presenceOf(x) znamená, že x =/= ± Příklady: presenceOf(x) == presenceOf(y) // x přítomen právě tehdy, když je přítomen y | presenceOf(x) => presenceOf(y) // implikace presenceOf(x) => !presenceOf(y) Pozor na použití: precedenční podmínky: polynomiální složitost 3 logické binární podmínky: polynomiální složitost precedence + logické binární: NP-těžké! Hana Rudová, Omezující podmínky, 4. prosince 201 8 Směrová konzistence Výrazy s intervalovými proměnnými Pro vytváření účelových funkcí nebo definici omezení startOf(x) endOf(x) sizeOf(x, V) Příklad: minimalizace času dokončení poslední úlohy (tzv. makespanu) minimize max(i in l..n) endOf(x[i]) Hana Rudová, Omezující podmínky, 4. prosince 201 8 112 Směrová konzistence Příklad: rozvrhování problému job-shop Job-shop problém: problém rozvrhování úloh, které se skládají z nepřekrývajících operací každá operace úlohy prováděna na jiném stroji pořadí operací úlohy předem určeno op11 -► op12 —>- op13 op21 op22 op23 unarm stroje op31 op32 op33 op41 op42 op43 1 2 3 4 5 6 7 8 9 10 11 [] M1 [] M2 □ M3| I dvar interval op[j in Jobs] [p in Pos] size Ops [j] [p] .pt; dvar sequence mchs[m in Mens] in all(j in Jobs, p in Pos: Ops [j] [p] .meh == m) op[j][p]; minimize max(j in Jobs) endOf(op[j] [nbPos]); subject to { tuple Oper { forali(m in Mchs) int mch; // Machine noOverlap(mchs [m] ) ; ■ „_._// n n i -i / • • -r -i . 0 n int pt; // Processing time forallCj in Jobs, p in 2..nbPos) j. ^ endBeforeStart(op[j] [p-1] ,op[j] [p] ) ; 0per 0'ps[j in Jobs] [m in Mchs] = př. 0ps[l] [2]=<3,6> Hana Rudová, Omezující podmínky, 4. prosince 2018 113 Směrová konzistence Kumulativní funkce Hodnota výrazu kumulativní funkce reprezentuje vývoj kvantity v čase, která může být inkrementálně změněna (snížena nebo navýšena) intervalovými proměnnými. Příklady: intervaly využívají počty pracovníků M intervaly využívají skladové zásoby Intervalové proměnné x [i] přispívají do kumul. funkce po dobu svého provádění pulse(xř 1) int wor[l..5] = [1,3,2,4,1]; I cumul Function y = sum(i in 1..5) pul se(x[i ] , wor [i ]) ; Omezení na výrazech kumulativní funkce int h = ... dvar int h = ... cumulFunction f= ... cumulFunction f= ... f<=h f<=h Hana Rudová, Omezující podmínky, 4. prosince 201 8 114 1 0 x Time i Směrová konzistence Příklad: RCPSP Resource-contrained project scheduling problem (RCPSP) 1 dvar interval a[i in Tasks] size i.pt; 2 cumulFunction usage[r in Resources] = 3 sum(i in Tasks: i.qty[r]>0) pulse(a[i],i.qty[r]); 4 minimize max(i in Tasks) endOf(a[i]); 5 subject to { 6 forali(r in Resources) 7 usage[r] <= Capacity[r]; 8 forali(i in Tasks, j in i.succs) 9 endBeforeStart(a[i], a[]); 10 } odkazuje jako klíč na celý tuple Hana Rudová, Omezující podmínky, 4. prosince 201 8 Směrová konzistence Alternativní podmínka Pokud je interval x přítomný, pak je právě jeden z intervalů yl, . . . ,yn přítomný a je synchronizován s x (má stejný start a konec) & alternative(x, [yl,...,yn]) Pokud je x nepřítomné, pak jsou yi také nepřítomnél Rozšíření: právě k intervalů z yl, . . . ,yn je synchronizováno s x & alternative(x, [yl,...,yn], k) //k: celočíselný vyrazí Příklad použití: -0 každá intervalová proměnná x[t] vyžaduje nbWorkers[t] přítomných intervalů mezi assigned[t] [w] pro pracovníky w M dvar interval x[t in Tasks] size pt[u]; int nbWorkers[t in Tasks]; dvar interval assigned[Tasks][Workers] optional; forall (t in Tasks) alternative(x[t], all (w in Workers) assigned[t][w], nbWorkers[t]); Hana Rudová, Omezující podmínky, 4. prosince 2018 116 Směrová konzistence Konzistenční algoritmus pro nebinární podmínky Obecný konzistenční algoritmus Varianta AC-3 s frontou proměnných rozšíření AC-2001 na nebinární podmínky M Opakovaně se provádí revize podmínek, dokud se mění domény procedure Nonbinary-AC-3-with-Variables(Q) while Q non empty do vyber a smaž V j e Q for V C takové, že V j e scope(C) do W : = revise (V/, C) // W je množina proměnných jejichž, doména se změnila if 3 Vi e W taková, že Di = 0 then return fail Q := Q u {W} end Nonbinary-AC-3-with-Variables Hana Rudová, Omezující podmínky, 4. prosince 2018 117 Směrová konzistence Revizní procedura: různé typy konzistence Speciální revise procedury jsou definovány v závislosti na typu omezení, tj. revise procedura může implementovat obecnou hranovou konzistenci konzistenci mezí M konzistenční algoritmy pro globální podmínky jako allDifferent Hana Rudová, Omezující podmínky, 4. prosince 201 8 118 Směrová konzistence Revizní procedura 3 Uživatel má často možnost definovat vlastní revise proceduru Je potřeba určit událost, která revizi vyvolá událostí je změna domény proměnné (suspension) M vyvolání revize pouze při dané změně proměnné & při libovolné změně domény (u obecné hranové konzistence) M při změně mezí (u konzistence mezí) ±> při instanciaci proměnné M tj. pro každou proměnnou lze použít různé události 3 revize jednolivých podmínek jsou realizovány v závislosti na aktivaci odpovídající události (událostmi řízený výpočet)! Je potřeba navrhnout propagaci přes podmínku pro danou událost M výsledkem propagace je zmenšení domén proměnných M pro jednu podmínku lze mít více propagačních kódů Hana Rudová, Omezující podmínky, 4. prosince 2018 119 Směrová konzistence Základní konzistenční algoritmus s událostmi -0 procedure Nonbinary-AC-3-with-Events(Q) while Q non empty do vyber a smaž event(Vj) e Q for V C takové, že V) e scope(C) a C čeká na event(Vj) do W : = revi se (event (V)), C) // jsou vyvolány pouze ty revize, které čekaji na danou event(Vj) // W je množina proměnných jejichž, doména se změnila if 3 Vi g W taková, že Dt = 0 then return fail Q := Q u {W} end Nonbinary-AC-3-with-Events Hana Rudová, Omezující podmínky, 4. prosince 201 8 120 Směrová konzistence Prohledávání a pohled dopředu Přehled prohledávacích algoritmů pro CSP Rozšiřování částečného konzistentního přiřazení stromové prohledávání J* backtracking ±> pohled dopředu (propagace omezení) ±> pohled zpět (inteligentní vracení) * neúplná stromová prohledáváni Procházení úplných nekonzistentních přiřazení generuj a testuj lokální prohledávání 3 Kombinování úplných nekonzistentních přiřazení 3 population-based search Hana Rudová, Omezující podmínky, 4. prosince 201 8 122 Prohledávání a pohled dopředu Prohledávací algoritmy pro CSP Prohledávací algoritmy prochází (traversálně) graf stavového prostoru uzly grafu (stavy): konzistentní částečné instanciace iniciální stav: prázdné přiřazení hrany grafu: operátory, které rozšíří částečné řešení [x\/ai,...,Xj/aj] o přiřazení jedné proměnné, které není v konfliktu s dřívějšími přiřazeními, tj vznikne [xi/ai,... ,Xj/aj,Xj+i/aj+i] cílové stavy: úplná řešení I Hana Rudová, Omezující podmínky, 4. prosince 201 8 červené čtverečky: chybný pokus o instanciaci, řešení neexistuje nevyplněná kolečka: nalezeno řešení (cílové stavy) černá kolečka: vnitřní uzel, máme pouze částečné přiřazení Prohledávání a pohled dopředu Prohledávací algoritmy pro CSP: vlastnosti Bod volby: z uzlu grafu vede více hran máme na výběr, kterou hodnotu přiřadíme proměnné CSP má řešení bez navracení vzhledem k uspořádání d, jestliže všechny listy v jeho grafu stavového prostoru reprezentují řešení. 3 v grafu nejsou žádné slepé větve I Hana Rudová, Omezující podmínky, 4. prosince 201 8 124 Prohledávání a pohled dopředu Backtracking (BT) Prohledávání stavového prostoru do hloubky Dvě fáze backtrackingu 3 dopředná fáze: proměnné jsou postupně vybírány, rozšiřuje se částečné řešení přiřazením konzistentní hodnoty (pokud existuje) pro další proměnnou zpětná fáze: pokud neexistuje konzistentní hodnota pro aktuální proměnnou algoritmus se vrací k předchozí přiřazené hodnotěl Proměnné dělíme na minulé - proměnné, které už byly vybrány (a mají přiřazenu hodnotu) M aktuální - proměnná, která je právě vybrána a je jí přiřazována hodnota M budoucí - proměnné, které budou vybrány v budoucnosti Hana Rudová, Omezující podmínky, 4. prosince 201 8 125 Prohledávání a pohled dopředu Příklad: backtracking Hana Rudová, Omezující podmínky, 4. prosince 201 8 126 Prohledávání a pohled dopředu Algoritmus backtrackingu procedure Backtracking((X,D,C)) í : = 1 (inicializace čitače proměnných) D\ := Di (kopirováni domény) whi 1 e 1 < í < n přiřazeni xt : = Select-Value if Xi is null (žádná hodnota nebyla vrácena) i := i-1 (zpětná fáze) else i := í + 1 (dopředná fáze) I D[ := Di if í = 0 return , ,nekonzistentni ' ' else return přiřazené hodnoty {x\,...,xn} end Backtracking 3 Algoritmus vrací pouze první řešení Série domén V i: D[ c Di. Select-Value pracuje nad (promazává) D[ Hodnoty v D\ ještě netestovány vzhledem k aktuálnímu částečnému přiřazení Hana Rudová, Omezující podmínky, 4. prosince 201 8 127 Prohledávání a pohled dopředu Uspořádání hodnot pro backtracking 3 procedure Select-Value while D[ is not empty vyber a smaž libovolný ae D[ if Consistent(aí-i,Xí = a) return a return null I Backtracking ověřuje v každém kroku konzistenci podmínek vedoucích z minulých proměnných do aktuální proměnné Backtracking tedy zajišťuje konzistenci podmínek na všech minulých proměnných na podmínkách mezi minulými proměnnými a aktuální proměnnou Hana Rudová, Omezující podmínky, 4. prosince 201 8 128 Prohledávání a pohled dopředu Problémy a vylepšení backtrackingu Thrashing: opakované objevování stejných nekonzistencí a částečných úspěchů při prohledávání! M Algoritmy pohledu dopředu kontrolují podmínky dopředu 3 backtracking odhalí nesplnění podmínky teprve když přiřadí hodnoty jejím proměnným příklad: A,B,C,D,E in 1..10, A=3*E konzistenčními algoritmy lze předem upravit domény A a El Backjumping se vrací k původci chyby příklad: A,B,C,D,E in 1..10, A>E backtracking vyzkouší všechny možnosti pro B, C, D než odhalí A^l hned po prvním neúspěšném přiřazení E se lze vrátit k přiřazování Al M Dynamický backtracking: změna uspořádání minulých proměnných Neúplná prohledávání: hledání pouze v některých částech stavového prostoru Hana Rudová, Omezující podmínky, 4. prosince 201 8 129 Prohledávání a pohled dopředu Algoritmy pohledu dopředu {look-ahead) LA Používají propagace omezení 3 Vyvolány před přiřazováním hodnoty další proměnné Snaží se zjistit, jak rozhodnutí o výběru proměnných a hodnot ovlivní budoucí prohledávání! 3 Po provedení propagace omezení lze mnohem lépe rozhodnout, kterou proměnnou přiřadit I ±> většinou lepší přiřadit proměnné, které nejvíce omezují zbytek stavového prostoru příklad: A, B,C,D,E in 1..10, D=A*B*C*E, E>5, lépe je začít s El M rozhodnout, kterou hodnotu přiřadit proměnné snaha o výběr hodnoty, která umožní nejvíce voleb v budoucích přiřazeních X příklad: A,B,C in 1..10, A*B<10, B=C*2, pro A je lepší vybrat ll Vylepšení složitosti nejhoršího případu oproti naivnímu backtrackingu zřídka. Cílem je snaha o efektivní využití algoritmů propagace omezení. Hana Rudová, Omezující podmínky, 4. prosince 2018 130 Prohledávání a pohled dopředu Pohled dopředu pro výběr hodnoty proceduře Look-Ahead((X, D, C)) rozdíly od backtrackingu i : = 1 (inicializace čitače proměnných) D[ := Di pro 1 < i < n (kopirováni domény) whi 1 e 1 < i < n přiřazeni xt : = Select-Value-XXX i f Xi i s null (žádná hodnota nebyla vrácena) i := i-1 (zpětná fáze) nastav všechny Drk, k > i na jejich hodnotu před poslední instanciací Xi I else i := í + 1 (dopředná fáze) i f í = 0 return , , nekonzi stentni ' ' else return přiřazené hodnoty {x\,... ,xn} end Look-Ahead Sel ect-Val ue-XXX se liší dle typu LA algoritmu Ukládáno n kopií každé D' M pro každou úroveň ve stavovém prostoru jedna kopie Hana Rudová, Omezující podmínky, 4. prosince 2018 131 Prohledávání a pohled dopředu Kontrola dopředu (forward checking) FC & procedure Select-Value-Forward-Checking while D[ is not empty vyber a smaž libovolný a e D[ for V k, í < k < n for y b G Dk if not Consistent(ai_i,Xi = a,Xfc = Z?) smaž b z DFk if 3k,í< kV2, c2 : V2 = 3 x V3 Stavový prostor: V 1 d = V, > fail c1 => Y2=1 d c2 => fail c2 > V2=1..2 > fail 4 d c2 i :> V2=1..3 :> V2=3 V3=1 V' 1 Hana Rudová, Omezující podmínky, 4. prosince 201 8 135 Prohledávání a pohled dopředu Prohledávání s iniciální konzistencí Prohledávací algoritmus často aplikován až po zajištění iniciální konzistence typicky: iniciální konzistence a pak kontrola dopředu nebo iniciální konzistence a pak pohled dopředu Příklad: pohled dopředu + iniciální konzistence Vi,V2lV3 in 1...4 cl:Vi>V2, c2:V2 = 3xV3 V- y 2 3< d => V1 in 2..4 V2in 1..3 c2 => V2=3 V3= 1 d => V1= 4 I V3 1 ó Hana Rudová, Omezující podmínky, 4. prosince 201 8 136 Prohledávání a pohled dopředu Srovnání algoritmů proměnné aktuálni I Backtracking (BT) kontroluje v kroku a podmínky c(Vi,VJ,...,c(Va_i,VJ z minulých proměnných do aktuální proměnnél Kontrola dopředu (FC) kontroluje v kroku a podmínky C(Va+l, Va),...,C(Vn, Va) z budoucích proměnných do aktuální proměnnél Pohled dopředu (LA) kontroluje v kroku a podmínky ^ / Vi(a < l < n), Vfc(a í na jejich hodnotu před posledni instanciaci x\ else if i < n s :=mini pro každou hodnotu vi e xi nalezneme proměnnou s nejmenším indexem, která je s xJmx v konfliktu i- konfliktní proměnná je ta z nich, která má největší index (když její hodnotu změníme, můžeme zrušit konflikt s odpovídající hodnotou) v1 v2 (přiřazení této proměnné musíme určitě změnit, aby šla hodnota vi použít) I Hana Rudová, Omezující podmínky, 4. prosince 201 8 151 Pohled zpět při prohledávání Algoritmus GBJ Každá proměnná Xt uchovává v latestt index konfliktní proměnné procedúre GBJ ((X,D, C)) rozdíly od backtrackingu í : = 1 (inicializace čitače proměnných) D[ := Di (kopirováni domény) latestj := 0 (inicializace čitače na konfliktni proměnnou whi 1 e 1 < í < n přiřazeni xi := Select-Value-GBJ i f xt i s null (žádná hodnota nebyla vrácena) í := latestj (skok zpět) else í := í + 1 (dopředná fáze) D[ := Di latestj := 0 i f í = 0 return , , nekonzi stentni ' ' else return přiřazené hodnoty {x\,...,xn} end GBJ Hana Rudová, Omezující podmínky, 4. prosince 2018 1 52 Pohled zpět při prohledávání GBJ: výběr hodnoty procedure Select-Value-GBJ while D[ is not empty vyber a smaž libovolný v e D[ v1 TT v2 consistent := true k : = 1 while k < í a consistent \i i f k > latestj latestj := k if not Consistent(Vfc,X{ = v) consistent := false else k := k+1 if consistent return v return null (v doméne Xt neexistuje konzistentní' hodnota) Hana Rudová, Omezující podmínky, 4. prosince 2018 1 53 Pohled zpět při prohledávání GBJ: příklad M vyznačené přiřazení zároveň říká, že předchozí hodnoty už jsme vyzkoušeli (a vyřadili) M X7 = red vyřadí x\ (tj. Iatest7 = 1), X7 = biu e vyřadí X3 => celkem latest7 = 3 M vracíme se ke konfliktní proměnné X3, ta už má ale prázdnou doménu M latestj = 2, vracíme se tedy k X2 3 X3=red dala latestj na 1, X3=blue dala latestj na 2 M lépe (až k x\) se ale vrátit neumíme, GBJ se v tomto okamžiku vrací k předchozí proměnné Hana Rudová, Omezující podmínky, 4. prosince 2018 1 54 Pohled zpět při prohledávání Konflikty řízený skok zpět Conflict-directed backjumping CBJ Při skoku zpět na proměnnou Xj z listu slepé větve nemusíme nalézt v doméně Xj žádné hodnoty pro přiřazení. a/_i se pak nazývá vnitřní slepá větev.l CBJ skáče zpět v listu slepé větve i ve vnitřní slepé větvi M udržujeme Jí množinu skoků zpět pro každou proměnnou pomocí nesplněných omezení proměnná Xj(j < i) je bližší k xi než Xk(k < í), jestliže j > k, naopak Xk je vzdálenější omezení R je vzdálenější než omezení S, jestliže je nejbližší proměnná v rozsahu R vzdálenější než nejbližší proměnná v rozsahu S (pokud totožné proměnné, rozhodují další proměnné). Pro uspořádání (x\,X2, ■ ■ ■)'■ S rozsah R\\ (x3,Xs,Xj), rozsah S\\ (x2,XQ,Xs,Xg) R\ je vzdálenější než S\ od Xiol rozsah R2: (x3,Xs,Xs,Xg), rozsah 5*2: (x2,XQ,Xs,Xg) R2 je vzdálenější než 5*2 od Xiol M mezi nesplněnými omezeními vybereme to nejvzdálenější (ostatní omezení neumožní nejdelší možný skok zpět) 3 skočíme zpět na nejbližší proměnnou v tomto omezení (je bezpečné změnit proměnnou, která byla nejpozději přiřazená) Hana Rudová, Omezující podmínky, 4. prosince 2018 1 55 Pohled zpět při prohledávání CBJ: výběr hodnoty proceduře Select-Value-CBJ while D[ is not empty vyber a smaž libovolný v e D[ consistent := true k := 1 while k < í a consistent if Consistent(Vfc,X{ = v) ' k : = k + 1 else R := nejvzdálenější nesplněné omezení přidej proměnné v rozsahu R vyjma Xj do Ji consistent := false if consistent return v return null (v doméně Xt neexistuje konzistentní' hodnota) Hana Rudová, Omezující podmínky, 4. prosince 2018 1 56 Pohled zpět při prohledávání Algoritmus CBJ proceduře CBJ((X,D,C)) í := 1 Jí := 0 whi 1 e 1 < í < n přiřazeni xt : = Select-Value-CBJ i f Xt i s null íp := í í := index poslední proměnné v Jt Jt ■= Jí u Jip - {xt} rozdíly od backtrackingu (inicializace čitače proměnných) (kopirováni domény) (inicializace množiny skoků zpět) (žádná hodnota nebyla vrácena) (skok zpět) (spoj množiny skoku zpět) (takto upravená Ji se použije ve vnitřni slepé větvi) else i := í + 1 (dopředná fáze) D[ := Dt Jí:=0 # if í = 0 return , ,nekonzistentni ' ' else return přiřazené hodnoty {x\, end CBJ l Hana Rudová, Omezující podmínky, 4. prosince 201 8 Pohled zpět při prohledávání CBJ: příklad před vstupem do Select-Value-CBJ pro proměnnou Xy je Jy = 0 M X3 =/: Xy je nejvzdálenější omezení, které vyřadilo x 7 = red, tedy// = {X3} X\± Xy je nejvzdálenější omezení, které vyřadilo Xy =blue, tedy Jy = {x\, X3} M skáčeme zpět na poslední proměnnou v Jy, tedy na X3 do Í3, která byla zatím prázdná, přidáme X\ M doména X3 je prázdná, v J3 je jediná proměnná X\ a na tu se vracíme Hana Rudová, Omezující podmínky, 4. prosince 2018 1 58 Pohled zpět při prohledávání Algoritmy učení Množiny skoků zpět jsou chybná prirazení vypočítaná během prohledávání Tato chybná prirazení se mohou vyskytovat i později v jiných cestách stromu prohledávání a jsou znovu počítána 3 Přidáme chybná prirazení jako nová omezení při detekci slepé větve nemá cenu uchovávat celou slepou větev ät v proměnné Xí+i na toto přiřazení už později nenarazíme M uchováme chybná přiřazení na podmnožině proměnných {x\,...,xt\ Prořezávání stavového prostoru 3 čím menší chybná přiřazení se podaří uchovat, tím rychlejší bude prohledávání Zvětšování množiny omezení cena za prořezávání stavového prostoru nesmí přerůst cenu za zvětšování množiny omezení Hana Rudová, Omezující podmínky, 4. prosince 2018 1 59 Pohled zpět při prohledávání Učení skoku zpět (jumpback learning) M Využijeme chybná prirazení, která jsme se naučili v CBJ Algoritmus učení skoku zpět = CBJ + přidávání nových omezení Po dosažení listu slepé větve äi-i přidáme omezení zakazující äí-i[Jí] x3 po dosažení listu slepé větve v xq je Jq = {x2,X4,Xs} <= red vyřadila xq ± Xs, blue vyřadila xq ± x2, green vyřadila xq ± xj dsíJe] tedy zakazuje přiřazení [(X2,blue>, (X4,green), (xs,red)] M později při procházení stromu lze např. ze znalosti x2 =blue, X4 =green odvodit x 5 ^red Hana Rudová, Omezující podmínky, 4. prosince 2018 160 Pohled zpět při prohledávání Další rozšíření backtrackingu Problémy skoku zpět Při skoku zpět zapomínáme už udělanou práci Příklad: Obarvěte graf třemi barvami tak, že mají sousední vrcholy různou barvu (uvedené hodnoty barev jsme už vyzkoušeli) Vrchol Barva A 1 II B 2 ■2 11 C 1 2 ll 1 D 12 3. ■=> skok na B 1 21 E 12 3 1» zpět na D 1 1 2 3.1 Při druhém ohodnocení C děláme zbytečnou práci, stačilo nechat původní hodnotu 2, změnou B se nic neporušilo I Hana Rudová, Omezující podmínky, 4. prosince 201 8 162 Další rozšíření backtrackingu Dynamický backtracking: příklad Stejný graf (A,B,C,D,E), stejné barvy (1,2,3), ale jiný postup Skok zpět + pamatování si důvodu konfliktu + přenos důvodu konfliktu + změna pořadí proměnných = dynamický backtracking I Vrchol 1 2 3 Vrchol 1 2 3 Vrchol 1 2 31 A 0 0 0 1 B 0 1 0 t A ol vybraná barva: o C A 0 t A 0 1 0 Al důvod konfliktu: AB D A B 0 D A B AB D A 0 1 E A B D t A B t A D ol skok zpět (na D) I skok zpět (na B)l + přenos důvodu chyby (AB) í- přenos důvodu chyby (A) + změna pořadí (B,C)I M Vrchol C, resp. celý graf, který na něm případně visel není nutno přebarvovat Hana Rudová, Omezující podmínky, 4. prosince 2018 163 Další rozšíření backtrackingu Dynamický backtracking: algoritmus procedure DB(Variables, Constraints) Labelled := 0; Unlabelled := Variables while Unlabelled <> 0 do vyber X z Unlabelled ValuesX := DX - hodnoty nekonzistentní s Labelled použitím Constraints if ValuesX = 0 then nechť E je vysvětlení konfliktu (množina konfliktních proměnných) if E = 0 then failure else nechť Y je nejbližší proměnná v E zruš přiřazení Y (z Labelled) s vysvětlením E-Y smaž všechna vysvětlení zahrnujícící Yl else vyber V z ValuesX Unlabelled := Unlabelled -{X} Labelled := Labelled u {X/V} return Labelledl Nevýhody algoritmu: přeuspořádáváním proměnných Hana Rudová, Omezující podmínky, 4. prosince 201 8 rušíme efekt heuristik výběru proměnných 164 Další rozšíření backtrackingu Redundance backtrackingu Redundantní práce: opakování výpočtu, jehož výsledek už máme k dispozici Změna B neovlivňuje hodnotu C => není potřeba znova procházet podstromy C=l,... ,C=9l M Backmarking pamatuje si, kde testy na konzistenci neuspěly eliminuje opakování dříve provedených konzistenčních testů Hana Rudová, Omezující podmínky, 4. prosince 2018 165 Další rozšíření backtrackingu Základy backmarkingu Mark(Y,£0: u každé hodnoty b z domény Y pamatuje nejvzdálenější konflikt konflikt = proměnná xp taková, že ap je v konfliktu s Y = b p BackTo(Y): u každé proměnné Y pamatuje nejvzdálenější návrat * návrat = proměnná, jejíž hodnota se změnila od poslední instanciace YÍ Mark BackTo X I Y=b Mark(Y,b) BackTo(Y) BackTo(Y) Mark(Y,b) zde je Y/b v pořáku Y/b je nekonzistentní Y/b je s X/a stále s X/a (konzistentní nekonzistentní, se vším nad X) Y=b tedy nezkoušíme přiřazovat Hana Rudová, Omezující podmínky, 4. prosince 201 8 166 zde je třeba X=? ^ Y/b znovu zkontrolovat Y=b Y/b je nekonzistení s X/a (aleje konzistentní se vším předtím) Další rozšíření backtrackingu Backmarking: příklad Problém N královen 1 . Dámy přiřazujeme po řádcích, tj. pro 1 každou dámu hledáme sloupec 1 2. Vedle šachovnice píšeme úrovně návratu 1 (BackTo). Na začátku všude 1. 1 3. Do políčka zapisujeme čísla ^ nejvzdálenějších konfliktních dam (Mark). Na začátku všude 1 J 5 4. Dámu v řádku 6 nelze přiřadit. 1 5. Vracíme se na 5, opravíme BackTo. 1 6. Když znova přijdeme na 6, všechny pozice jsou stále špatné (M a r k< BackTo) Backmarking lze kombinovat s backjumpingem (zdarma) 1 m 2 i « 3 2 1 2 ľ 4 !> 5 4 2 1 2 3 6 3 2 4 3 1 2 3 7 8 Hana Rudová, Omezující podmínky, 4. prosince 201 8 167 Další rozšíření backtrackingu Algoritmus backmarkingu procedure Backmarki ng((X,D, C)) rozdíly od backtrackingu Mark(Xj,v) := 0, BackTo(Xj) := 0 pro Ví a V v (inicializace datových struktur) i : = 1 (inicializace čitače proměnných) D[ := Di (kopirováni domény) whi 1 e 1 < i < n přiřazeni xt := Select-Value-Backmarking if Xi is null (žádná hodnota nebyla vrácena) for V j :i < j < n (úprava BackTo pro budouci proměnné) if í < BackTo(Xj) then BackTo(Xj) := í (í je nový nejvzdálenějši návrat) BackTo(Xj) := i - 1 i := i-1 (zpětná fáze) else i := í + 1 (dopředná fáze) D[ := Dt if í = 0 return , ,nekonzistentni ' ' else return přiřazené hodnoty {x\,...,xn} end Backmarking Hana Rudová, Omezující podmínky, 4. prosince 2018 168 Další rozšíření backtrackingu Uspořádání hodnot pro backmarking proceduře Select-Value-Backmarking smaž z D[ všechna v taková, že Mark(X{,v) Neúplná stromová prohledávání Hana Rudová, Omezující podmínky, 4. prosince 201 8 171 Neúplná stromová prohledávání Neúplná stromová prohledávání Neprohledáváme celý stavový prostor Nemáme záruku, že řešení neexistuje, i když ho algoritmus nenalezne M ztráta úplnosti M u některých algoritmů lze obecně zaručit úplnost, i když s vyšší složitostí než měl původní algoritmus V řadě případů najdeme řešení rychlejil I Neúplné algoritmy často odvozeny od algoritmu úplného (DFS) M přerušení běhu algoritmu (cutoff) ±< po vyčerpání přiděleného prostředku (čas, počet návratů, ...) algoritmus přerušíme X* prostředek může být globální (pro celý strom) i lokální (pro daný podstrom nebo uzel) opakovaní běhu algoritmu (restart) ± běh předešlého neúplného prohledávání opakujeme s jiným nastavením parametrů při opakování běhu lze využívat algoritmy učení Hana Rudová, Omezující podmínky, 4. prosince 2018 172 Neúplná stromová prohledávání Randomizovaný backtracking Časově omezený backtracking (přerušení) běh (úplného) algoritmu ukončíme po zadaném časovém intervalu (prostředek=čas) časový interval lze pro další běhy zvětšit => při dostatečném počtu kroků máme úplný algoritmus Náhodný výběr hodnot a proměnných (opakování) I M pokud máme možnost volby při výběru hodnot nebo proměnných (vzhledem k dané heuristice uspořádání hodnot a proměnných) náhodně zvolíme některou z nichl 3 Randomizovaný backtracking s učením 3 chybná přiřazení předchozích běhů uchováme a využíváme M takto lze také dosáhnout úplnosti, protože chybných přiřazení je konečně mnoho Hana Rudová, Omezující podmínky, 4. prosince 201 8 173 Neúplná stromová prohledávání Omezení počtu návratů 3 Bounded-backtrack search (BBS) Omezený počet návratů (přerušení) «• návrat do bodů volby, kde už nelze vybrat novou hodnotu nezapočítáváme „omezený počet navštívených listů" Při neúspěchu zvětšíme počet návratů o jedna (opakování) Implementace 3 počítáme počet návratů (neúspěchů) M při překročení meze se prohledávání ukončí Hana Rudová, Omezující podmínky, 4. prosince 2018 174 Neúplná stromová prohledávání Omezení hloubky Depth-bounded search (DBS) Omezíme hloubku prohledávaného stromu (přerušení) M do dané hloubky stromu se zkouší všechny alternativy M ve zbytku stromu se může použít jiná neúplná metoda Při neúspěchu zvětšíme hloubku prohledávání o jedna (opakování) Příklad: DBS(1 ,BBS(0)) I M Implementace M udržujeme pořadové číslo přiřazované proměnné je-li pořadové číslo větší než daná mez, zkouší se pouze jedna alternativa - BBS(O) Hana Rudová, Omezující podmínky, 4. prosince 2018 1 75 Neúplná stromová prohledávání Prohledávání s kreditem Credit search (CS) Omezený kredit (počet návratů) pro prohledávání (přerušení) kredit se rovnoměrně dělí mezi alternativní větve prohledávání 3 Implementace v každém uzlu se nejednotkový kredit (rovnoměrně) rozdělí mezi alternativní podstromy při jednotkovém kreditu se neberou alternativy Hana Rudová, Omezující podmínky, 4. prosince 2018 176 Neúplná stromová prohledávání Iterativní rozšiřování Iterative broadening IB 3 Omezený maximální počet voleb (hodnot) při každém výběru proměnné (přerušení) 3 v každém bodě volby větvení omezeno konstantou M při překročení max. počtu voleb pokračujeme předchozím bodem volby Při neúspěchu zvýšíme povolený počet voleb o jedna (opakování) 3 Implementace M po výběru proměnné umožníme pouze výběr určeného počtu jejích hodnot Hana Rudová, Omezující podmínky, 4. prosince 2018 177 Neúplná stromová prohledávání Stromová prohledávání a heuristiky Při řešení reálných problémů často existuje nápověda odvozená ze zkušeností s „ručním" řešením problému 3 Heuristiky - radí, jak pokračovat v prohledávání M doporučují hodnotu pro přiřazení často vedou přímo k řešení 3 Co dělat, když heuristika neuspěje? I M DFS se stará hlavně o konec prohledávání (spodní část stromu) DFS tedy spíše opravuje poslední použité heuristiky než první 3 DFS předpokládá, že dříve použité heuristiky ho navedly dobřel Pozorování: M počet porušení heuristiky na úspěšné cestě je malý M heuristiky jsou méně spolehlivé na začátku prohledávání než na jeho konci (na konci máme více informací a méně možností) Hana Rudová, Omezující podmínky, 4. prosince 2018 178 Neúplná stromová prohledávání Zotavení se z chyb heuristiky Heuristika doporučuje hodnotu pro prirazení Diskrepance = porušení heuristiky M použita jiná hodnota, než doporučila heuristika Pozorování: málo chyb heuristiky na cestě k řešení => cesty s méně diskrepancemi jsou prozkoumány dříve 3 Pozorování: chyby heuristiky hlavně na začátku cesty => cesty s diskrepancemi na začátku jsou prozkoumány dříve Hana Rudová, Omezující podmínky, 4. prosince 201 8 179 Neúplná stromová prohledávání Omezené diskrepance Limited discrepancy search (LDS) Omezený maximální počet diskrepancí na cestě (přerušení) M cesty s diskrepancemi na začátku jsou prozkoumány dříve Při neúspěchu navýšíme počet povolených diskrepancí o jedna (opakování) 3 tj. nejprve jdeme tak, jak doporučuje heuristika; potom jdeme po cestách s maximálně jednou diskrepancí; pak maximálně se dvěma diskrepancemi, atd. Příklad: LDS-PROBE(l), heuristika ' ~ ~ " 1 doporučuje vydat se levou větví Diskrepance pro nebinární domény 6 54 3 2 1 3 nedoporučené hodnoty se berou jako jedna diskrepance (zde) výběr každé další hodnoty proměnné je jedna diskrepance (tj. třetí hodnota = dvě diskrepance, čtvrtá hodnota = tři diskrepance, ...) Hana Rudová, Omezující podmínky, 4. prosince 2018 180 Neúplná stromová prohledávání Algoritmus LDS procedure LDS(Variables,Constraints) for D=0 to |Variables| do % D určuje max. počet povolených diskrepancí R := LDS-PROBE(Variables,{},Constraints,D) if R ^ fail then return R return faill procedure LDS-PROBE(Unlabelled,Labelled,Constraints,D) if Unlabelled = {} then return Labelled select X e Unlabelled I Values^ := - {values inconsistent with Labelled using Constraints} if Values^ = {} then return fail else select HV e Values^ using heuristic if D>0 then for VV g ValuesHHV} do R := LDS-PROBE(Unlabelled-{X}, Labelled u {X/V}, Constraints, D-l) if R ^ fail then return R return LDS-PROBE(Unlabelled-{X}, Labelled u {X/HV}, Constraints, D) end LDS-PROBE Hana Rudová, Omezující podmínky, 4. prosince 2018 181 Neúplná stromová prohledávání Omezené diskrepance - zlepšení LDS v každé další iteraci prochází i větve z předchozí iterace, tj. opakuje již provedený výpočet a navíc se v rámci iterace musí vracet do již prošlých částí Improved limited discrepancy s e are h (ILDS) 3 daný počet diskrepancí na cestě (přerušení) s> cesty s diskrepancemi na konci prozkoumány dříve Při neúspěchu navýšíme počet diskrepancí o jedna (opakování) Příklad: ILDS-PROBE(l), heuristika doporučuje vydat se levou větví 1 2 3 I Hana Rudová, Omezující podmínky, 4. prosince 201 8 182 Neúplná stromová prohledávání Algoritmus ILDS procedure ILDS(Variables,Constraints) % analogie LDS(Variables,Constraints) procedure ILDS-PROBE(Unlabelled,Labelled,Constraints,D) Rozdíly od LDS if Unlabelled = {} then return Labelled select X e Unlabelled Values^ := - {values inconsistent with Labelled using Constraints} if Values^ = {} then return fail else select HV e Values^ using heuristic if D<|Unlabelled| then R := ILDS-PROBE(Unlabelled-{X}, Labelled u {X/HV}, Constraints, D) if R ^ fail then return R if D>0 then for VV g ValuesHHV} do R := ILDS-PROBE(Unlabelled-{X}, Labelled u {X/V}, Constraints, D-1) if R ^ fail then return R end ILDS-PROBE Hana Rudová, Omezující podmínky, 4. prosince 201 8 183 Neúplná stromová prohledávání Hloubkou omezené diskrepance 3 ILDS bere cesty s diskrepancemi na konci dříve 3 Depth-bounded discrepancy search (DDS) 3 Diskrepance povoleny pouze do dané hloubky (přerušení) v této hloubce je vždy diskrepance, tj. zabrání se procházení větví z předchozí iterace hloubka zároveň omezuje maximální počet diskrepancí 3 cesty s diskrepancemi na začátku prozkoumány dříve Při neúspěchu navýšíme hloubku o jedna (opakování) Příklad: DDS(3), heuristika doporučuje vydat se levou větví 3 12 3 4 Hana Rudová, Omezující podmínky, 4. prosince 2018 184 Neúplná stromová prohledávání Lokální prohledávání Lokální prohledávání (LS) Princip M pracuje s úplnými nekonzistentními přiřazeními proměnných 3 snaží se lokálními opravami snížit počet konfliktů Příklad: umístění n dam na šachovnici M iniciální přiřazení umístí každou královnu do každého sloupce a řádku bez ohledu na diagonální omezení přesunujeme královnu v jejím sloupci do jiného řádku tak, abychom odstranili co nejvíce konfliktů M LS vyřeší řádově větší problémy než algoritmy založené na prohledávání do hloubkyl Přibližná metoda prohledávání neúplná metoda nezaručuje nalezení (vyloučení existence) řešení i když existuje (neexistuje) malé paměťové nároky Hana Rudová, Omezující podmínky, 4. prosince 2018 186 Lokální prohledávání Terminologie lokálního prohledávání M Stav 0: ohodnocení všech proměnných Evaluace E: hodnota objektivní funkce (počet nesplněných podmínek=počet konfliktů) M Globální optimum: stav s nejlepší evaluaci M Lokální změna: změna hodnoty (jedné) proměnné M Okolí o: množina stavů lišící se od daného stavu o jednu lokální změnu M Lokální optimum: stav, v jehož okolí jsou stavy s horší evaluací; není globálním optimuml Striktní lokální optimum: stav, v jehož okolí jsou pouze stavy s horší evaluací; není globálním optimum & Ne-striktní lokální optimum: stav, v jehož okolí exisují stavy se stejnou evaluací; není globálním optimum & Plateau: množina stavů se stejnou evaluaci minimum Hana Rudová, Omezující podmínky, 4. prosince 2018 187 Lokální prohledávání Algoritmus lokálního prohledávání Algoritmy lokálního prohledávání mají společnou kostru procedure LS(MaxPokusu,MaxZmen) parametry algoritmu 6 : = náhodné ohodnoceni proměnných for i := 1 to MaxPokusu while GPodminka do for j := 1 to MaxZmen while LPodminka do if E(0)=O then return 0 vyber ô e o(0) if akceptovatelne(č) then 6 := ô 6 := novyStav(fl) return nejlepši 6i 3 Jak stanovit MaxPokusu, MaxZmen? 3 pokračovat dokud existuje přiřazení s lepší evaluací restart (MaxPokusu>l) v některých případech diskutabilní Hana Rudová, Omezující podmínky, 4. prosince 2018 188 Lokální prohledávání Metoda největšího stoupání (hill climbing) HC Začíná v náhodně vybraném stavu M Hledá vždy nejlepší stav v okolí Okolí = hodnota libovolné proměnné je změněna, velikost okolí n x (d - 1) Útěk ze striktního lokálního minima pomocí restartu proceduře HC(MaxZmen) restart: 0 : = náhodné ohodnoceni proměnných for j := 1 to MaxZmen do if E(0) = 0 then return 0 if 0 je striktní lokální optimum then goto restart else 0 := stav z o{0) s nejlepší evaluaci goto restart end HC Hana Rudová, Omezující podmínky, 4. prosince 201 8 189 Lokální prohledávání Metoda minimalizace konfliktu (MC) Okolí u HC je poměrně velké: n x (d - 1) M ale pouze změna konfliktní proměnné může přinést zlepšení M konfliktní proměnná = vystupuje v některých nesplněných podmínkách MC mění pouze konfliktní proměnné 3 okolí = hodnota zvolené proměnné je změněna, velikost okolí d - 1 proceduře MC(MaxZmen) 6 : = náhodné ohodnoceni proměnných PocetZmen := 0 while E(0) > 0 a PocetZmen únik z lokálního minima prostřednictvím náhodného výběru Hana Rudová, Omezující podmínky, 4. prosince 2018 191 Lokální prohledávání Minimalizace konfliktů s náhodnou procházkou proceduře MCRW(MaxZmen,p) Rozdíly od MC 6 : = náhodné ohodnoceni proměnných PocetZmen := 0 while E(0) > 0 a PocetZmen (1 - p) 0.02 < p < 0.1 vyber náhodně hodnotu a pro V else vyber hodnotu a, která minimalizuje počet konfliktů pro V if a^současná hodnota V then při řad' a do V PocetZmen := PocetZmen+1 return 0 Hana Rudová, Omezující podmínky, 4. prosince 201 8 192 Lokální prohledávání Největší stoupání s náhodnou procházkou procedure HCRW(MaxZmen, p) Rozdíly od MCRW 6 : = náhodné ohodnoceni proměnných PocetZmen := 0 while E(0) > 0 a PocetZmen s nejlepší evaluací if a^současná hodnota V then pri rad' a do V PocetZmen := PocetZmen+1 return 0 Hana Rudová, Omezující podmínky, 4. prosince 201 8 193 Lokální prohledávání Tabu seznam 3 Setrvání v lokálním optimu je speciálním případem cyklu M Jak se obecně zbavit cyklů? M stačí si pamatovat předchozí stavy a zakázat opakování stavu ±> paměťově příliš náročné (mnoho stavů) M můžeme si zapamatovat pouze několik posledních stavů (zabrání krátkým cyklům)l Tabu seznam = seznam tabu (zakázaných) stavů I M stav lze popsat význačným atributem (není nutné uchovávat celý stav) M (proměnná,hodnota): zachycuje změnu stavu (uložíme původní hodnoty) tabu seznam má fixní délku {tabu tenure) ±< „staré" stavy ze seznamu vypadávají s přicházejímími novými stavyl M Aspirační kritérium = odtabuizovaní stavu 3 do stavu lze přejít, i když je v tabu seznamu (např. krok vede k celkově lepšímu stavu)l Tabu seznam je používán samostatně i v kombinaci s jinými metodami LS Hana Rudová, Omezující podmínky, 4. prosince 2018 194 Lokální prohledávání Algoritmus prohledávání s tabu seznamem Tabu seznam zabraňuje krátkemu cyklení 3 Povoleny jsou pouze tahy mimo tabu seznam a tahy splňující aspirační kritérium 3 Tabu seznam (TS) v kombinaci s metodou stoupání (HC): proceduře TSHC(MaxZmen) 6 : = náhodné ohodnoceni proměnných I PocetZmen := 0 while E(0) > 0 a PocetZmen do tabu seznamu, kde c je současná hodnota V smaž nejstarši položku v tabu seznamu při řad' a do V PocetZmen := PocetZmen+1 return 0 Hana Rudová, Omezující podmínky, 4. prosince 2018 195 Lokální prohledávání Výběr souseda: přehled Metoda stoupání (HC) 3 soused s nejlepší evaluací vybrán Tabu prohledávání (TS+HC) 3 soused s nejlepší evaluací vybrán (metoda stoupání) sousedé z tabu seznamu nemohou být vybránil Minimální konflikt (MC) soused je omezen na náhodně vybranou konfliktní proměnnou 3 výběr její hodnoty s nejlepší evaluací Náhodná procházka (RW) 3 soused vybrán náhodně Min. konflikt (metoda stoupání) s náhodnou procházkou MC+RW (HC+RW) 3 s malou pravděpodobností: náhodný výběr souseda jinak: minimální konflikt (metoda stoupání) Hana Rudová, Omezující podmínky, 4. prosince 2018 196 Lokální prohledávání Simulované žíhání (simulated annealing) SA Myšlenka: simulace procesu ochlazování kovů na začátku při vyšší teplotě atomy více kmitají a pravděpodobnost změny krystalické mřížky je vyšší 3 postupným ochlazováním se atomy usazují co „nejlepší polohy" s nejmenší energií a pravděpodobnost změny je menší => na začátku je tedy pravděpodobnost toho, že akceptujeme zhoršování řešení, vyšší I Akceptování nového stavu vždy při zlepšení M při zhoršení pouze za dané pravděpodobnosti, která klesá se snížením teploty Cykly algoritmu M vnější: simulace procesu ochlazování snižováním teploty T čím nižší bude teplota, tím nižší bude pravděpodobnost akceptování zhoršení M vnitřní: počítáme, kolikrát jsme neakceptovali zhoršení (dán limit Maxlter) Hana Rudová, Omezující podmínky, 4. prosince 2018 197 Lokální prohledávání Metropolisovo kritérium Rozdíl mezi kvalitou nového (5) a existujícího (9) řešení 3 AE = E(5)-E(0) 3 E (chybovost) musí být minimalizováno Metropolisovo kritérium I lepší (někdy případně i stejně kvalitní) řešení akceptováno: AE > 0 horší řešení (AE > 0) akceptováno pokud U < e~AE/T 3 U náhodné číslo z intervalu (0,1)1 3 pomůcka: porovnej e-10/100 vs. e-100/100,a e-10/100 vs. e-10/l Hana Rudová, Omezující podmínky, 4. prosince 201 8 198 Lokální prohledávání Algoritmus simulovaného žíhání procedure SA( TInit, TEnd, Maxlter ) 6 : = náhodné ohodnoceni proměnných a := 6 (dosud nejlepši nalezené přiřazeni) for T := TInit to TEnd PocetChyb := 0 while PocetChyb < Maxlter vyber lokálni změnu z 0 do ô if E (ô) A) => CSP nad disjunkcemi boolean proměnných 3 SAT je NP-úplnýl 1 LS řeší poměrně velké formule M formulace LS je velice přirozená a jeho použití je velice populární M lokální změna je překlápěním (flipping) hodnoty proměnné Algoritmus GSAT (greedy SAT) M postupné překlápění proměnných M evaluace udává, jaký je (vážený) počet nesplněných klauzulí Hana Rudová, Omezující podmínky, 4. prosince 2018 200 Lokální prohledávání Algoritmus GSAT proceduře GSAT(A,MaxPokusu,MaxZmen) (A je CNF formule) for i := 1 to MaxPokusu do 0 : = náhodné ohodnoceni proměnných for j := 1 to MaxZmen do i f A je splnitelná pomoci 0 then return 0 V := proměnná, jejíž změna hodnoty nejvice sniži počet nesplněných klauzuli 0 := přiřazeni, které se liši od 0 změnou hodnoty V return nejlepši 0i M Příklad: {-.C, -A v v C, -A v D v E, v --C} M iniciální přiřazení (všechny proměnné mají hodnotu 1) nesplňuje první a poslední klauzuli změna A,D,E nemá vliv na počet nesplněných klauzulí 3 změna C na 0 splní první i poslední klauzuli ale nesplní —>A v ~*B v C (evaluace=l) 3 změna B má evaluaci 1 také, pokud ale změníme C a pak B, pak dostáváme evaluaci 0 Hana Rudová, Omezující podmínky, 4. prosince 2018 201 Lokální prohledávání Heuristiky pro GSAT 3 GSAT lze kombinovat s různými heuristikami, které zvyšují jeho efektivitu obzvláště při řešení strukturovaných problémů Použití náhodné procházky spolu s minimalizací konfliktů Vážení klauzulí 3 některé klauzule zůstávají po řadu iterací nesplněné, klauzule tedy mají různou důležitost M splnění „těžké" klauzule lze preferovat přidáním váhy M váhu může systém odvodit ±> na začátku mají všechny klauzule stejnou váhu ±> po každém pokusu zvyšujeme váhu u nesplněných klauzulí Průměrování řešení 3 standardně každý pokus začíná z náhodného řešení 3 společné části předchozích řešení lze zachovat ±> restartovací stav se vypočte ze dvou posledních výsledků bitovým srovnáním stejné bity zachovány, ostatní nastaveny náhodně Hana Rudová, Omezující podmínky, 4. prosince 2018 202 Lokální prohledávání Hybridní prohledávání 3 Příklady kombinace lokálního prohledávání M prohledává úplná nekonzistentní přiřazení a stromového prohledávání 3 rozšiřuje částečné konzistentní přiřazeni 1. Lokální prohledávání před nebo po stromovém prohledávání např: M před: lokální prohledávání nám poskytne heuristiku na uspořádání hodnot -0 po: lokálním prohledáváním se snažíme lokálně vylepšit spočítané řešení (optimalizace) 2. Stromové prohledávání je doplněno lokálním prohledávání v listech prohledávacího stromu i v jeho uzlech např. lokální prohledávání pro výběr hodnoty nebo vylepšení spočítaného řešení 3. Lokální prohledávání je doplněno stromovým prohledáváním pro výběr souseda z okolí a nebo pro prořezávání stavového prostoru Hana Rudová, Omezující podmínky, 4. prosince 201 8 203 Lokální prohledávání Iterativní dopředně prohledávání Iterative Forward Search (IFS) 3 Hybridní prohledávání: konstruktivní nesystematický algoritmus M pracuje nad modelem s pevnými a měkkými omezujícími podmínkami pevné podmínky: musí být splněny měkké podmínky: reprezentují účelové funkce, jejichž vážený součet je minimalizován Pracuje s konzistentními přiřazeními 3 Základní myšlenky (blízký dynamickému backtrackingu) ' 3 začíná s prázdným přiřazením M vybere novou proměnnou k přiřazení pokud nalezne konflikt, zruší přiřazení všech proměnných v konfliktu s vybranou proměnnou M výběr hodnot pomocí konfliktní statistiky 3 výběr proměnných není pro algoritmus kritický, protože lze proměnné přiřadit opakovaně Hana Rudová, Omezující podmínky, 4. prosince 2018 204 Lokální prohledávání IFS: algoritmus procedure IFSQ iteration = 0; % čítač iterací current = 0; % aktuální řešení best = 0; % nejlepší řešení while canContinue (current, iteration) do iteration = iteration + 1; variable = selectVariable (current); value = selectValue (current, variable); unassign(current, conflictingVariables(current, variable, value)); assign(current, variable, value); if better (current, best) then best = current return best end IFS procedure conflictingVariables: kontroluje konzistenci tak, aby byla splněna omezení na přiřazených proměnných, a vrací konfliktní proměnné unassign: odstraní přiřazení konfliktních proměnných Hana Rudová, Omezující podmínky, 4. prosince 2018 205 Lokální prohledávání IFS: konfliktní statistika Předpoklad: při výběru hodnoty a proměnné A je nutné zrušit přiřazení hodnoty b proměnné B, tj. [A = a — -> B = b] 3 V průběhu výpočtu si tedy lze pamatovat: A = a => 3x^B = b, 4x^B = c, 1 x ^ C = a, 120 x ^ D = al Při výběru hodnoty 3 vybíráme hodnoty s nejnižším počtem konfliktů vážených jejich frekvencí I ±> konflikt započítáme pouze tehdy, pokud to vede k odstranění přiřazení * pv. A = a => 3x^B = b, 4x^B = c, 1 x ^ C = a, 120 x^D = a A = b => lx^ B = a, 3x^ B = b, 2 x ^ C = a Máme přiřazení B = c,C = a,D = b a vybíráme hodnotu pro A: ±> nechť A/a vede ke konfliktu s BI c: vyhodnoceno jako 4 • není konflikt s C/a, tak se nezapočítává ±> nechť Alb vede ke konfliktu s C/a: vyhodnoceno jako 2 ±> tj. vybereme hodnotu b pro proměnnou A Hana Rudová, Omezující podmínky, 4. prosince 2018 206 Lokální prohledávání Srovnání prohledavačích algoritmů Srovnání prohledávacích algoritmů A — B znamená, že uzly prohledávacího stromu B jsou i v stromě A M za předpokladu stejného uspořádání hodnot i proměnných Existuje srovnání i pro další algoritmy? Jaké algoritmy používat pro daný problém? Experimentální porovnání na různýc sadách problémů (benchmarks) M reálné problémy M náhodně vygenerované problémy aplikačně založené náhodné problémy Kriteria CPU čas velikost generovaného prohledávacího stromu počet volání procedury (např. Consi stent) I Hana Rudová, Omezující podmínky, 4. prosince 201 8 208 Srovnání prohledávacích algoritmů Experimenty na reálných problémech Sady reálných problémů (benchmarks), na kterých lze algoritmy porovnávat CSPLib http://www.csplib.org M knihovna problémů pro omezující podmínky (otevřená pro nové problémy) 3 kolem 130 problémů z oblasti jako je rozvrhování, návrh a konfigurace, kombinatorika, bioinformatika, hry popis problému, reference na jeho řešení, data, výsledky někdy i řešení nebo podrobné studie různých možností řešení příklady ±> dopravní signalizace v čase na zadaných křižovatkách, výrobní linka, problém batohu, sledování cíle v distribuovaných senzorických sítích, ... Problém: výsledky lze stále velice obtížně zobecnit na další problémy pro jeden problém je lepší jeden algoritmus, pro další problém jiný algoritmus Hana Rudová, Omezující podmínky, 4. prosince 201 8 209 Srovnání prohledávacích algoritmů Náhodné problémy Algoritmy porovnávány na umělých, náhodně vygenerovaných problémech M lze generovat problémy různé obtížnosti (fáze přechodu) 3 libovolný počet datových instancí 3 lze testovat, co se stane (např. s parametry algoritmu) při změnách problému Náhodné binární CSP (random binary CSP) 3 parametry (n, m, pi, p2) 3 n počet proměnných M m počet hodnot v doméně proměnných pi pravděpodobnost, že existuje omezení na páru proměnných 3 p2 pravděpodobnost, že omezení povoluje daný pár hodnot Hana Rudová, Omezující podmínky, 4. prosince 201 8 210 Srovnání prohledávacích algoritmů Aplikačně založené náhodné problémy Identifikace problémové domény M lze definovat parametrizovatelné problémy 3 problémy mají přitom specifickou (z aplikace vycházející) strukturu problémy lze náhodně generovat s různým nastavením parametrů M Výhody 3 zaměřené na reálné problémy generování řady problémů umožňuje statistické porovnání M Příklad: shop scheduling problémy m strojů n úloh, každá úloha se skládá z m operací prováděných na odlišných strojích operace jedné úlohy nesmí být prováděny zároveň 3 podmínky na sekvencování operací úlohy (žádné, dáno pořadí, stejné pořadí pro všechny) 3 minimalizace dokončení poslední úlohy, minimalizace největšího zpoždění úlohy, ... Hana Rudová, Omezující podmínky, 4. prosince 2018 21 1 Srovnání prohledávacích algoritmů Fáze přechodu Náhodný k-SAT problém formule pevné délky jsou generovány výběrem m klauzulí 3 každá klauzule délky k je uniformně náhodně generována z množiny všech klauzulí Obtížnost nalezení řešení při malém počtu klauzulí je většina problémů splnitelná a snadno řešitelná při velkém počtu klauzulí je detekována snadno nesplnitelnost většiny problémů nalezení řešení je nejobtížnější za předpokladu, že cca 50% problémů je splnitelných! Fenomén fáze předchodu (phase transition) 3 fáze přechodu z obtížně řešitelných problémů na snadno řešitelné problémů počet volání Využití fáze přechodu: lze generovat problémy různé obtížnosti poměr počtu klauzulí vůči počtu proměných Hana Rudová, Omezující podmínky, 4. prosince 201 8 21 2 Srovnání prohledávacích algoritmů Optimalizace & soft omezení: modely Optimalizační problém s podmínkami (COP) Problém splňování podmínek (X, D, C) M proměnné X = {x\,... ,xn} M domény D = {Di,... ,Dn} M omezení C = {Ci,..., Cn} ± Q je definováno na Y* c x, Yi = {x^.....xík} x Q je podmnožina x ... x D^l Objektivní funkce obj : Soi — W 3 Základní definice: Optimalizační problém s podmínkami (constraint optimization problem) M nalezení řešení d pro (X, D, C) takové, že obj (d) je optimálni x optimální = maximální nebo minimálni Hana Rudová, Omezující podmínky, 4. prosince 201 8 214 Optimalizace & soft omezení: modely COP: operační výzkum Pevné (hard, required) omezení Ch = {Ci,..., Cn} 3 Q je definováno na Y* ^X,Yi= {xh,... ,xik} 3 Q je podmnožina x ... x Difc Měkké (soft) omezení Cs = {Fi,..., Fi\ Fj je definované nad Qj ^ X, Qj = {Xjlt... Fj je funkce do reálných čísel Dj1 x ... x DJř + Optimalizační problém s podmínkami (COP): (X,D,Ch,Cs)i Objektivní funkce relace funkce I zjednodušení na X F(d) = XFj(d[Qj]) d[Qj]... projekce d na Qjl Řešení COP: d° splňující všechna omezení z Ch tak, že F(d°) = maxdF(d) nebo = min^FW) Hana Rudová, Omezující podmínky, 4. prosince 201 8 21 5 Optimalizace & soft omezení: modely Použití soft omezení Problémy optimalizační, příliš podmíněné, špatně definované problémy, ... M Fuzzy preference, pravděpodobnosti, ceny, váhy, úrovně požadavků,... 3 Příliš podmíněné problémy: řešení CSP neexistuje Fi Prednáška < Cvičeni @ 10 tj . pokud PrednaskaCviceni pak Fi=10 F2 Prednáška in 4. .5 @6 t j . pokud Prednaskae{4, 5} pak F2=0 pokud Prednaska<£{4,5} pak F2=6 F3 Cviceni in 1. .4 @ 4l Problémy s nejistotou M Je 0.7 nezbytné, abych přišla do středy. po..st 0.7, ct..ne 0 Je nezbytné, abych nepřišla příliš později než ve středu, po..st 0.7, ct 0.5, pa 0.3, so..ne Ol Špatně definované problémy: není zřejmé, která omezení definují CSP Zitra = pekne @ 80% Zitra = zamračeno @ 30% Hana Rudová, Omezující podmínky, 4. prosince 201 8 216 Optimalizace & soft omezení: modely Přístupy pro soft omezení Vybrané přístupy M základní: MAX-CSP, omezení s váhami, fuzzy omezení 3 zobecňující: omezení nad polookruhy (semiring-based)i Rozlišení systémů na základě: (v závorkách popis pro CSP)^ omezení - rozšíření klasického omezení (c = relace) problém - rozšíření CSP (trojice (V,D,C)) 3 úroveň splnění - jak přiřazení hodnot splňuje problém (/\c0) 3 řešení - které přiřazení je (optimálním) řešením (splňují všechna omezení) 3 úroveň konzistence problému - jak je možné nejlépe splnit problém tj. jak (optimální) řešení splňuje problém (true) Hana Rudová, Omezující podmínky, 4. prosince 201 8 217 Optimalizace & soft omezení: modely Omezení s váhami, MAX-CSP 3 Omezení s váhami: Váha/cena spojená s každým omezením M Omezení - dvojice (c,w(c)) M Problém - trojice (V,D,CW) M Úroveň splnění - funkce na množině přiřazení co(0) = Xčn-c => součet vah nesplněných omezení M Řešení - přiřazení 9 s minimální co(9) M Úroveň konzistence - úroveň splnění řešení 3 MAX-CSP (maximální CSP) Váhaje rovna jedné => maximalizace počtu splněných omezení Hana Rudová, Omezující podmínky, 4. prosince 201 8 218 Optimalizace & soft omezení: modely Omezení s váhami: příklad Přednáška < Cvičeni @ 10 Přednáška in 4.. 5 @6 Cvičeni in 1..4 @ 4 Přiřazení: @1 tj . juC2=1 = 1 => @0.5 tj. juc2=0. 5 = 2 => @0.1 tj . jUC2=0.1 c3: max(A + B) @(A + B)/10 tj . juc3=(A + B)/10l 3 Fuzzy CSP (X,D,Cf) M Cf je množina fuzzy omezení X uspořádaná množina proměnných Hana Rudová, Omezující podmínky, 4. prosince 201 8 220 Optimalizace & soft omezení: modely Kombinace a projekce omezení M Projekce n-tic (dl9...,di) iYx příklad: (1,2,3,4,5) í[dae)d'e)= (4,1,5)1 Kombinace c = cx © cY, dom(c) = Z = X u Y c,cx,cY omezení nad Z,X, Y Vc(di,...,dk) = min(jL/Cx((di, ■ ■ ■, dk) if ),/iCy((di, ■ ■ ■ ,dk) ly)) 3 udává, jaká je úroveň splnění všech přiřazení Z vzhledem k cx a cy příklad (pokračování): kombinace cl e c2 e c3 pro (1, 3) /iaec2ec3(l,3) = min(/ici((l)), aic2((1, 3)), /ic3((l, 3))) =min(l, 0.1,0.4) = O.ll 1 Projekce C = Cy ^x, dom(c) = X,X c 7 c,cx,cy omezení nad x.x.y iuc(dxl,... ,dxk) = max iäCY(dyi,... ,dyi) ((dyi,...,dyi)EDyix---xDyi)A((dyi,...,dyi)lx=(dxi,...,dxji)) M udává, jaká je úroveň splnění všech přiřazení X vzhledem k cy «• příklad (pokračování): projekce c3 ^(B) na (1) /ic3^(B)(l) = max(/iC3(l, l),jUC3(2, l),/iC3(3, 1)) = max(0.2,0.3,0.4) = 0.4 Hana Rudová, Omezující podmínky, 4. prosince 2018 221 Optimalizace & soft omezení: modely Řešení fuzzy CSP 3 Úroveň splnění přiřazení (d\,..., dn) dána jako jL/0c(di, ■ ■ ■, dn)t Řešení - přiřazení (d\,..., dn) takové, že max ij®c(di,...,dn) = c(P^)I příklad: © C = cl e c2 e c3 pro všechna (A, B) ^ (3,3) ...0.6, (2,2)...0.4, (1,1)...0.2 (2,3) a (3,2) ...0.5, (2,1) a (1,2)...0.3 (1,3) a (3,1)...0.11 => (3,3) je řešení, c(P^) = 0.61 Úroveň nekonzistence 1 - CCF^) C (Pii) je úroveň konzistence také jako projekce na prázdnou množinu proměnných ©C ^0 Hana Rudová, Omezující podmínky, 4. prosince 201 8 222 Optimalizace & soft omezení: modely Příklad: řešení fuzzy CSP 3 Viz dříve: 0 C = cl © c2 © c3 pro všechna (A, B) (3,3) ...0.6, (2,2)...0.4, (1,1)...0.2, (2,3) a (3,2) ...0.5, (2,1) a (1,2)...0.3, (1,3) a (3,1)...0.1 ©C = ©C %,B} 0 C ^{A,B} (3, 3) = max(A/ec(3, 3)) = 0.6, eCIM1(2,2) = 0.4,...l ( ©C^{A} (1) =max(/i©c(l.l)./iec(1.2),/iec(1.3)) = max(0.2,0.3,0.1) =0.3 ©C^{A} (2) =max(AJ©c(2,D,A/ec(2,2),AJec(2,3)) = max(0.3,0.4,0.5) =0.5 ©C^{A} (3) =max(AJ©c(3,D,A/©c(3,2),AJ©c(3,3)) = max(0.1,0.5,0.6) =0.61 * ©C U0 ©C W0 () =max(jU0C(l,l)-A/©c(l-2),A'©c(l,3),jU0c(2,l),iU©c(2,2), jU©c(2,3),jU©c(3,l),A'©c(3,2),jU©c(3,3)) = 0.6 Hana Rudová, Omezující podmínky, 4. prosince 2018 223 Optimalizace & soft omezení: modely Omezení nad polookruhy Semiring-based CSP 3 c-polookruh (JA, + , x,0,1) 3 JK. množina polookruhu (množina preferencí) 0 g J4. (úplné nesplnění), 1 e J4. (úplné splnění) ^ + komutativní, idempotentní, asociativní operace I s jednotkovým prvkem 0, s absorbujím prvkem 1 x komutativní, asociativní operace, distributivní nad +, s jednotkovým prvkem 1, s absorbujím prvkem 0 J x se používá ke kombinaci preferencí několika omezení min u fuzzy CSP 0 minimum (nesplnění), 1 maximum (splnění) Částečné uspořádání ((axb) < (c xb)) fakt, že něco lze lokálně zlepšit nelze globálně ignorovat (platí pro CSP s váhami) př. a = 0.3, c = 0.4, b = 0.2 pro fuzzy CSP: není striktní monotoniel idempotence: Va e JA: ax a = a (platí pro fuzzy CSP) omezení, které je v problému obsaženo, může být do něj přidáno beze změny významu př. x > l@10,x > l@10,x = 0@oo, přiřazení x = 0 má pro CSP s váhami úroveň konz. 20 I striktní monotonie a idempotence x zároveň pouze pro dvouprvkové JA, tj. jen pro CSPl Existující vztahy: CSP = fuzzy CSP na dvouprvkové J4. fuzzy CSP lze polynomiálně transformovat na CSP s váhami Hana Rudová, Omezující podmínky, 4. prosince 2018 225 Optimalizace & soft omezení: modely Definice omezení nad polookruhy Systém (S,D, V): S c-polookruh, D konečná doména, V uspořádaná množina proměnných Soft omezení (def, con): rozsah omezení con c y, def : D|Cřm| — J4. Soft problém je (C, con) nad (S,D, V), kde con ^ V, C množina omezení Projekce n-tic t ly * příklad: (1,2,3,4,5) 1JSÄe)d'e)= (4,1,5)1 | Kombinace c = c\ ® c 2 Ci = (defí, con{) and c 2 = (def 21 con-i) c = (def, con), con = coni u co^2, def {i) = defx(X\ccZx) x def2{ticZ2)l 3 příklad: CSP s váhami: J4 = N u {00}, + = min, x = +, +00, 0 zadáno omezení c\ na xy: aa 2, ab 4, ba 1, bb 0, zadáno omezení C2 na x: a 0, b 1 kombinace c = ci ® c2: aa 2(=2+0) ab 4(=4+0) ba 2(=1 +1) bb 1 (=0+1) Hana Rudová, Omezující podmínky, 4. prosince 2018 226 Optimalizace & soft omezení: modely Řešení pro omezení nad polookruhy Projekce c c = (def, con), I c y c' = (def, corí), con' = con n I de f (t') = X def^) f/f\Con _ff 3 příklad (pokračování): c\ na xy: aa 2, ab 4, ba 1, bb 0, projekce c\ ^{Xy- a 2, b 0 Úroveň splnění problému P = (C, con) udává omezení S0l(P) = (® C) V con 3 kombinace všech omezení v C a následovně projekce na proměnné v con M pro každé přiřazení proměnných v con vrací omezení Sol(P) jeho úroveň splnění «• příklad (pokračování): c\ na xy: aa 2, ab 4, ba 1, bb 0 c2 na x: a 0, b 1 problém Pi = ({ci,c2}, {x,y}): Sol(Pi) = (d ® c2) ^{x,yY- aa 2, ab 4, ba 2, bb 11 problém P2 = ({ci,c2}, {x}): Sol(P2) = (c\ ® c2) tt{Xy. a 2, b ll Úroveň konzistence: blevel(P) = Sol(P) tt0 3 příklad (pokračování): blevel{Pi) = blevel(P2) = 1 Hana Rudová, Omezující podmínky, 4. prosince 2018 227 Optimalizace & soft omezení: modely Optimalizace & soft omezení: algoritmy Soft propagace Klasická propagace: eliminace nekonzistentních hodnot z domén proměnných Soft propagace: propagace preferencí (cen) nad fc-ticemi hodnot proměnných snaha o získání realističtějších preferencí 3 výpočet realističtějších příspěvků pro cenovou funkcil C je soft ^-konzistentní, jestliže pro všechny podmnožiny (k - 1) proměnných W a libovolnou další proměnnou y platí ®{cí | Ci e C a corii ^W} = | q g C a corii c (W u {y})}) $w M coyií označuje proměnné v omezení a 3 uvažování (def) pouze omezení ve W stejné jako: uvažování (def) omezení ve W a omezení spojující y s W, s následnou projekcí na W Hana Rudová, Omezující podmínky, 4. prosince 201 8 229 Optimalizace & soft omezení: algoritmy Soft hranová konzistence (SAC) M k = 2,W = {x} : cx = cxy,cx}) ^{x}l M CSP: libovolná hodnota v doméně x může být rozšířena o hodnotu v doméně y tak, že je cxy splněno hodnoty a v doméně x, které nelze rozšířit na y, mají def((a)) = Ol Fuzzy CSP: úroveň preference všech hodnot x v cx je stejná jako úroveň preference daná cxy,cx}) tt{x}i I Příklad na fuzzy CSP: J4. = (0,1), + = max, x = min, 0, 1 3 x,y e {a,b} ■9 Cx ■ CL . . . 0.9,b. ..0.1, C-y • & • • • 0.9, b. ..0.5, 0.8, ab ... 0.2, ba...0, bb ... 0 .0 není SAC: cx dává 0.9 na x = a, ale cx}) ^{X} dává 0.8 na x = a ®{Cy, cxy, cx} dává na (a, a) : min(0.9,0.8,0.9) = 0.8 ®{cy, cxy, cx} dává na (a, Z?) : min(0.5,0.2,0.9) = 0.2 projekce (<8>{cy, cxy, cx}) ^{X} dávána (a) : max(0.8,0.2) =0.8 Hana Rudová, Omezující podmínky, 4. prosince 2018 230 Optimalizace & soft omezení: algoritmy Výpočet SAC 3 Základní algoritmus pro výpočet SAC: 3 pro každé x a y změnit definici cx tak, aby korespondovala s (®{Cy,CXy,CX}) tt{x} 3 iterace až do dosažení stabilityl x idempotentní (fuzzy CSP) zajištěna ekvivalence, tj. původní i nový (po dosažení SAC) problém mají stejné řešení 3 zajištěno ukončení algoritmu x není idempotentní (CSP s váhami) 3 pro každé u, v e JA existuje w e JA taková, že v xw = u 3 w se nazývá rozdíl mezi u a v, maximální rozdíl se značí u - v 3 nutno požadovat novou vlastnost pro systém (a rozšířit projekci a kombinaci) s novou vlastností zajištěna ekvivalence, při striktní monotonii zajištěno i ukončení tato vlastnost platí pro CSP s váhami Hana Rudová, Omezující podmínky, 4. prosince 2018 231 Optimalizace & soft omezení: algoritmy Řešení COP 3 Cíl: nalezení úplného řešení s optimální hodnotou cenové funkce Prohledávání 3 lokální prohledávání x přímé zahrnutí optimalizačního kriteria do evaluace (hodnota obj. funkce) 3 stromové prohledávání 3 metoda větví a mezí + její rozšíření CSP s omezeními: minimalizace součtu vah omezení minXCecc(^) 3 velmi častá optimalizační úloha 3 váha (cena) omezení: 0 = úplné splnění, (0, oo) částečné nesplnění, oo úplné nesplnění 3 hodnota cenové funkce: cena přiřazení/řešení «• maximalizace je duální problém 3 algoritmy pro fuzzy CSP na podobných principech Hana Rudová, Omezující podmínky, 4. prosince 2018 232 Optimalizace & soft omezení: algoritmy COP jako série CSP problémů Triviální metoda řešení 3 Řešení COP jako CSP a nalezení iniciální hodnoty cenové funkce W1 Opakované řešení CSP (í = 1...) s přidáním omezení XCecc(^) < Wl 3 Když řešení nového CSP neexistuje, pak poslední Wl dává optimum I 3 Výpočetně zbytečně náročné Efektivní rozšíření obtížné Hana Rudová, Omezující podmínky, 4. prosince 201 8 233 Optimalizace & soft omezení: algoritmy Metoda větví a mezí (branch&bound) BB M Prohledávání stromu do hloubky přiřazené=minulé proměnné P, nepřiřazené=budoucí proměnné F M omezení pouze na minulých proměnných Cp, omezení na minulých i budoucích proměnných Cpp, omezení pouze na budoucích proměnných C>l Výpočet mezí horní mez UB: cena nejlepšího dosud nalezeného řešení dolní mez LB: dolní odhad minimální ceny pro současné částečné přiřazení Ořezávání: LB > UB (cíl: minimalizace) M víme, že rozšíření současného částečného řešení už bude mít horší (vyšší) cenu LB než dosud nalezené řešení UB M lze proto ořezat tuto část prohledávacího prostoru příklad: pokud nalezneme řešení s cenou 10 odřízneme všechny větve, které mají cenu vyssi nez 9 Hana Rudová, Omezující podmínky, 4. prosince 2018 234 Optimalizace & soft omezení: algoritmy Metoda větví a mezí: výběr hodnoty Algorimus metody větví a mezí 3 generický algoritmus rozšiřitelný jako implementace backtrackingu 3 možná rozšíření zejména o: pohled dopředu, výpočet dolní meze LB(d) vrací dolní odhad ceny pro každé částečné přiřazení d M použití při rozšíření o jednu proměnnou LB(dí-i,a)i | Optimistický výběr hodnoty proceduře Select-Value-BB while D[ i s not empty vyber a smaž libovolný a e D[ takový, že min LB{at-\,a) if Consistent(aí_i,Xí = a) a LB(ät-i,a) < UB return a (jinak ořezej a) return null (konzistentní' hodnota neexistuje) Hana Rudová, Omezující podmínky, 4. prosince 201 8 235 Optimalizace & soft omezení: algoritmy Algoritmus metody větví a mezí proceduře Branch-Bound((X,D, C), UB,f^) rozdíly od backtrackingu i : = 1, D[ := Di (inicializace čitače proměnných, kopirováni domény) Reseni := null (řešeni dosud nenalezeno) repeat while 1 < i < n přiřazeni xt : = Select-Value-BB if Xi is null (žádná hodnota nebyla vrácena) i := i-1 (zpětná fáze) else i := í + 1 (dopředná fáze) D: := Di I if i = 0 if Reseni is not null return UB, Reseni else return , ,nekonzistentni ' ' else Reseni := x\,...,xn (uloženi hodnot dosud nejlepšiho přiřazeni) spočítej cenu současného přiřazení W = Scecc(^)' UB:=mm{W, UB} i := 1, nastav D'k na Dk pro k = 1... n until true end Branch-Bound Hana Rudová, Omezující podmínky, 4. prosince 2018 236 Optimalizace & soft omezení: algoritmy min Xcec c (d) Dolní mez Kvalita dolní meze: velmi důležitá pro efektivitu BB Dolní mez lze ovlivnit pomocí 3 ceny minulých proměnných i* vzdálenost (součet vah omezení na minulých proměnných) lokální ceny budoucích proměnných vzhledem k minulým proměnným 3 NC* 3 lokální ceny budoucích proměnných 3 AC* 3 globální ceny budoucích proměnných prohledávání ruská panenka Hana Rudová, Omezující podmínky, 4. prosince 201 8 237 Optimalizace & soft omezení: algoritmy NC* algoritmus Projekce ceny hodnot (j, *) pro každou proměnnou j do dolní hranice LB ceny řešení Smazání hodnot (j, a) převyšující (nebo rovné) horní hranici UB LB=6 LB=8 Hodnotu a proměnné j značíme (j, a) LB=8 UB=10 LB=8 UB=10 obrázek: proměnná j má nejprve tři hodnoty (j, 1), (j, 2), (j, 3), jejichž cena je 2,4 a 5 Všechny hodnoty proměnné j značíme (j, *) I Hana Rudová, Omezující podmínky, 4. prosince 2018 238 Optimalizace & soft omezení: algoritmy AC* algoritmus (A) Projekce ceny hrany (í,a)(j,b) do ceny hodnoty (í, a), pokud je tato cena zahrnuta ve všech hranách (i,a)(j, *) NC* algoritmus (B) projekce ceny hodnot pro každou proměnnou (C) smazání hodnot s cenou > UB i j i (í,2)(j,D (i,2)(j,2) (i, 2)0,3) (i, 2) Hana Rudová, Omezující podmínky, 4. prosince 201 8 239 Optimalizace & soft omezení: algoritmy Prohledávání ruská panenka (Russion doll search) M n po sobě jdoucích BB prohledávání, každé má navíc jednu proměnnou ........ „ statické uspořádání proměnných první podproblem obsahuje pouze n-tou proměnnou í-tý podproblem obsahuje posledních i proměnných ((n - i + 1)... n) & podproblémy řešeny pomocí BB s využitím LB a UB z předchozích běhůl Při řešení podproblému (n - i + 1) M problém zahrnuje proměnné XuXt+i,...,xn I mějme částečné přiřazení pro tento podproblem (au clí+u ■ ■ ■ > &í+j) s nepřiřazenými proměnnými Xí+j+i, xnl M do dolní meze lze zahrnout optimální cenu (n-í- j) podproblému optim(Xi+j+i,xn) & LB((auai+i,...,ai+j)) = dist((auai+i,... ,ai+j)) + optim(xi+j+i,... ,xn) dist{{auat+i,at+j)) vzdálenost (součet vah omezení na minulých proměnných) optimální řešení přechozích problémů použita pro: výběr hodnoty, pro zlepšení iniciální horní mezel 3 Vnořená prohledávání se vyplatí vzhledem k prořezání stavového prostoru Hana Rudová, Omezující podmínky, 4. prosince 2018 240 Optimalizace & soft omezení: algoritmy Opakování Vzorové písemné práce 2 vzorové písemné práce na webu předmětu Struktura písemné práce: 7 otázek 1. 1 přehledová otázka 2. otázky na propagaci a konzistenční algoritmy 3. otázky na stromové prohledávání prohledávání 4. otázky na lokální prohledávání a optimalizace 5. 1 otázka na řešení problému v OPL Hlavní typy otázek pro 2,3,4 3 příklady k vypočítání (jako vzorové příklady - někdy kratší verze) pojem (a příklad) kód algoritmu (a příklad) 3 porovnání pojmů/algoritmů (a příklady) Hana Rudová, Omezující podmínky, 4. prosince 201 8 242 Opakování Příklady s řešeními na webu I. Příklady 1. M binarizace 3 AC-1 vs. AC-3 & konzistence mezí vs. hranová konzistence Příklady 2. strom stavového prostoru: backtracking vs. kontrola dopředu vs. pohled dopředu Příklady 3. & omezení s váhami Příklady 4. & přehled konzistenčních algoritmů M algoritmus AC-4 & algoritmus DAC Hana Rudová, Omezující podmínky, 4. prosince 201 8 243 Opakování Příklady s řešeními na webu II Příklady 5. 3 strom stavového prostoru: backtracking vs. kontrola dopředu 3 pohled zpět: Gaschnigův skok zpět Příklady 6. 3 přehled prohledávacích algoritmů 3 problém rozvrhování výuky v OPL Příklady 7. 3 binarizace 3 podpora hodnoty 3 konzistence mezívs. hranová konzistence 3 algoritmus DAC, nalezení řešení bez navracení Hana Rudová, Omezující podmínky, 4. prosince 201 8 244 Opakování Příklady s řešeními na webu III. Příklady 8. & strom stavového prostoru: backtracking vs. kontrola dopředu vs. pohled dopředu & problém plánování projektu v OPL Příklady 9. & stromový CSP, nalezení řešení bez navracení algoritmus PC-2 I M problém rozvrhování výuky jedné místnosti v OPL strom stavového prostoru: kontrola dopředu vs. pohled dopředu bez iniciální konzistence & rozvrhování úkolů pro zaměstnance na směny Domácí úkol 1 M nalezení podpory M algoritmus DAC a nalezení řešení bez navracení M problém přiřazení poboček k obchodům v OPL Hana Rudová, Omezující podmínky, 4. prosince 2018 245 Opakování Pojem: směrová konzistence a šířka grafu Co to je šířka grafu a jaký je její význam? Použité pojmy objasněte. Šířka grafu je minimum z šířek všech jeho uspořádaných grafů. Šířka uspořádaného grafu je maximum z šířek jeho vrcholů. Šířka vrcholu v uspořádaném grafu je počet hran vedoucích z tohoto vrcholu do předchozích vrcholů. Uspořádaný graf je graf s lineárním uspořádáním vrcholů. Šířka grafu nám říká, jak silnou úroveň směrové i-konzistence potřebujeme, abychom nalezli řešení problému bez navracení. Hana Rudová, Omezující podmínky, 4. prosince 201 8 246 Opakování Algoritmus: lokální prohledávání M Napište (nebo alespoň slovně popište) algoritmus prohledávání s tabu seznamem. Je Váš algoritmus kombinován s nějakou další metodou lokálního prohledávání? proceduře TSHC(MaxZmen) 6 : = náhodné ohodnoceni proměnných % iniciál ní přiřazení PocetZmen := 0 while E(0) > 0 a PocetZmen do tabu seznamu, kde c je současná hodnota V smaž nejstarší položku v tabu seznamu při řad' a do V PocetZmen := PocetZmen+1 return 0 Algoritmus je kombinován s metodou stoupání/hill climbing. Hana Rudová, Omezující podmínky, 4. prosince 201 8 247 Opakování Příklady stručněji: omezení s váhami Jaká je úroveň konzistence pro následující CSP problém s váhami s omezeními cl a c2? P=({cl,c2},{X,Y}) dom(X)=dom(Y)={r,s} con(cl)={X,Y} def(r,r)=l, def(r,s)=2, def(s,r)=4, def(s,s)=6 con(c2)={Y} def(r)=0, def(s)=l Výsledek: blevel(P)=l. Nutno uvést stručný postup, např. I Spočítáme (ci ® C2) ^0 0 = = min(/^Cl 0C2 (r, r), /jc] ®C2 (r, s), /jc] ®C2 (s, r), /jc] ®C2 (s, s)) =1 = min(l + 0,2 + 1,4 + 0,6 + 1) = 1 Hana Rudová, Omezující podmínky, 4. prosince 201 8 248 Opakování Příklady stručněji: omezení s váhami II A jaká je úroveň splnění pro problém Pl =({cl ,c2},{Y})? výsledek: úroveň splnění pro Y=r: 1, pro Y=s: 3, postup:! Spočítáme (ci c2) tty (r) = min(jUCl®C2(r, r),jUCl®c2(s,r)) = min(l + 0,4 + 0) = 1 (ci c2) ^Y (s) = min(jUCl0C2(r,s),iUc10c2(s,s)) = min(2 + 1,6 + 1) = 31 | P=({cl,c2},{X,Y}) dom(X)=dom(Y)={r,s} con(cl)={X,Y} def(r,r)=l, def(r,s)=2, def(s,r)=4, def(s,s)=6 con(c2)={Y} def(r)=0, def(s)=l Hana Rudová, Omezující podmínky, 4. prosince 201 8 249 Opakování Doménové proměnné Celočíselné proměnné dvar int+ Sudoku: hodnota pole dvar int+ sudoku[l ..Size][l ..Size] in 1 ..Size;l forall (i in 1 ..Size) allDifferent(all (j in 1 ..Size) sudoku[i][j]); //ruzne pro kazdy radek I 3 přiřazení pracovníků:pracovník vyrábí produktl dvar int+ W[l ..nbWorkers] in 1 ..nbProducts;! total == sum (w in 1 ..nbWorkers) effectivity[w][W[w]];l Binární proměnné dvar boolean problém baťohu: je předmět v baťohu?ldvar boolean take[l ..nbltems];! sum (i in Items) (take[i] * weights [i]) <= capacity;! Sudoku: hodnota pole dvar boolean sudoku[l ..Size][l ..Size][l ..Size];l forall (i,k in 1 ..Size) sum (j in 1 ..Size) sudoku[i][j][k] == 1 ;l navíc: forall (i, j in 1 ..Size) sum(k in 1 ..Size) sudoku[i][j][k] == 1; Hana Rudová, Omezující podmínky, 4. prosince 2018 250 Opakování Rozvrhování: zdroje Jeden zdroj 3 jednotková doba trvání úlohy: dvar int, allDifferent(casy) odlišné doby trvání úloh: dvar interval, dvar sequence, noOverlap(casy)l Více zdrojů nepožadujeme určení zdroje pro úlohu I -i* bez doménových proměnných pro určení zdroje úlohy cumulFunction, pulse(casy[uloha], zdroju[uloha])l 3 požadujeme určení zdroje pro úlohu včetně doménových proměnných pro určení zdroje úlohy dvar interval přirazeni ... optional alternative(casy[uloha], ... prirazeni[uloha][zdroje], zdroju[uloha]) Hana Rudová, Omezující podmínky, 4. prosince 201 8 251 Opakování Rozvrhování Vztahy mezi úlohami a precedence endBeforeStart, endAtStart, ... tuple Závislost { int Pred; int Po; } {Závislost} závislosti = forall (zav in závislosti) endBeforeStart(casy[zav.Pred], casy[zav.Po]);l Volitelné úlohy presenceOf(dvar interval) dvar interval prirazeni[1..Uloh][1..Strojů] optional;l forall (u in L.Uloh, s not in mozne[u] ) presenceOf( pri razeni [u] [s] ) == 0; forall (u in L.Uloh, s in pri kazane [u]) presenceOf( pri razeni [u] [s] ) == l;l Dovolená: práce lidí se nepřekrývá s jejich dovolenoul řešení: přidáme dodatečné intervalové proměnné dvar interval casy[u in 1..Prace+Dovolenel size trváni[u]; forall (u in 1..Prace+Dovolene) noOverlap(casy);l cumulFunction nástroje = sum (p in 1..Prače) pulse( casy[p],nástrojů[p] ); Hana Rudová, Omezující podmínky, 4. prosince 2018 252 Opakování Optimalizace Problém baťohu: maximalizace součtu cen předmětů v baťohul maximize sum (i in nbltems) (take[i] * pricesfi] );l Minimalizace času dokončení poslední úlohyl minimize sum (u in 1 ..Počet) endOf( casy[u]); zadány poslední operace úlohy:! minimize sum (u in 1 ..Počet) endOf( casy[u][Posledni] );l Maximalice (váženého) počtu realizovaných úlohl maximize sum (u in 1 ..Počet) (vahy[u] * presenceOf(casy[u])); Hana Rudová, Omezující podmínky, 4. prosince 2018 253 Opakování Určete čas a místnost pro výuku množiny předmětů. Datová instance: 1. rozvrh tvoříte pro 3 vyučovací dny a každý den má 10 hodin 2. máte zadáno 14 předmětů 3. délka výuky předmětu je 4 nebo 5 hodin (určeno pro každý předmět předem) 4. máte k dispozici 3 místnosti 5. máte zadány 3 třídy (skupiny žáků) 6. každá třída má v zadání určeno 4 až 5 předmětů, které bude navštěvovat Omezující podmínky: 7. výuka předmětu musí probíhat souvisle bez přerušení (tj. nesmí např. začínat jeden den večer a končit druhý den ráno) 8. v každé místnosti je nejvýše jeden předmět v danou dobu 9. pro každou třídu je zadána množina jejích předmětů; každá třída může mít vždy nejvýše jeden z těchto předmětů v danou dobu Účelová funkce: 10. Jednotlivé předměty by měly být do rozvrhu umístěny tak, aby výuka všech tříd skončila co nejdříve (např. třetí den dopoledne). Tj. minimalizujte součet koncových časů výuky posledních předmětů všech tříd. Hana Rudová, Omezující podmínky, 4. prosince 2018 254 Opakování Školní rozvrh: vstupní proměnné i nt Dny = 3; int Hodin = 10; int Predmetu = 14; int Mistnosti = 3; int Tridy = 3;l range rTridy = 1..Tridy; range rMistnosti = 1..Mistnosti;l I tupl e predmetyTrid{ key int predmet; int trida; i nt trvani;} // napr. trida 1 ma predmety 1,2,3; trida 2 ma predmety 4,5, ... // predmety 1,2,3,4,5 maji trvani 4,4,5,5,4 // predmet je klic, tj. napr. <2> odkazuje na cely tuple <2,1,4> {predmetyTrid} PredmetyTrid = {<1,1,4>,<2,1,4>,<3,1,5>,<4,2,5>,<5,2,4>,...}; Hana Rudová, Omezující podmínky, 4. prosince 2018 25 5 Opakování Školní rozvrh: model Doménové proměnnél // přiřazeni času předmětům v maximálním rozmezi Dny*Hodin, zajištěni trváni dvar interval casy[p in PredmetyTrid] in 0 .. Dny*Hodin size p.trváni;l // volitelný interval pro přiřazeni předmětů a třid do mistnosti dvar interval při razeni[PredmetyTrid][rMistnosti] optional;l Každý předmět je vyučován právě v jedné místnosti I forall(p in PredmetyTrid) alternative(casy[p.předmět], all(m in rMistnosti) prirazeni[p] [m]);l V každé místnosti je nejvýše jeden předmět v danou dobul // sekvence rozvrhu mistnosti z důvodu nepřekrýváni dvar sequence rozvrhMistnosti[m in rMistnosti] in all (p in PredmetyTrid) prirazeni[p][m]; forall(m in rMistnosti) noOverlap(rozvrhMistnosti[m]); Hana Rudová, Omezující podmínky, 4. prosince 201 8 256 Opakování Školní rozvrh: model II Každý předmět je vyučován pro konkrétní třídu (skupinu žáků), tj. pro každou třídu je zadána množina jejích předmětů // sekvence rozvrhu tříd z důvodu nepřekrýváni dvar sequence rozvrhTridy[t in rTridy] in all (m in rMistnosti, p in PredmetyTrid : p.trida == t) pri razeni [p] [m]; a tedy každá třída může mít vždy nejvýše jeden předmět v danou dobul f orali (t in rTridy) noOverlap(rozvrhTridy[t]);l Výuka předmětu musí probíhat bez přerušeníl forali (p in PredmetyTrid) startOf(casy[p]) % Hodin <= (Hodin-p.trváni); alternativně: forali (p in PredmetyTrid) endOf(casy[p]) % Hodin <= Hodin; Hana Rudová, Omezující podmínky, 4. prosince 2018 257 Opakování Školní rozvrh: optimalizace Jednotlivé předměty by měly být do rozvrhu umístěny tak, aby výuka všech tříd skončila co nejdříve (např. třetí den dopoledne). Tj. minimalizujeme součet koncových časů výuky posledních předmětů všech tříd.l I // čas konce posledního předmětu každé třídy dexpr int maxTridy[t in rTridy] = max(p in PredmetyTrid : p.trida == t) endOf(casy[p]); // součet koncových časů poslednich hodin všech třid minimize sum(t in rTridy) maxTridy[t]; Hana Rudová, Omezující podmínky, 4. prosince 201 8 258 Opakování Rozvrhování úkolů pro zaměstnance na směny Je zadán počet dnů a počet zaměstnanců, kteří každý den pracují najedná směně. Všechny směny jsou stejně dlouhé a nepřekrývají se. Každý zaměstnanec má přitom určeno předem, kdy jeho směna během dne začíná, a každý zaměstnanec pracuje každou směnu právě na jednom z několika alternativních úkolů. Pro každý úkol máme určeno: I jakou má preferenci, 3 maximální počet hodin, který na něm může každý zaměstnanec za celou dobu pracovat, maximální počet zaměstnanců, kteří můžou na úkolu pracovat zároveň. Přiřaďte úkol každé směně zaměstnance tak, aby byly minimalizován součet preferencí realizovaných hodin úkolů za celou dobu. Hana Rudová, Omezující podmínky, 4. prosince 201 8 259 Opakování Směny: data Počet dnů 5 Délka dne: 24 Délka směny: 8 Počet zaměstnanců: 9 3 Počáteční čas směny pro jednotlivé zaměstnance: 6, 6,14,14, 6, 14,6, 14,6 úkol 12 3 4 preference max. počet hodin max. počet zaměstnanců 12 3 4 8 16 8 16 12 12 Hana Rudová, Omezující podmínky, 4. prosince 201 8 260 Opakování Směny: vstupní proměnné int pocetZamestnancu = i nt pocetDnu = ...; i nt pocetUkolu = ...; i nt trvani = ...; range Zamestnanci = 1..pocetZamestnancu; range Dny = 1..pocetDnu; range Ukoly = 1..pocetUkolu;l tuple Ukol { key int id; int pocet; int hodin; int preference; } tuple Zamestnanec { key int id; int od; } I Ukol ukoly[Ukoly] = . . . ; Zamestnanec zamestnanci[Zamestnanci] = ...; Hana Rudová, Omezující podmínky, 4. prosince 201 8 261 Opakování Směny: model Doménové proměnnél dvar interval casy[z in Zaměstnanci][d in Dny] in zaměstnanci [z].od .. (zaměstnanci[z].od+trvani) size trváni;l dvar interval přirazeni [z in Zaměstnanci] [d in Dny] [u in Úkoly] optional ;l Každou směnu pracuje zaměstnanec na jednom z úkolůl I forall (z in Zaměstnanci, d in Dny) alternative(casy[z][d], all (u in Úkoly) prirazeni [z] [d] [u]);l Minimalizace součtu preferencí realizovaných úkolůl minimize sum (z in Zaměstnanci, d in Dny, u in Úkoly) presenceOf(pri razeni[z][d][u])*ukoly[u].preference; Hana Rudová, Omezující podmínky, 4. prosince 201 8 262 Opakování Směny: model (dokončení) Každý zaměstnanec pracuje na jednom úkolul cumulFunction pocetUkol[u in Úkoly] [d in Dny] = sum (z in Zamestnanci) pulse(prirazeni[z][d][u],1); a počet zpracovávání každého úkolu zároveň je omezeni forall (u in Úkoly, d in Dny) pocetUkol [u] [d] <= úkoly[u].počet;l Každý úkol zpracovává zaměstnanec po dobu jeho trvání cumulFunction hodinUkol[u in Úkoly] [z in Zamestnanci] = sum (d in Dny) pulse(prirazeni[z][d][u],trváni);l a počet hodin je pro každý úkol zaměstnance omezeni forall (z in Zamestnanci, u in Úkoly) hodinUkol[u][z] <= úkoly[u].hodin; Hana Rudová, Omezující podmínky, 4. prosince 201 8 263 Opakování Zdroje, ze kterých průsvitky čerpají V průsvitkách jsou použity obrázky a texty z uvedených zdrojů: & Barták R., MFF UK, Praha. Průsvitky k přednášce Programování s omezujícími podmínkami http://kti .ms.mff .curii .cz/~bartak/podminky/prednaska.html Apt K., CWI, Holandsko. Průsvitky ke knize Principles of Constraint Programming http://homepages . cwi . nl/-apt/books . html Dechter R., University of California, USA. Průsvitky ke knize Constraint processing http://www.i es.uci.edu/~dechter/books/material s.html Laborie P., Introduction to CP Optimizer for Scheduling. Tutoriál prezentovaný na 27th International Conference on Automated Planning and Scheduling, 201 7. http://icapsl7.icaps-conference.Org/tutorials/#tut3 Hana Rudová, Omezující podmínky, 4. prosince 201 8 264 Zdroje