PA163 Programovaní s omezujícími podmínkami podzim 201 9 Základní informace Web předmětu: na IS průsvitky průběžně na ISu (interaktivní osnova, učební materiály) M 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: 80 bodů M cca 7 otázek: přehledové, srovnávací, algoritmy, pojmy, příklady (model) cca 25 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: 20 bodů ±> za jednu domácí úlohu lze získat až 1 0 bodů J* podmínkou je získání alespoň 8 bodů z celkového počtu 20 bodů za D.Ú. bonusové body: cca 12 bodů -t 1 bod za aktivní účast na přednášce hodnocení: A více než 90, B 89-80, C 79-70, D 69-60, E 59-50 Hana Rudová, Omezující podmínky, 16. prosince 2019 2 Organizace předmětu Literatura Dechter, R. Constraint processing. Morgan Kaufmann Publishers, 2003. * http://www.ics.uci.edu/~dechter/books/ Tsang, E. Foundations of Constraint Satisfaction. Academic Press, 1993. http://www.braci1.net/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. http://kti.ms.mff.cuni.cz/~bartak/podminky/index.html Elektronické materiály viz web předmětu Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 3 Organizace předmětu Přehled přednášky Úvod Konzistenční algoritmy Prohledávací algoritmy I Optimalizační problémy a řešení Opakování v příkladech Omezující podmínky v navazujících přednáškách: 3 PA1 67 Rozvrhování Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 4 Organizace předmětu Cvičení Účast na cvičeních povinná v případě více než jedné absence nutné zpracovat doplňující příklady * při vysokém počtu absencí na cvičení předmět absolvovat nelze 3 Cíl 3 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, 1 6. prosince 201 9 5 Organizace předmětu Software: IBM ILOG CPLEX Optimization Studio 3 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ů 3 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í https://www.i bm.com/analyti cs/opti mi zati on-modeli ng Tutoriály a dokumentace ve Studijních materiálech https://i s.muni.cz/auth/el/1433/podzi m2019/PA163/i1og/IL0G02_cou rse.zi p Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 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; I 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; }; Hana Rudová, Omezující podmínky, 16. prosince 2019 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, 1 6. prosince 201 9 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, 16. prosince 2019 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, 1 6. prosince 201 9 Ú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, 1 6. prosince 201 9 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, 1 6. prosince 201 9 13 Úvod do CP Propagace v bloku: vstup 8 6 3 Žádné pole v bloku nemůže obsahovat čísla 3,6,8 Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 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 Žádné pole v bloku nemůže obsahovat čísla 3,6,8 propagace do dalších polí v bloku m Řádky a sloupce: podobně Hana Rudová, Omezující podmínky, 16. prosince 2019 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, 1 6. prosince 2019 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, 1 6. prosince 201 9 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, 1 6. prosince 201 9 1 8 1,3,6,7 Ú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, 1 6. prosince 201 9 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, 16. prosince 2019 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 3 mají hodnoty: čísla ' udržování množiny možných čísel Omezení: vyjadřují odlišnosti S relace mezi proměnnými Modelování: proměnné, hodnoty, omezení Řešení: propagace, prohledávání Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 21 Úvod do CP Dána Omezení (constraint) M množina (doménových) proměnných Y = {yi,... ,yk} M 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 3 omezuje hodnoty, kterých mohou proměnné nabývat současně I 3 Příklad: I M 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 3 Omezení c definováno na proměnných yi,.. .yk je splněno, pokud pro hodnoty d\ e Di, ...dk £ Dk platí (d\,... dk) e c M 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, 1 6. prosince 201 9 22 Úvod do CP Problém splňování podmínek (CSP) 3 Dána 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 Příklad: proměnné: A, B, C -•domény: A e {0,1} B = l C e {0,1,2} 3 omezení: A =/= B B =/= C Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 23 Úvod do CP Řešení CSP 3 Částečné ohodnocení (přiřazení) proměnných (di,dk),k < n M některé proměnné mají přiřazenu hodnotu 3 Úplné ohodnocení (přiřazení) proměnných (d\,..., dn) 3 všechny proměnné mají přiřazenu hodnotu I Řešení CSP I M úplné ohodnocení proměnných, které splňuje všechna omezení (di,...,dn) g Di x ... x Dn je řešení (X,D,C) 3 pro každé q e C na x^,.. .xtk platí (d^,... dtk) ecj 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 problém) Hana Rudová, Omezující podmínky, 16. prosince 2019 24 Úvod do CP Přístup CP k programování 3 Formulace daného problému pomocí omezení: modelování Řešení vybrané reprezentace pomocí 3 doménově specifických metod obecných metod Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 25 Úvod do CP Obecné metody 3 Algoritmy propagace omezení (konzistenční algoritmy) umožňují odstranit nekonzistentní hodnoty z domén proměnných M zjednodušují problém M udržují ekvivalenci mezi původním a zjednodušeným problémem používají se pro výpočet lokální konzistence I M 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 m Prohledávací algoritmy prohledávání stavového prostoru řešení příklady: backtracking, metoda větví a mezí Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 26 Úvod do CP Prohledávání: příklad Prohledávání pomocí větvení 3 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, 1 6. prosince 201 9 27 Úvod do CP Doménově specifické metody 3 Specializované algoritmy Nazývány řešiče omezení (constraint solvers) 3 Příklady: program pro řešení systému lineárních rovnic knihovny pro lineární programování implementace unifikačního algoritmu I Programování s omezujícími podmínkami široký pojem zahrnující řadu oblastí 3 lineární algebra, globální optimalizace, lineární a celočíselné programování, ... Existence doménově specifických metod => použití místo obecných metod 3 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, 16. prosince 2019 28 Úvod do CP Algebrogram m Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platil 3 SEND + MORE MONEY různá písmena mají přiřazena různé cifry i SaM nejsou 0 Jediné řešení: 9567 + 1085 10652 Proměnné:IS,E,N,D,M,0,R,Y Domény: 1 ..9 pro S,M 0..9 pro E,N,D,0,R,Y Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 29 Algebrogram: alternativy pro omezení rovnosti 3 1 omezení rovnostil 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, 1 6. prosince 201 9 30 Úvod do CP Algebrogram: alternativy pro omezení nerovnosti i 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, 1 6. prosince 201 9 31 Úvod do CP Optimalizační problém s podmínkami (COP) 3 Problém splňování podmínek (X, D, C) Účelová funkce obj : Sol — 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 i* optimální = maximální nebo minimálni Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 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,..., cn m ProměnnéJxi,... ,xn m Domény:l0..1 n 3 Omezení:!^ Ví.Xí < m i=l n Účelová funkce:lmaximize ^ CíXí i=l Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 33 Úvod Aplikace: přehled Operační výzkum 3 optimalizační problémy 3 rozvrhování, plánování, alokace zdrojů Zpracování přirozeného jazyka 3 konstrukce parserů Počítačová grafika geometrické vztahy při analýze scény 3 Databáze 3 obnovení/zajištění konzistence dat Molekulární biologie 3 DNA sekvencování 3 ... Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 34 Příklad aplikace z MU: univerzitní rozvrhování [ Timetabling - Mozilla Firefox □as 1 File Edit View History Bookmarks Tools Help 1 x_ * Y http5://v\mw.5ma5.purdue.edu/rmetabling/selectPrimaryRole.do al'l M IE-Google Kl a Filter Timetable PHY S 112 (268) M on 7:30a ENGR 126RLec 1 4 54 11:00a 11:30a 12:00p OLS 252 Lec 1 15 1 3 ^^^^^M MA 154 Lec 2 OLS 274 Lec 3 10 24 1 PHYS221Lec1 PHYS241Lec1 PHYS 241 Lec 2 PHYS 241 Lec 3 4 54 OLS 274 Lec 1 MA 154 Lec 2 OLS 274 Lec 3 PHYS 219 Lec 1 10 24 1 CGT163LabP2 4 5 4 ANTH 205 Lec 1 ENGR 100H Lec 1a MA 165 Lec 5 16 61 4 6 15 Weekl ENGR 100H Lec 1b 4 6 Week 4 ENGR 100H Lec 1 HYS 241 Lec 2 PHYS 241 Lec 3 www.smas.purdue.edu ^ Proxy: None 4$ © 0 I rozvrhovací systém Unitime http://www.unitime.org International Timetabling Competition 2019 co-organized by Fl MU: https://www.itc2019.org Hana Rudová, Omezující podmínky, 16. prosince 2019 35 Úvod do CP Univerzitní rozvrhování: proměnné a omezení Doménové proměnné 3 čas výuky předmětu I: Timel, hodnoty: možné časy místnost výuky předmětu I: Rooml, hodnoty: identifikátory místností I Omezující podmínky zakázaný čas: Timel ^ Prohibited I minimální velikost místnosti: Rooml > ConstSize identifikátory místností uspořádány podle velikosti * 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 m ... Hana Rudová, Omezující podmínky, 16. prosince 2019 36 Úvod do CP Univerzitní rozvrhování: optimalizace Optimalizační kritéria 3 výuka v preferovaných časech 3 cena za výuku předmětu I ve vybraném čase: CostTimel CostTime = CostTimel + CostTime2 + ■ ■ ■ I výuka v preferovaných místnostech I 3 cena za výuku předmětu I ve vybraném čase: CostRooml 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ů 3 CostOverlap = ^ SIJ I IJ: timeOverlap(IJ) minimize (WTime * CostTime + WRoom * CostRoom + WOverlap * CostOverlap) Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 37 Úvod do CP Polynomiální a NP-úplné problémy Polynomiální problémy 3 existuje algoritmus polynomiální složitosti pro řešení problému NP-úplné problémy S řešitelné nedeterministickým polynomiálním algoritmem 3 potenciální řešení lze ověřit v polynomiálním čase 3 v nejhorším případě exponenciální složitost (pokud neplatí P=NP) Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 38 Úvod do CP Složitost: polynomiální problémy Lineární rovnice nad reálnými čísly 3 proměnné nad doménami z R, omezení: lineární rovnice 3 Gaussova eliminace M 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, 1 6. prosince 201 9 39 Úvod do CP Složitost: NP-úplné problémy Boolean omezení 3 0/1 proměnné omezení = Boolean formule (konjunkce, disjunkce, implikace, ...) -i* příklad: proměnné A,B, C, omezení (A v B), (C => A), CSP problém (A v B) a (C => A) I problém splnitelnosti Boolean formule (SAT problém): NP-úplný n proměnných:l2n možností I Omezení nad konečnými doménami 3 obecný CSP problém problém splnitelnosti nad obecnými relacemi NP-úplný problém n proměnných, d maximální velikost domény:ldn možností Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 40 Úvod do CP Složitost a úplnost «• Úplné vs. neúplné algoritmy ú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 «• příklad: neúplný polynomiální algoritmus pro NP-úplný problém I m Složitost řešiče I Gaussova eliminace (P), SAT řešiče (NP), obecný CSP řešič (NP) 3 Složitost algoritmů propagace omezení M většinou polynomiální neúplné algoritmy I 3 Složitost prohledávacích algoritmů M ú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, 16. prosince 2019 41 Úvod do CP Grafová reprezentace CSP Reprezentace podmínek * intenzionální (matematická/logická formule) 3 extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) I Graf: vrcholy, hrany (hrana spojuje dva vrcholy) Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholů) Reprezentace CSP pomocí hypergrafu podmínek vrchol = proměnná, hyperhrana = podmínka I c1 Příklad proměnné Xi,...,X6 s doménou {0,1 } omezení c\ : X\ + x 2 + Xq = = 1 /X 1 0 ■ ^í/l C2 : X\ - X3 + X4 = = 1 0, 1 0, 1 0, 1 | 0,1 0, 1 | | 0, 1 | C3 : X4 + Xs - Xq > 0 C4 : X2 + Xs - Xq = 0 Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 I Úvod do CP Binární CSP Ä Binární CSP 3 CSP, ve kterém jsou pouze binární podmínky M 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 3 dva CSP problémy jsou ekvivalentní, pokud mají stejnou množinu řešení 3 Rozšířená ekvivalence CSP M řešení problémů lze mezi sebou „syntakticky" převést např: obecný CSP převedeme na binární CSP a porovnáme tyto binární CSP Hana Rudová, Omezující podmínky, 16. prosince 2019 43 Úvod do CP Duální problém Duální problém: původním omezením odpovídají nové duální proměnné 3 proměnné: fc-ární podmínku Ci převedeme na duální proměnnou Ví s doménou obsahující konzistentní fc-tice 3 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 Příklad proměnné Xi,... ,Xq s doménou {0,1} omezení c\ : X\ + X2 + Xq = 1... v\ C2 : X\ - X3 + X4 = 1... V2 C3 : X4 + Xs - Xq > 0... V3 C4 : X2 + Xs - Xq = 0... V4 (0,0,1), (0,1,0), R21 & R33 (1,0,0) R11 (0,0,1), (1,0,0), (1,1,1) R31 (0,0,0), (0,1,1), (1,0,1) R22 & R33 (0,1,0), (1,0,0), (1,1,0), (1,1,1) Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 44 Úvod do CP Použití binarizace Konstrukce duálního problému jedna z možných metod binarizace Výhody binarizace S získáváme unifikovaný tvar CSP problému M řada algoritmů navržena pro binární CSP 3 pro výukové účely je vysvětlení na binárních CSP vhodné ±> algoritmy jsou přehlednější a jednodušší na pochopení ±> 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 složitější propagační algoritmy 3 lze využít jejich sémantiky pro lepší propagaci 3 příklad: al l_di f f erent vs. množina binárních nerovností Hana Rudová, Omezující podmínky, 16. prosince 2019 45 Úvod do CP Hranová konzistence Propagace omezení 3 Příklad: 3 proměnné: A,B,C -•domény: A g {0,1} B=0 C g {0,1,2,3} 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, 1 6. prosince 201 9 47 Hranová konzistence Vrcholová konzistence 3 Vrcholová konzistence (node consistency) NC 3 unární podmínky převedeme do domén proměnných Vrchol reprezentující Vije vrcholově konzistentní: 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í: každý jeho vrchol je vrcholově konzistentní Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 48 Hranová konzistence Hranová konzistence (Arc Consistency AC) Pouze pro binární CSP (až její rozšíření jsou pro nebinární CSP) 3 podmínka odpovídá hraně v grafu podmínek více podmínek na jedné 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í, V/) nezaručuje konzistenci hrany (V/, 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, IAB, BA, BC, CB, IAB, BA, BC, CB Hana Rudová, Omezující podmínky, 16. prosince 2019 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 ' Složitost 0(enk3) I cyklus přes všechny hrany 0(e) I revi se 0(k2) I 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, 16. prosince 2019 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 (Í2>k) (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 3 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, 16. prosince 2019 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 proceduře 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) 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 Technika AC-3 je dnes asi nejpoužívánější, ale stále není optimální Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 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. 3 Nyní musíme prozkoumat doménu V3, zda některá z hodnot a, b, c, d neztratila svoji podporu ve V2.1 3 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} 3 a g D2 má podpory {(3, a), (3, b), (3, d)} 3 d g D3 má pouze jedinou podporu {{2, a)} 3 b g D2 má podpory {(1,a), (1, c), (3, a), (3, c)} I m Podpory spočítáme jen jednou. Při opakovaných revizích je budeme používat. Hana Rudová, Omezující podmínky, 16. prosince 2019 56 Hranová konzistence Algoritmus na inicializaci podpor m 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 & Udržujeme počet vlastních podpor (víme, co nám chybí). counter[(í, j), a]: počet podpor, které má hodnota a e Dt u proměnné V j procedure initial i ze (G) Q := {}, S := {} // vyprázdněni datových struktur for each (Ví, V)) 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 D{ Q := Q u i(í,a)} return Q // Q je fronta se smazanými hodnotami Hana Rudová, Omezující podmínky, 16. prosince 2019 57 Hranová konzistence Aktualizace podpor během výpočtu Situace po zpracování hrany (Ví, V}) algoritmem initialize counter^ j} i 2 a1 — 2 a2^ 1 a3 , , 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). j , ^b2 I Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 58 Hranová konzistence Algoritmus AC-4 procedure 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 Di Q := Q u {<í,a>} I Složitost 0(ek2) => algoritmus optimální v nejhorším případě M 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, 1 6. prosince 201 9 59 Hranová konzistence Další AC algoritmy 3 Existuje řada dalších algoritmů pro zajištění hranové konzistence AC-5, AC-6, AC-7, ... AC-6 (Bessiěre, Cordier) 3 zlepšuje paměťovou náročnost a průměrný čas AC-4 3 drží si pouze jednu podporu, další podpory hledá až při ztrátě aktuální podpory I AC-3.1: AC-3 hledá podpory vždy od začátku, jak to vylepšit? 3 AC-2001: AC-3 s frontou proměnných místo fronty omezení 3 Porovnání: 3 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, 16. prosince 2019 60 Hranová konzistence AC-3.1: optimální algoritmus AC-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í ' proceduře 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, 16. prosince 2019 61 Hranová konzistence AC-2001: jiný optimální algoritmus AC-3 proceduře 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) g 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 if 3y G D/ a y > las t {{í, x), j) a (x,;y)GCij 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, 1 6. prosince 201 9 62 Hranová konzistence Je hranová konzistence dostatečná (úplná)? 3 Použitím AC odstraníme mnoho nekompatibilních hodnot 3 Dostaneme potom řešení problému? NE S Víme alespoň zda řešení existuje? NE I m X,Y,Z g {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 3 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, 1 6. prosince 201 9 63 Hranová konzistence Konzistence po cestě Konzistence po cestě (PC path consistency) 3 Příklad: X,Y,Z e {1,2}, X ± Y, Y + Z, Z + X 3 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, Vj+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, 1 6. prosince 201 9 65 Konzistence po cestě PC a cesty délky 2 Zjišťování konzistence všech cest není efektivní Stačí ověřit konzistenci cest délky 2 3 Věta: CSPje PC právě tehdy, když každá cesta délky 2 je PCI 3 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+i ii) vezmeme libov. dvě kompatibilní hodnoty Xo e D0 a xn+\ e Dn+i (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+i) jsou konzistentní iv) podle indukčního kroku najdeme zbylé hodnoty na cestě Vo, V\,..., Vni 3 Definici PC lze tedy upravit tak, že vyžadujeme pouze konzistenci cest délky 21 Hana Rudová, Omezující podmínky, 16. prosince 2019 66 Konzistence po cestě Vztah PC a AC ^ PC => AC pokud je cesta (í,j,í) konzistentní (PC), pak je i hrana (í, j) konzistentní (AC), tj. z PC tedy plyne AC ±> PC: ke každé „dvojici hodnot" pro í, i najdu hodnotu v j => AC: ke každé hodnotě v i tedy najdu hodnotu v ji * AC 4> PC 3 příklad: X,Y, Z e {1,2}, X^Y, Y^Z, Z^X 1 -i* je AC, ale není PC, zdůvodnění: Í=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? M PC vyřazuje dvojice hodnot M PC si pamatuje podmínky explicitně PC si pamatuje, které dvojice hodnot jsou v relaci PC dělá všechny relace nad dvojicemi implicitní (A A+1 již zrevidované cesty opět nekonzistentní M 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 Ríj pomocí existujících binárních (i unárních) podmínek ' proceduře PC-l(G) repeat Changed := falše fór m : = 1 to n f or í : = 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, 16. prosince 2019 70 Konzistence po cestě Složitost algoritmu PC-1 Celková složitost 0(n5k5) odvození podobné jako proAC-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 3 opakovaná revize všech cest, i když pro ně nedošlo k žádné změněl s, při revizi stačí kontrolovat jen zasažené cesty podobně jako pro PC-il cesty stačí brát pouze s jednou orientací ... Rij je totéž co Rjt ± příklad: VUV2 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 Vi,V3 (V3, V\) hledám kompatibilní hodnotu z V2 Hana Rudová, Omezující podmínky, 16. prosince 2019 71 Konzistence po cestě Algoritmus PC-2 Cesty beru pouze s jednou orientací aktualizuji pouze jednu z Ríj, Rjí 3 Do fronty dávám pouze zasažené cesty podobná modifikace jako AC-3 M revi se-3(í, m, j) mění R^, Itačí tedy aktualizovat Ru přes j a Rij přes í Před spuštěním algoritmu M inicializovat relace Rtj pomocí existujících binárních (i unárních) podmínek 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, bylo redukováno alespoň o jednu hodnotu celkem n3 trojic (í,m,j) => 0(n3) ^ revise-3 0(fc3)l Algoritmus není optimální podobně jako AC-3 M existuje algoritmus PC-4 založen na počítání podpor 3 složitost PC-4 je 0(n3k3), což už je optimálníl 3 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 + 1,V2 ^ V3, VI ^ V2I ^ Nápověda: zkonstruuj iniciální relace Ríj iniciálně přidej do fronty (VI, V2, V3), (VI, V3, V2), (V2, VI, V3) Hana Rudová, Omezující podmínky, 16. prosince 2019 73 Konzistence po cestě Omezení PC algoritmů & Paměťové nároky 3 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él 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, 16. prosince 2019 74 Konzistence po cestě Na půli cesty od AC k PC 3 Jak oslabit PC, aby algoritmus: M neměl paměťové nároky PC neměnil graf podmínek 3 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é 3 Příklad: VuV2e {a,b},V3 e {a,b,c}, Vľ + V2,Vi + V3,Vi + V3 je AC ale není PC RPC odstraní z domény V3 hodnoty a, b Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 75 Konzistence po cestě Omezená konzistence po cestě (RPC) 3 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. M Proměnná Vije omezeně konzistentní po cestě (Restricted Path Consistent, RPC). M každá hrana vedoucí z Ví je hranově konzistentní pro každé a e Dí 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 3 Algoritmus: založen na AC-4 + seznam cest pro PC (viz Barták přednáška) Hana Rudová, Omezující podmínky, 16. prosince 2019 76 Konzistence po cestě Propagace pro nebinární omezení Nebinární omezení Zobecnění principů NC, AC, a PC směrem ke k-konzistenci 3 zajímavé z pohledu složitosti řešení problémů 3 pracuje se s libovolnými k-ticemi proměnných v praxi se vzhledem k paměťové a časové složitosti nevyužíval M Obecné typy konzistence pro nebinární podmínky 3 pracuje se přímo s n-árními podmínkami 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í 3 speciální typy konzistence pro globální omezení (př. all_different)l Pro různé podmínky lze použít různý druh konzistence 3 A k-konzistence I Silná k-konzistence => j-konzistence V j < k 3 k-konzistence ^> silná k-konzistencel NC = silná 1-konzistence = 1-konzistence 3 AC = (silná) 2-konzistence 3 PC = (silná) 3-konzistence M Cvičení: uveďte příklad problému, který je 4-konzistentní, ale není 3-konzistentní Hana Rudová, Omezující podmínky, 16. prosince 2019 81 Propagace pro nebinární omezení Konzistence pro nalezení řešení 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) M silná k-konzistence pro k všechna jeho omezení jsou obecně hranově konzistentní M Příklad (pokračování): po GAC dostaneme ^=1, B=0, C=l Hana Rudová, Omezující podmínky, 16. prosince 2019 85 Propagace pro nebinární omezení Konzistence mezí Bounds consistency BC: slabší než obecná hranová konzistence propagace pouze při změně minimální nebo maximální hodnoty v doméně proměnné M tedy došlo ke změně mezí domény proměnnél Konzistence mezí pro nerovnice M A > B=> min(A) > min(B)+l, max(B) < max(A)-l příklad: A g {4,..., 10}, Be {6,... 18}, A > B min(A) > 6+1 => A e {7,..., 10} max(B) < 10-1 => B g{6,...,9}I Cvičer napište pravidla pro konzistenci mezí pro uvedená omezení # A < B, A>B, 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 změna mi n (A) vyvolá pouze změnu mi n (B) amin(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 E {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 E {3,..., 6, 9,10}, B E {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, 16. prosince 2019 88 Propagace pro nebinární omezení Globální podmínky Globální podmínka: definována pro libovolný konečný počet proměnných Global Constraint Catalog http://sofdem.gi thub.i o/gccat/ Nicolas Beldiceanu, Mats Carlsson and Jean-Xavier Rampon 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, 16. prosince 2019 89 Propagace pro nebinární omezení (Globální podmínky a) rozvrhování 3 Všechny proměnné různé M all Different Disjunktivní zdroj/rozvrhování dvar interval, dvar sequence 3 noOverlap Kumulativní zdroj/rozvrhování cumuFunction, pulse Alternativní zdroje 3 alternative Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 90 Propagace pro nebinární omezení Všechny proměnné různé Proměnné v poli Array jsou různé dvar int Array[Interval]; 3 globální podmínka: al 1 Different(Array) ; M binární podmínky: for (i, j in Interval : i ! = allDifferent vs. binární podmínky 3 allDifferent má úplnou propagaci M binární podmínky mají slabší (neúplnou) propagaci Příklad: učitelé musí učit v různé hodiny I globální podmínka: Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr e{3,4}, Eva e {3,4} I 3 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, 1 6. prosince 201 9 91 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 Propagace pro nebinární omezení Naivní propagace pro all Different U = {Petr, Ota, Eva}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro Jan, Anna, Marie Jan g {5,6}, Anna = 5, Marie e {1,5,6}I Konzistence: musí platit: V{Xi,.. .,Xk} c V : card{Di u ■ ■ ■ u Dk} > k M Inferenční pravidlol M V: množina všech proměnných 3 U = {Xi,...,Xk}, dom(U) = {Di u ■ ■ ■ u Dk} 3 card(U) = card(dom(U)) => Vv e dom(U),\/X e (V - U),X + vl M hodnoty v dom(U) jsou pro ostatní proměnné nedostupné 3 Složitost 3 hledání všech podmnožin množiny n proměnných (naivní) 0(2n) Hana Rudová, Omezující podmínky, 16. prosince 2019 92 Propagace pro nebinární omezení učitel min max Jan 3 6 Petr 4 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) 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 v grafu neexistují dvě hrany, které by měly společný vrchol 3 Maximální párování párování, které má maximální počet hraní CSP jako bipartitní graf 3 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, 16. prosince 2019 93 Propagace pro nebinární omezení all Different - párování v bipartitních grafech II Inicializace sjednocení domén proměnné proměnných vypočti maximální párování * 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 ^0 vypočti nové maximální párování 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, 16. prosince 2019 94 Propagace pro nebinární omezení Intervalové proměnné Intervalová proměnná: pro modelování časového intervalu (úlohy, aktivity) hodnotou intervalové proměnné je celočíselný interval [start, end) 3 příklad: dvar interval x in 0..1000000 size 100..200; 0 [100,200] 1000000 F.........ľ - '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 3 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, 16. prosince 2019 95 Propagace pro nebinární omezení 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; 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, 16. prosince 2019 96 Propagace pro nebinární omezení 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 p^vní? 16 ■ B(4) 16 I r C(5) 15 Pro A,B,C není dost času, a tedy aktivita A musí být první 4h A(2) H 7 6h B(4) 16 Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 C(5) 15 97 Propagace pro nebinární omezení 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, 1 6. prosince 201 9 98 Propagace pro nebinární 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 logické binární podmínky: polynomiální složitost 3 precedence + logické binární: NP-těžké! Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 99 Propagace pro nebinární omezení 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, 1 6. prosince 201 9 100 Propagace pro nebinární omezení 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 Q 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] .men == m) op[j][p]; minimize max(j in Jobs) endOf(op[j] [nbPos]); subject to { tuple Oper { forall(m in Mchs) int mch; // Machine noOverlap(mchs [m] ) ; ■ „_._// n . .r _ , 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] = Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 101 př. 0ps[l] [2]=<3,6> Propagace pro nebinární omezení 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: M intervaly využívají počty pracovníků M intervaly využívají skladové zásoby I 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]; 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, 1 6. prosince 2019 102 1 0 X Time i Propagace pro nebinární omezení Příklad: RCPSP Resource-contrained project scheduling problem (RCPSP) tuple Task { key int id; i nt pt; int qty[Resources]; {int} succs; } {Task} Tasks = ... ; I R1 ■ R2 I I 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 forall(r in Resources) 7 usage[r] <= Capacity[r]; 8 forall(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, 1 6. prosince 201 9 103 Propagace pro nebinární omezení 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) M alternative(x, [yl,...,yn]) 3 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 3 alternative(x, [yl,...,yn], k) //k: celočiselný vyrazí Příklad použití: 3 každá intervalová proměnná x[t] vyžaduje nbWorkers[t] přítomných intervalů mezi assigned[t] [w] pro pracovníky w |kód ještě nutno rošířit o nepřekrývání pro pracovníky).! 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, 16. prosince 2019 104 Propagace pro nebinární omezení Konzistenční algoritmus pro nebinární podmínky 3 Obecný konzistenční algoritmus M Varianta AC-3 s frontou proměnných rozšíření AC-2001 na nebinární podmínky! Opakovaně se provádí revize podmínek, dokud se mění domény proceduře Nonbinary-AC-3-with-Variables(Q) while Q non empty do vyber a smaž V j e Q for V C takové, že V) e scope(C) do W : = revise (V/, C) // W je množina proměnných jejichž, doména se změnila i f 3 Vi G W taková, že Dt = 0 then return fail Q := Q u {W} end Nonbinary-AC-3-with-Variables Hana Rudová, Omezující podmínky, 16. prosince 2019 105 Propagace pro nebinární omezení 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í 3 konzistenční algoritmy pro globální podmínky jako allDifferent Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 106 Propagace pro nebinární omezení Revizní procedura 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) ±> při změně mezí (u konzistence mezí) X> 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 pro jednu podmínku lze mít více propagačních kódů Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 107 Propagace pro nebinární omezení Základní konzistenční algoritmus s událostmi -M 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 j e scope(C) a C čeká na event(Vj) do W : = revi se(event(Vj), C) // jsou vyvolány pouze ty revize, které čekají na danou event(Vj) // W je množina proměnných jejichž, doména se změnila if 3 Vi g W taková, že Di = 0 then return fail Q := Q u {W} end Nonbinary-AC-3-with-Events Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 108 Propagace pro nebinární omezení Směrová konzistence Směrová hranová konzistence (Probinárnícsp> CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (xi,... ,xn), právě když je každá hrana (xj,Xí) hranově konzistentní pro každé j < í. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC f or 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 = x\ ©white blue 4 black x3 red i white blue ©green white 4 black x1 red white black I Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} M 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 %x\, x2, x$, X4J Opakování revizí není nutné, lomena revidované proměnné se v dalších cyklech nemění Složitost 0(ek2) Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 každá hrana se reviduje jednou se složitostí 0(k2) 11 0 Směrová konzistence Směrová í-konzistence 3 Algoritmus pro DAC byl pouze pro binární CSP 3 í-konzistence vyžaduje uvažování omezení s větším rozsahem proměnných M 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, 1 6. prosince 201 9 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í DAC je definován pouze na binární CSP M 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) Algoritmus pro silnou směrovou konzistenci viz [Dechter, Constraint Processing] Hana Rudová, Omezující podmínky, 16. prosince 2019 112 Směrová konzistence Řešení bez navracení pomocí DIC-í 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í (xi,..., Xi) konzistentně rozšířeno o proměnnou atí+i.I 3 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 Pro i zpětných hran potřebujeme směrovou (í + l)-konzistenci 3 Je-li m maximum počtu zpětných hran pro všechny vrcholy, stačí nám silná směrovou (m + l)-konzistence 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, 1 6. prosince 201 9 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ů. Šířka uspořádaného grafu je maximum z šířek jeho vrcholů. Šířka grafu je minimum z šířek všech jeho uspořádaných grafů. -0 proceduře MinWidthOrdering((V,E)) Jkonstruujeme od konce)l 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, 16. prosince 2019 114 Směrová konzistence Graf podmínek s šířkou 1 = strom 3 Tvrzení: Graf je strom právě tehdy, když má šířku 1 J M 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 hranV| směřují z kořenového uzlu. \ 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 1 Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 11 5 Směrová konzistence Konzistence pro stromové CSP 3 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 3 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. 3 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 :wq {Xj,Xi+i) je hranově konzistentní (z DAC), tedy a existuje hodnota konzistentní se současným přiřazením Xj 3 tuto hodnotu přiřadíme Xí+i 10 Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 116 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) Cvičení: XI, X2.X3.X4 in 1..5, X1=X2+1, X1 Složitost algoritmu 0(nk2) M 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 nechť Xpd) označuje rodiče Xi v uspořádaném stromu for i = n to 1 by -1 do if Dpd) = 0 exit (řešeni neexistuje) end TreeSolving Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 11 7 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 dl 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: ±> musíme najít hodnotu kompatibilní se všemi již ohodnocenými proměnnými, které jsou s proměnnou spojené podmínkou (hranou) St 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) I Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 maximálna w 118 Směrová konzistence Adaptivní konzistence 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. Je tedy nutná směrová í-konzistence odpovídající šířce grafu? 3 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 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, 16. prosince 2019 119 Směrová konzistence Polynomiální CSP 3 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 ^ ADC není jen procedura pro rozhodnutí konzistence 3 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, 16. prosince 2019 120 Směrová konzistence Prohledávání a pohled dopředu Přehled prohledávacích algoritmů pro CSP 3 Rozšiřování částečného konzistentního přiřazení M stromové prohledávání 3 backtracking -i* pohled dopředu (propagace omezení) x pohled zpět (inteligentní vracení) 3 neúplná stromová prohledáváni 3 Procházení úplných nekonzistentních přiřazení 3 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, 1 6. prosince 201 9 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] 3 cílové stavy: úplná řešení I Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 č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í. v grafu nejsou žádné slepé větve I Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 124 Prohledávání a pohled dopředu Backtracking (BT) 3 Prohledávání stavového prostoru do hloubky Dvě fáze backtrackingu 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 3 Proměnné dělíme na minulé - proměnné, které už byly vybrány (a mají přiřazenu hodnotu) aktuální - proměnná, která je právě vybrána a je jí přiřazována hodnota budoucí - proměnné, které budou vybrány v budoucnosti Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 125 Prohledávání a pohled dopředu Příklad: backtracking Příklad: VltV2, V3 e {1,2,3}, c : Vi = 3 x V3 Příklady vizualizací viz http://www.fi .muni .cz/~hanka/vis 3 zpětná vazba k této bakalářská práci? viz kontakt na stránkách Hana Rudová, Omezující podmínky, 16. prosince 2019 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) if í = 0 return , ,nekonzistentni ' ' else return přiřazené hodnoty {x\,...,xn} end Backtracking M Algoritmus vrací pouze první řešení M Série domén D[: 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í I Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 127 Prohledávání a pohled dopředu Uspořádání hodnot pro backtracking 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 3 na podmínkách mezi minulými proměnnými a aktuální proměnnou Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 128 Prohledávání a pohled dopředu Problémy a vylepšení backtrackingu 3 Thrashing, opakované objevování stejných nekonzistencí a částečných úspěchů při prohledávání! 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 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, 1 6. prosince 201 9 129 Prohledávání a pohled dopředu Algoritmy pohledu dopředu (look-ahead) LA Používají propagace omezení 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í 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 3 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é -i* snaha o výběr hodnoty, která umožní nejvíce voleb v budoucích přiřazeních * příklad: A,B,C in 1..10, A*B<10, B=C*2, pro A je lepší vybrat 1 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, 16. prosince 2019 1 30 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 M Sel ect-Val ue-XXX se liší dle typu LA algoritmu 3 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, 16. prosince 2019 131 Prohledávání a pohled dopředu Kontrola dopředu (forward checking) FC M 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 D'k 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 => V2=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, 1 6. prosince 201 9 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< v3 1, d => V] in 2..4 V2in 1..3 c2 => V2=3 V3= 1 d => V1= 4 I Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 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,Va),...,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 M Pohled dopředu (LA) kontroluje v kroku a podmínky ^ / Vi(a < l < n),\/k(a í na jejich hodnotu před posledni instanciaci x\ else if i < n s :=mini latestj latestj := k if not Consistent(Vfc,X{ = v) consistent := false else k := k+1 if consistent return v return null (v doméně Xt neexistuje konzistentní' hodnota) Hana Rudová, Omezující podmínky, 16. prosince 2019 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 x-? = red vyřadí x\ (tj. Iatest7 = 1), x 7 = biu e vyřadí X3 => celkem latest7 = 3 vracíme se ke konfliktní proměnné X3, ta už má ale prázdnou doménu latest3 = 2, vracíme se tedy k X2 3 X3=red dala latest^ na 1, X3=blue dala latest^ na 2 & 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, 16. prosince 2019 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 3 udržujeme Ji 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 3 mezi nesplněnými omezeními vybereme to nejvzdálenější (ostatní omezení neumožní nejdelší možný skok zpět) 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, 16. prosince 2019 1 55 Pohled zpět při prohledávání CBJ: výběr hodnoty procedure 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 Xt do Jt consistent := false if consistent return v return null (v doméně xt neexistuje konzistentní' hodnota) Hana Rudová, Omezující podmínky, 16. prosince 2019 1 56 Pohled zpět při prohledávání Algoritmus CBJ proceduře CBJ((X,D,C)) í := 1 D[ := Dt 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 Jí rozdíly od backtrackingu (inicializace čitače proměnných) (kopirováni domény) (inicializace množiny skoků zpět) Ji := Ji u J ip {Xi) (žá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 í := í + 1 (dopŕedná fáze) Jí:=0 # if í = 0 return , ,nekonzistentni ' ' else return prirazené hodnoty {x\, end CBJ I Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 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 x-i ^ 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} 3 skáčeme zpět na poslední proměnnou v J7, tedy na x3 3 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, 16. prosince 2019 1 58 Pohled zpět při prohledávání Algoritmy učení 3 Množiny skoků zpět jsou chybná prirazení vypočítaná během prohledávání 3 Tato chybná prirazení se mohou vyskytovat i později v jiných cestách stromu prohledávání a jsou znovu počítána Přidáme chybná přiřazení jako nová omezení při detekci slepé větve M nemá cenu uchovávat celou slepou větev dt v proměnné Xt+\ na toto přiřazení už později nenarazíme 3 uchováme chybná přiřazení na podmnožině proměnných {x\,...,xt\ 3 Prořezávání stavového prostoru čím menší chybná přiřazení se podaří uchovat, tím rychlejší bude prohledávání 3 Zvětšování množiny omezení 3 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, 16. prosince 2019 1 59 Pohled zpět při prohledávání Učení skoku zpět (jumpback learning) 3 Využijeme chybná přiřazení, 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í ai-iL/i] *3 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 ± xjk * dsíJe] tedy zakazuje přiřazení [(X2,blue>, {X4,green), (xs,red>] 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, 16. prosince 2019 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 m B 2 ■2ll C 1 2 ll 2 1 D 1 2 3 l=> skok na B 1 ll 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, 1 6. prosince 201 9 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, 16. prosince 2019 163 Další rozšíření backtrackingu Dynamický backtracking: algoritmus procedure DB(Variables, Constraints) Labelled := 0; Uniabelled := 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 Labelled Nevýhody algoritmu: přeuspořádáváním proměnných rušíme efekt heuristik výběru proměnných Hana Rudová, Omezující podmínky, 16. prosince 2019 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, 16. prosince 2019 165 Další rozšíření backtrackingu Základy backmarkingu Mark(Y, 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 Mark(Y,b) I Mark Neúplná stromová prohledávání Neúplné prohledávání do hloubky Hana Rudová, Omezující podmínky, 16. prosince 2019 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 ztráta úplnosti 3 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) 3 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 -i* prostředek může být globální (pro celý strom) i lokální (pro daný podstrom nebo uzel) 3 opakovaní běhu algoritmu (restart) 3 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, 16. prosince 2019 1 72 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 3 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 Randomizovaný backtracking s učením 3 chybná přiřazení předchozích běhů uchováme a využíváme takto lze také dosáhnout úplnosti, protože chybných přiřazení je konečně mnoho Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 173 Neúplná stromová prohledávání Omezení počtu návratů 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 3 „omezený počet navštívených listů" Pro úplnost: při neúspěchu zvětšíme počet návratů o jedna (opakování) Příklad: BBS(6) I Implementace «• počítáme počet návratů (neúspěchů) při překročení meze se prohledávání ukončí Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 1 74 Neúplná stromová prohledávání Omezení hloubky Depth-bounded search (DBS) Omezíme hloubku prohledávaného stromu (přerušení) 3 do dané hloubky stromu se zkouší všechny alternativy ve zbytku stromu se může použít jiná neúplná metoda Pro úplnost: při neúspěchu zvětšíme hloubku prohledávání o jedna (opakování) I Implementacel «• 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, 16. prosince 2019 1 75 Neúplná stromová prohledávání Prohledávání s kreditem 3 Credit search (CS) 3 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í jednotkový kredit zakazuje možnost volby (hodnoty), tj. pokračujeme pouze bez návratů Pro úplnost: při neúspěchu navýšíme kredit o jedna (opakování) Implementacel M v každém uzlu se nejednotkový kredit (rovnoměrně) rozdělí mezi alternativní podstromy M při jednotkovém kreditu se neberou alternativy (tj. při neúspěchu končíme) Hana Rudová, Omezující podmínky, 16. prosince 2019 176 Neúplná stromová prohledávání Iterativní rozšiřování Iterative broadening IB Omezený maximální počet voleb (hodnot) při každém výběru proměnné (přerušení) v každém bodě volby větvení omezeno konstantou «• při překročení max. počtu voleb pokračujeme předchozím bodem volby Úplnost: při neúspěchu zvýšíme povolený počet voleb o jedna (opakování) Implementacel 3 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, 16. prosince 2019 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 Heuristiky - radí, jak pokračovat v prohledávání M doporučují hodnotu pro přiřazení často vedou přímo k řešení Co dělat, když heuristika neuspěje? I DFS se stará hlavně o konec prohledávání (spodní část stromu) DFS tedy spíše opravuje poslední použité heuristiky než první DFS předpokládá, že dříve použité heuristiky ho navedly dobřel 3 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, 16. prosince 2019 178 Neúplná stromová prohledávání Zotavení se z chyb heuristiky 3 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 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, 1 6. prosince 201 9 179 Neúplná stromová prohledávání Omezené diskrepance Limited discrepancy search (LDS) Omezený maximální počet diskrepancí na cestě (přerušení) 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 '~ - - ■ doporučuje vydat se levou větví 3 Diskrepance pro nebinární domény 6 54 3 2 1 M nedoporučené hodnoty se berou jako jedna diskrepance (zde) M 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, 16. prosince 2019 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 e 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, 16. prosince 2019 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 se arch (ILDS) M 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í) I Příklad: ILDS-PROBE(l), heuristika doporučuje vydat se levou větví 1 2 3 Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 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, 1 6. prosince 201 9 183 Neúplná stromová prohledávání Hloubkou omezené diskrepance ILDS bere cesty s diskrepancemi na konci dříve Depth-bounded discrepancy search (DDS) 3 Diskrepance povoleny pouze do dané hloubky (přerušení) M v této hloubce je vždy diskrepance, tj. zabrání se procházení větví z předchozí iterace M hloubka zároveň omezuje maximální počet diskrepancí 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, 16. prosince 2019 184 Neúplná stromová prohledávání Lokální prohledávání Lokální prohledávání (LS) 3 Princip M pracuje s úplnými nekonzistentními přiřazeními proměnných snaží se lokálními opravami snížit počet konfliktů Příklad: umístění n dam na šachovnici 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ů 3 LS vyřeší řádově větší problémy než algoritmy založené na prohledávání do hloubkyl 3 Přibližná metoda prohledávání 3 neúplná metoda nezaručuje nalezení (vyloučení existence) řešení i když existuje (neexistuje) 3 malé paměťové nároky Hana Rudová, Omezující podmínky, 16. prosince 2019 186 Lokální prohledávání Terminologie lokálního prohledávání -0 Stav 0: ohodnocení všech proměnných M Evaluace e: hodnota objektivní funkce (počet nesplněných podmínek=počet konfliktů) M Globální optimum: stav s nejlepší evaluací M Lokální změna: změna hodnoty (jedné) proměnné 3 Okolí o: množina stavů lišící se od daného stavu o jednu lokální změnu 3 Lokální optimum: stav, v jehož okolí jsou stavy s horší evaluací; není globálním optimuml M Striktní lokální optimum: stav, v jehož okolí jsou pouze stavy s horší evaluací; není globálním optimum M Ne-striktní lokální optimum: stav, v jehož okolí exisují stavy se stejnou evaluací; není globálním optimum M Plateau: množina stavů se stejnou evaluací minimum Hana Rudová, Omezující podmínky, 16. prosince 2019 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 M Jak stanovit MaxPokusu, MaxZmen? 3 pokračovat dokud existuje přiřazení s lepší evaluací M restart (MaxPokusu>l) v některých případech diskutabilní Hana Rudová, Omezující podmínky, 16. prosince 2019 188 Lokální prohledávání Metoda největšího stoupání (hill climbing) HC Začíná v náhodně vybraném stavu Hledá vždy nejlepší stav v okolí Okolí = hodnota libovolné proměnné je změněna, velikost okolí n x (d - 1) 3 Ú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, 1 6. prosince 201 9 189 Lokální prohledávání Metoda minimalizace konfliktu (MC) M Okolí u HC je poměrně velké: n x {d - 1) 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é * 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, 16. prosince 2019 191 Lokální prohledávání Minimalizace konfliktů s náhodnou procházkou procedure 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, 1 6. prosince 201 9 192 Lokální prohledávání Největší stoupání s náhodnou procházkou procedure HCRW(MaxZmen, p) Rozdíly od MCRW 0 : = 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, 1 6. prosince 201 9 193 Lokální prohledávání Tabu seznam Setrvání v lokálním optimu je speciálním případem cyklu Jak se obecně zbavit cyklů? stačí si pamatovat předchozí stavy a zakázat opakování stavu paměťově příliš náročné (mnoho stavů) 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 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 3 Tabu seznam je používán samostatně i v kombinaci s jinými metodami LS Hana Rudová, Omezující podmínky, 16. prosince 2019 194 Lokální prohledávání Algoritmus prohledávání s tabu seznamem M Tabu seznam zabraňuje krátkemu cyklení Povoleny jsou pouze tahy mimo tabu seznam a tahy splňující aspirační kritérium M 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, 16. prosince 2019 195 Lokální prohledávání Výběr souseda: přehled Metoda stoupání (HC) M soused s nejlepší evaluací vybrán 3 Tabu prohledávání (TS+HC) 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 ' výběr její hodnoty s nejlepší evaluací M Náhodná procházka (RW) soused vybrán náhodně 3 Min. konflikt (metoda stoupání) s náhodnou procházkou MC+RW (HC+RW) s malou pravděpodobností: náhodný výběr souseda jinak: minimální konflikt (metoda stoupání) Hana Rudová, Omezující podmínky, 16. prosince 2019 196 Lokální prohledávání Simulované žíhání (simulated annealing) SA 3 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í při zhoršení pouze za dané pravděpodobnosti, která klesá se snížením teploty Cykly algoritmu «• 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, 16. prosince 2019 197 Lokální prohledávání Metropolisovo kritérium Rozdíl mezi kvalitou nového (5) a existujícího (9) řešení M AE = E(5)-E(0) & E (chybovost) musí být minimalizováno Metropolisovo kritérium I 3 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 U náhodné číslo z intervalu (0,1)1 • pomůcka: porovnej e-10/100 vs. e-100/100,a e-10/100 vs. e-10/l Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 198 Lokální prohledávání Algoritmus simulovaného žíhání proceduře SA( TInit, TEnd, Maxlter ) 6 : = náhodné ohodnoceni proměnných a := 6 (dosud nejlepší nalezené přiřazeni) for T := TInit to TEnd PocetChyb := 0 while PocetChyb < Maxlter vyber lokálni změnu z 0 do ô if E (ô) CSP nad disjunkcemi boolean proměnných M SAT je NP-úplnýl 1 LS řeší poměrně velké formule 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 3 evaluace udává, jaký je (vážený) počet nesplněných klauzulí Hana Rudová, Omezující podmínky, 16. prosince 2019 200 Lokální prohledávání Algoritmus GSAT procedúre 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} 3 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í změna C na 0 splní první i poslední klauzuli ale nesplní —>A v ~*B v C (evaluace=l) M 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, 16. prosince 2019 201 Lokální prohledávání Heuristiky pro GSAT GSAT lze kombinovat s různými heuristikami, které zvyšují jeho efektivitu M obzvláště při řešení strukturovaných problémů Použití náhodné procházky spolu s minimalizací konfliktů Vážení klauzulí * některé klauzule zůstávají po řadu iterací nesplněné, klauzule tedy mají různou důležitost splnění „těžké" klauzule lze preferovat přidáním váhy 3 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í 3 Průměrování řešení M 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, 16. prosince 2019 202 Lokální prohledávání Hybridní prohledávání 3 Příklady kombinace lokálního prohledávání 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ř: před: lokální prohledávání nám poskytne heuristiku na uspořádání hodnot M 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, 1 6. prosince 201 9 203 Lokální prohledávání Iterativní dopředně prohledávání Iterative Forward Search (IFS) 3 Hybridní prohledávání: konstruktivní nesystematický algoritmus pracuje nad modelem s pevnými a měkkými omezujícími podmínkami 3 pevné podmínky: musí být splněny M měkké podmínky: reprezentují účelové funkce, jejichž vážený součet je minimalizován Pracuje s konzistentními přiřazeními Základní myšlenky (blízký dynamickému backtrackingu) ' začíná s prázdným přiřazením 3 vybere novou proměnnou k přiřazení M 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 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, 16. prosince 2019 204 Lokální prohledávání Iterative Forward Search Algorithm A (partial) feasible solution ■ Unassigned variables Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 205 Lokální prohledávání Iterative Forward Search Algorithm A (partial) feasible solution £- o ■ Unassigned variables Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 206 Lokální prohledávání Iterative Forward Search Algorithm A (partial) feasible solution Select a value < m £- o □ 1? 1? U 1? T Unassigned variables Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 207 Lokální prohledávání Iterative Forward Search Algorithm A (partial) feasible solution Select a value < m £- o ■ Some variables can be unassigned Unassigned variables Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 208 Lokální prohledávání IFS: algoritmus procedure IFS() 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, 16. prosince 2019 209 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] 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 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í J př. 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í 5 = c,C = a,D = £>a vybíráme hodnotu pro A: nechť AIa vede ke konfliktu s BI c: lyhodnoceno jako 4 • není konflikt s C/a, tak se nezapočítává ±* nechť Alb vede ke konfliktu s C/a: lyhodnoceno jako 2 -i* tj. vybereme hodnotu b pro proměnnou A Hana Rudová, Omezující podmínky, 16. prosince 2019 210 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 náhodně vygenerované problémy M aplikačně založené náhodné problémy Kriteria M CPU čas M velikost generovaného prohledávacího stromu počet volání procedury (např. Consi stent) I Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 212 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 3 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 3 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í 3 příklady 3 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, ... 3 Problém: výsledky lze stále velice obtížně zobecnit na další problémy 3 pro jeden problém je lepší jeden algoritmus, pro další problém jiný algoritmus Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 213 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) libovolný počet datových instancí M 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) M n počet proměnných ^ m počet hodnot v doméně proměnných M pi pravděpodobnost, že existuje omezení na páru proměnných P2 pravděpodobnost, že omezení povoluje daný pár hodnot Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 214 Srovnání prohledávacích algoritmů Aplikačně založené náhodné problémy Identifikace problémové domény lze definovat parametrizovatelné problémy * problémy mají přitom specifickou (z aplikace vycházející) strukturu M problémy lze náhodně generovat s různým nastavením parametrů Výhody * zaměřené na reálné problémy M generování řady problémů umožňuje statistické porovnání Příklad: shop scheduling problémy * m strojů 3 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ň M podmínky na sekvencování operací úlohy (žádné, dáno pořadí, stejné pořadí pro všechny) * minimalizace dokončení poslední úlohy, minimalizace největšího zpoždění úlohy, ... Hana Rudová, Omezující podmínky, 16. prosince 2019 21 5 Srovnání prohledávacích algoritmů Fáze přechodu Náhodný k-SAT problém M formule pevné délky jsou generovány výběrem m klauzulí každá klauzule délky k je uniformně náhodně generována z množiny všech klauzulí 3 Obtížnost nalezení řešení 3 při malém počtu klauzulí je většina problémů splnitelná a snadno řešitelná M 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ýchl 3 Fenomén fáze předchodu (phase transition) M 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, 1 6. prosince 201 9 21 6 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) 3 proměnné X = {x\,... ,xn} M domény D = {D\,... ,Dn} M omezení C = {Ci,..., Cn} ± Q je definováno na Y* ^ X, Yí = {x^,... ,Xík} i* Ci je podmnožina x ... x Díki Objektivní funkce obj : Sol — 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 ^ optimální = maximální nebo minimálni Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 218 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} M d je podmnožina x ... x Difc Měkké (soft) omezení Cs = {F\,..., Fi\ M F j je definované nad Qj ^ X, Qj = {Xjlt... ,Xjt} Fj je funkce do reálných čísel DJ: x ... x DJř + Optimalizační problém s podmínkami (COP): (X,D, C^, C5)l Objektivní funkce relace funkce I zjednodušení na X F(d) = X^Qj]) d[Qj]... projekce d na Qjl Řešení COP: d° splňující všechna omezení z Ch tak, že = maxjF(d) nebo = min^FW) Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 219 Optimalizace & soft omezení: modely Použití soft omezení Problémy optimalizační, příliš podmíněné, špatně definované problémy, ... Fuzzy preference, pravděpodobnosti, ceny, váhy, úrovně požadavků,... 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 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, 16. prosince 2019 220 Optimalizace & soft omezení: modely Přístupy pro soft omezení Vybrané přístupy 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)^ 3 omezení - rozšíření klasického omezení (c = relace) 3 problém - rozšíření CSP (trojice (V,D,C)) 3 úroveň splnění - jak přiřazení hodnot splňuje problém (I\c6) 3 řešení - které přiřazení je (optimálním) řešením (splňují všechna omezení) ú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, 1 6. prosince 201 9 221 Optimalizace & soft omezení: modely Omezení s váhami, MAX-CSP 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) 3 Úroveň splnění - funkce na množině přiřazení co(0) = Xčn-c => součet vah nesplněných omezení 3 Řešení - přiřazení 9 s minimální co(9) M Úroveň konzistence - úroveň splnění řešení MAX-CSP (maximální CSP) Váhaje rovna jedné => maximalizace počtu splněných omezení Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 222 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 Fuzzy CSP (X,D,Cf) M Cf je množina fuzzy omezení 3 X uspořádaná množina proměnných Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 224 Optimalizace & soft omezení: modely Kombinace a projekce omezení * Projekce n-tic (dl9...,di) 1$ 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 Hc(di,...,dk) = mm(iuCx((di,...,dk) i f),/iCr((di,■ ■ ■ ,dk) iy)) 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 Y c,cx,cy omezení nad X,X,Y L*c(dxi,...,dXk) = max HcY(dyi,...,dyi) ((dyi,...,dyi)eDyix---xDyi)A((dyi,...,dyi){x=(dxi,...,dx]c)) M udává, jaká je úroveň splnění všech přiřazení X vzhledem k cY 3 příklad (pokračování): projekce c3 ^(B) na (1) Aic3*(B)(l) -max(iUc3(l,l),^c3(2,l),iUc3(3,l)) = max(0.2,0.3,0.4) =0.4 Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 225 Optimalizace & soft omezení: modely Řešení fuzzy CSP Úroveň splnění přiřazení (d\,..., dn) dána jako jl/0c(<ži, ■ ■ ■, dn)l 3 Řešení - přiřazení (d\,..., dn) takové, že max jU0C(^i,...,^n) = 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 (Piu) je úroveň konzistence také jako projekce na prázdnou množinu proměnných ©C ^0 Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 226 Optimalizace & soft omezení: modely Příklad: řešení fuzzy CSP M Viz dříve: © 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»(AlB) 0 C ^{A,B} (3, 3) = max(A/ec(3, 3)) = 0.6, 0C»W}(2,2) = O.4,...I ( ©C^ai (1) =max(/iec(l,l),/iec(1.2),/iec(l,3)) =max(0.2,0.3,0.1) =0.3 0C*|A) (2) =max(AJ©c(2,D,A/ec(2,2),AJec(2,3)) = max(0.3,0.4,0.5) =0.5 ©C^ai (3) =max(AJ©c(3,D,A/ec(3,2),AJec(3,3)) = max(0.1,0.5,0.6) =0.61 * 0C»0 ©C W0 () =max(jU©c(l,D,A/©c(l,2),A'©c(l,3),jU©c(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, 1 6. prosince 201 9 227 Optimalizace & soft omezení: modely Omezení nad polookruhy Semiring-based CSP 3 c-polookruh (JA, + , x,0,1) J4. 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í) 3 Částečné uspořádání ((a x b) < (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 g 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 M striktní monotonie a idempotence x zároveň pouze pro dvouprvkové J4, 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, 16. prosince 2019 229 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) i|SÄe)d'e)= (4,1,5)1 Kombinace c = ci ® C2 ci = (dcfi, coni) and C2 = (def2, con2) c = (def, con), con = coni u con2, def (i) = defx(i\ccZx) x def2(ticZ2)l M příklad: CSP s váhami: JA = 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:1 aa 2(=2+0) ab 4(=4+0) ba 2(=1+1) bb 1 (=0+1) Hana Rudová, Omezující podmínky, 16. prosince 2019 230 Optimalizace & soft omezení: Řešení pro omezení nad polookruhy Projekce c (1/ c = (def, con), I q V c' = (def, corí), corí = con n I def ď) = X def(t) f/f\Con f r LILiIncon L 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 3 pro každé přiřazení proměnných v con vrací omezení Sol(P) jeho úroveň splnění 3 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) = (a ® c2) ^{X,yh aa 2, ab 4, ba 2, bb ll problém P2 = {{ci,c2}, {x}): Sol(P2) = (c\ ® c2) tt{X}'- a 2, b 1 Úroveň konzistence: blevel(P) = Sol(P) ^0 3 příklad (pokračování): blevel(Pi) = blevel(P2) = 1 Hana Rudová, Omezující podmínky, 16. prosince 2019 231 Optimalizace & soft omezení: mod 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 3 snaha o získání realističtějších preferencí 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í I Ci e C a COYli ^ W} — (<8> {Ci | Ci G ca COYIí ^ (W u {j7})}) M coyií označuje proměnné v omezení ct M 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, 1 6. prosince 201 9 233 Optimalizace & soft omezení: algoritmy Soft hranová konzistence (SAC) 3 k = 2,W = {x} : cx = (®{Cy,cxy,cx}) tt{x}i 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 M 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á (®{cy,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} 3 cx'- a... 0.9, b... 0.1, 0.9,b. ..0.5, 0.8, ab ... 0.2, ba...0, bb ... 0 3 není SAC: cx dává 0.9 na x = a, ale (®{cy, cxy, cx}) ^{X} dává 0.8 na x = a ®{cy,cXy,cx} dává na (a, a) : biin(0.9,0.8,0.9) = 0.8l ®{cy,cxy,cx} dává na (a,b) :feiin(0.5,0.2,0.9) = 0.2l projekce (®{cy, cxy, cx}) ^{X} dává na (a) : lnax(0.8,0.2) = 0.8 Hana Rudová, Omezující podmínky, 1 6. prosince 2019 234 Optimalizace & soft omezení: algoritmy Výpočet SAC M 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} M iterace až do dosažení stabilityl 3 x idempotentní (fuzzy CSP) zajištěna ekvivalence, tj. původní i nový (po dosažení SAC) problém mají stejné řešení M zajištěno ukončení algoritmul 3 x není idempotentní (CSP s váhami) 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 ±> 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í X tato vlastnost platí pro CSP s váhami Hana Rudová, Omezující podmínky, 16. prosince 2019 23 5 Optimalizace & soft omezení: algoritmy Řešení COP Cíl: nalezení úplného řešení s optimální hodnotou cenové funkce Prohledávání lokální prohledávání i* přímé zahrnutí optimalizačního kriteria do evaluace (hodnota obj. funkce) 3 stromové prohledávání I i* metoda větví a mezí + její rozšíření CSP s omezeními: minimalizace součtu vah omezení minXCecc(^) «• velmi častá optimalizační úloha váha (cena) omezení: 0 = úplné splnění, (0, oo) částečné nesplnění, oo úplné nesplnění hodnota cenové funkce: cena přiřazení/řešení M maximalizace je duální problém algoritmy pro fuzzy CSP na podobných principech Hana Rudová, Omezující podmínky, 1 6. prosince 2019 236 Optimalizace & soft omezení: algoritmy COP jako série CSP problémů Triviální metoda řešení Řešení COP jako CSP a nalezení iniciální hodnoty cenové funkce W1 3 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 Výpočetně zbytečně náročné Efektivní rozšíření obtížné Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 237 Optimalizace & soft omezení: algoritmy Metoda větví a mezí (branch&bound) BB Prohledávání stromu do hloubky M přiřazené=minulé proměnné P, nepřiřazené=budoucí proměnné F 3 omezení pouze na minulých proměnných O, omezení na minulých i budoucích proměnných Cpp, omezení pouze na budoucích proměnných Cpi Výpočet mezí horní mez UB: cena nejlepšího dosud nalezeného řešení M dolní mez LB: dolní odhad minimální ceny pro současné částečné přiřazení 3 Ořezávání: LB > UB (cíl: minimalizace) 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, 1 6. prosince 2019 238 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í-\,a)i 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(äi-i,a) < UB return a (jinak ořezej a) return null (konzistentní' hodnota neexistuje) Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 239 Optimalizace & soft omezení: algoritmy Algoritmus metody větví a mezí procedure Branch-Bound((X,D, C), UB,f^) rozdíly od backtrackingu i : = 1, D[ := Di (inicializace čitače proměnných, kopírová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) 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 pro k = 1... n until true end Branch-Bound Hana Rudová, Omezující podmínky, 16. prosince 2019 240 Optimalizace & soft omezení: algoritmy I Dolní mez Kvalita dolní meze: velmi důležitá pro efektivitu BB 3 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 ^ NC* M lokální ceny budoucích proměnných * AC* M globální ceny budoucích proměnných prohledávání ruská panenka Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 241 Optimalizace & soft omezení: algoritmy NC* algoritmus Projekce ceny hodnot (j, *) pro každou proměnnou j do dolní hranice LB ceny řešení I j j —x LB=8 Smazání hodnot (j,a) převyšující (nebo rovné) horní hranici UB LB=8 UB=10 LB=8 UB=10 Hodnotu a proměnné j značíme (j,a) 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, *) Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 242 I Optimalizace & soft omezení: algoritmy AC* algoritmus (A) Projekce ceny hrany (í,a)(j,b) do ceny hodnoty (i, 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,l) (í,2)(j,2) (i,2)0\3) (í,2) Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 243 Optimalizace & soft omezení: algoritmy Prohledávání ruská panenka (Russion doll search) 3 n po sobě jdoucích BB prohledávání, každé má navíc jednu proměnnou ........ „ statické uspořádání proměnných 3 první podproblem obsahuje pouze n-tou proměnnou í-tý podproblem obsahuje posledních i proměnných ((n - i + 1)... n) 3 podproblémy řešeny pomocí BB s využitím LB a UB z předchozích běhůl M Při řešení podproblému (n - i + 1) 3 problém zahrnuje proměnné Xí,Xí+\,...,xn I mějme částečné přiřazení pro tento podproblem {auat+i,at+j) s nepřiřazenými proměnnými Xí+j+i, xni 3 do dolní meze lze zahrnout optimální cenu (n-í- j) podproblému optim(Xi+j+i,xn) 3 LB((ai,ai+i,...,ai+j)) = dist((auai+i,... ,ai+j)) + optim(xi+j+i,... ,xn) dist((cii,OLi+i,at+j)) vzdálenost (součet vah omezení na minulých proměnných) 3 optimální řešení přechozích problémů použita pro: výběr hodnoty, pro zlepšení iniciální horní mezel Vnořená prohledávání se vyplatí vzhledem k prořezání stavového prostoru Hana Rudová, Omezující podmínky, 16. prosince 2019 244 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í 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 M příklady k vypočítání (jako vzorové příklady - někdy kratší verze) 3 pojem (a příklad) kód algoritmu (a příklad) porovnání pojmů/algoritmů (a příklady) Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 246 Opakování Příklady s řešeními na webu I. Příklady 1. M binarizace AC-1 vs. AC-3 M konzistence mezí vs. hranová konzistence Příklady 2. M strom stavového prostoru: backtracking vs. kontrola dopředu vs. pohled dopředu Příklady 3. M omezení s váhami Příklady 4. M přehled konzistenčních algoritmů Ä algoritmus AC-4 -0 algoritmus DAC Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 247 Opakování Příklady s řešeními na webu II Příklady 5. & strom stavového prostoru: backtracking vs. kontrola dopředu pohled zpět: Gaschnigův skok zpět Příklady 6. přehled prohledávacích algoritmů & problém rozvrhování výuky v OPL Příklady 7. binarizace M podpora hodnoty & konzistence mezívs. hranová konzistence & algoritmus DAC, nalezení řešení bez navracení Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 248 Opakování Příklady s řešeními na webu III Příklady 8. 3 strom stavového prostoru: backtracking vs. kontrola dopředu vs. pohled dopředu 3 problém plánování projektu v OPL Příklady 9. 3 stromový CSP, nalezení řešení bez navracení 3 algoritmus PC-2 3 problém rozvrhování výuky jedné místnosti v OPL 3 strom stavového prostoru: kontrola dopředu vs. pohled dopředu bez iniciální konzistence 3 rozvrhování úkolů pro zaměstnance na směny Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 249 Opakování Příklady s řešeními na webu IV Příklady 10 & nalezení podpory & algoritmus DAC a nalezení řešení bez navracení & problém přiřazení poboček k obchodům v OPL 3 BBS-DBS, DDS & rozvrhování na směny Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 250 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. 3 Šíř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ů. 3 Šíř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, 1 6. prosince 201 9 251 Opakování Algoritmus: lokální prohledávání 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) 0 : = náhodné ohodnoceni proměnných % iniciál ní přiřazení PocetZmen := 0 while E(0) > 0 a PocetZmen c2) ^Y (r) = min(jUCl0c2(n r),jUCl0c2(s,r)) = min(l + 0,4 + 0) = 1 (ci c2) tty (s) = min(jUCl®c2(r,s),jUc1®c2(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, 1 6. prosince 201 9 254 Opakování Doménové proměnné 3 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 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 3 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;! 3 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 I navíc: forall (i, j in 1 ..Size) sum(k in 1 ..Size) sudoku[i][j][k] == 1; Hana Rudová, Omezující podmínky, 16. prosince 2019 255 Opakování Rozvrhování: zdroje Jeden zdroj M jednotková doba trvání úlohy: dvar int, allDifferent(casy) odlišné doby trvání úloh: dvar interval, dvar sequence, noOverlap(casy)l 3 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 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, 1 6. prosince 201 9 256 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]; noOverlap(all (u in 1..Prace+Dovolene) casy[u]);l cumulFunction nástroje = sum (p in 1..Prače) pulse( casy[p],nástrojů[p] ); Hana Rudová, Omezující podmínky, 16. prosince 2019 257 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 max (u in 1 ..Počet) endOf( casy[u] ); zadány poslední operace úlohy:! minimize max (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, 16. prosince 2019 258 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, 16. prosince 2019 259 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, 16. prosince 2019 260 Opakování Školní rozvrh: model Doménové proměnnél // přiřazeni času předmětům v maximálním rozmezí 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říd do místnosti dvar interval prirazeni[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 místnosti 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, 1 6. prosince 201 9 261 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ůl // 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]; I 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); Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 262 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, 1 6. prosince 201 9 263 Opakování Rozvrhování vyšetření pacientů v nemocnici Každý pacient musí absolvovat vyšetření zadaného typu, která probíhají na různých pracovištích. Cílem řešení je pro každé vyšetření pacienta určit, ve kterém čase bude probíhat a které pracoviště bude vyšetření realizovat. Dále: & Vyšetření jednoho pacienta se nesmí překrývat. Vyšetření na jednom pracovišti se nesmí překrývat. Každý typ vyšetření má stanovenu délku provádění a pracoviště, na kterých ' může být prováděno. Některý typ vyšetření musí proběhnout před realizací jiného typu vyšetření (pokud je pacient absolvuje oba). Jsou proto zadány dvojice typů vyšetření určující, které vyšetření musí být realizováno před zahájením dalšího vyšetření. Vyšetření pacientů se závažnějším typem onemocnění by měla být dokončena dříve, aby mohli dříve nastoupit na operaci. Cílem je tedy minimalizovat vážený součet dokončení nejpozdějších vyšetření pacientů. Hana Rudová, Omezující podmínky, 16. prosince 2019 264 Opakování Jednoduché zadání Příklad jednoduchého zadání s řešením: počet pacientů 2, počet typů vyšetření 2, počet pracovišť 2 doby trvání vyšetření daného typu: 1, 2; 3 pracoviště pro vyšetření daného typu: 1:1,2, 2:1; typy vyšetření pro pacienty: 1:1,2,2:1; priority pacientů: 1,10; precedence pro dané typy vyšetření: 1 před 2; dvě optimální řešení s kvalitou 1 3: M pacient, vyšetření, čas, pracoviště 1,1,0,1; 1,2,1,2; 2,1,0,2 * 1,1,0,2; 1,2,1,2; 2,1,0,1. Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 265 Vstupní Konstanty a intervaly i nt NbPaci ents = ...; i nt NbMedi cals = ...; i nt NbRooms = ...; range RPacients = 1..NbPacients; range RMedicals = 1..NbMedicals; range RRooms = 1..NbRooms; Vyšetření: typ, místnostil tuple Tmedical{ int duration; {int} rooms; } Tmedical Medicals[RMedicals] = ...; Pacient: typy vyšetřeníl tuple pMedical{ int pacient; int medical; } {pMedical} PMedicals = ...; Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 data a typy i // [<2,{1,3}>, <2,{2,4}>, <3,{1,2,3}>] // {<1,1>,<1,2>,<2,2>,<2,3>,<3,1>, ...} 266 Opakování Vyšetření pacienta tuple Tmedical{ int duration; {int} rooms; } Tmedical Medicals[RMedicals] = ...; tuple pMedical{ int pacient; int medical; } {pMedical} PMedicals = ...; Časy vyšetření paciental dvar interval times[pm in PMedicals] size Medicals[pm.medical].duration; Nepřekrytí vyšetření paciental dvar sequence seqPacient[p in RPacients] in all(pm in PMedicals: pm.pacient == p) times[pm];l forall (p in RPacients) noOverlap(seqPacient[p]); Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 267 Opakování Vyšetření na jednom pracovišti dvar interval times[pm in PMedicals] size Medi cals[pm.medi cal].du rati on; Proměnné pro výběr místnosti pro vyšetření paciental dvar interval assigned[PMedicals][RRooms] optional; Na každém pracovišti maximálně jedno vyšetřeníl I forall (pm in PMedicals) alternative (times[pm], all (r in RRooms: r in Medicals [pm.medical].rooms) assigned[pm] [r]) ;l forall (r in RRooms) noOverlap(al1 (pm in PMedicals: r in Medicals [pm.medical].rooms) assi gned [pm][r]); Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 268 Opakování Precedence tuple pMedical{ i nt paci ent; i nt medi cal; } {pMedical} PMedicals = dvar interval times[pm in PMedicals] size Medicals[pm.medical].duration; Typy a vstupní datal tuple Tprec{ int before; I int after; } {Tprec} Prec = . . . ; Omezení na precedencel forali (pr in Prec, pmB in PMedicals, pmA in PMedicals: pmB.pacient == pmA.pacient && pmB.medical == pr.before && pmA.medical == pr.after) endBeforeStart(times[pmB],times[pmA]); Hana Rudová, Omezující podmínky, 16. prosince 2019 269 Opakování Minimalizace vážených časů posledních vyšetření Typy a vstupní datal int Priorities[RPacients] = Minimalizacel dexpr int pacientMax[p in RPacients] = max (pm in PMedicals: pm.pacient == p) endOf(times[pm]);l minimize sum (p in RPacients) Priorities[p]*pacientMax[p] ; Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 270 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 .cum' .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, 1 6. prosince 201 9 271 Zdroje