PA163 Programování s omezujícími podmínkami podzim 2006 Základní informace Web předmětu: http://www.fi.muni.cz/~hanka/cp průsvitky průběžně na ISu (interaktivní osnova, učební materiály) elektronicky dostupné materiály k jednotlivým částem přednášky Ukončení předmětu: písemná práce pro každý řádný termín společná příprava pro všechny cca 5 otázek: přehledové, srovnávací, algoritmy, pojmy, příklady (model) vzor písemné práce dostupný na webu předmětu ústní zkouška ve stejný den jako písemná práce (cca 30 minut) příprava na individuální otázky, během zkoušky diskuse nad písemnou prací opravný termín pouze jako ústní zkouška (není už písemná práce) Omezující podmínky v jiných přednáškách: PA167 Rozvrhování, IB013 Logické programování I Hana Rudová, Omezující podmínky, 20. prosince 2006 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://cswww.essex.ac.uk/Research/CSP/edward/FCS.html 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 IS nebo web předmětu Hana Rudová, Omezující podmínky, 20. prosince 2006 3 Organizace předmětu Přehled přednášky Problém splňování podmínek. Příklady a modelování. Složitost. Grafová reprezentace podmínek. Základní typy konzistence a algoritmy: hranová, po cestě, k-konzistence. Konzistence pro nebinární podmínky: doménová konzistence, konzistence mezí, globální podmínky. Směrová konzistence a algoritmy. Šířka grafu podmínek a polynomiální CSP. Stromové prohledávací algoritmy: backtracking, pohled dopředu, pohled zpět, neúplné prohledávání. Lokální prohledávání. Optimalizace, soft omezení: modely, algoritmy. Dynamické problémy. Hana Rudová, Omezující podmínky, 20. prosince 2006 4 Organizace předmětu Cvičení Cíl: praktické procvičení příkladů s omezujícími podmínkami u počítačů Obsah: logické programování s omezujícími podmínkami úvod do Prologu CLP program globální podmínky prohledávání modelování SICStus Prolog komerční produkt, zakoupena licence pro instalace na domácí počítače studentů dokumentace: http://www.fi.muni.cz/~hanka/sicstus/doc/html podrobné informace na webu předmětu Hana Rudová, Omezující podmínky, 20. prosince 2006 5 Organizace předmětu Časový harmonogram cvičení 22.9.2006 6.10.2006 27.10.2006 (pozor není už sudý týden) 10.11.2006 24.11.2006 8.12.2006 Hana Rudová, Omezující podmínky, 20. prosince 2006 6 Organizace předmětu Úvod do programování s omezujícími podmínkami Omezení (constraint) Dána množina (doménových) proměnných Y = {y1, . . . , yk} konečná množina hodnot (doména) D = D1 . . . Dk Omezení (podmínka) c na Y je podmnožina D1 × . . . × Dk omezuje hodnoty, kterých mohou proměnné nabývat současně Hana Rudová, Omezující podmínky, 20. prosince 2006 8 Úvod do CP Omezení (constraint) Dána množina (doménových) proměnných Y = {y1, . . . , yk} konečná množina hodnot (doména) D = D1 . . . Dk Omezení (podmínka) c na Y je podmnožina D1 × . . . × Dk tj. relace omezuje hodnoty, kterých mohou proměnné nabývat současně Hana Rudová, Omezující podmínky, 20. prosince 2006 8 Úvod do CP Omezení (constraint) Dána množina (doménových) proměnných Y = {y1, . . . , yk} konečná množina hodnot (doména) D = D1 . . . Dk Omezení (podmínka) c na Y je podmnožina D1 × . . . × Dk tj. relace omezuje hodnoty, kterých mohou proměnné nabývat současně Příklad: proměnné: A,B domény: {0,1} pro A {1,2} pro B omezení: A=B nebo (A,B) {(0,1),(0,2),(1,2)} Hana Rudová, Omezující podmínky, 20. prosince 2006 8 Úvod do CP Omezení (constraint) Dána množina (doménových) proměnných Y = {y1, . . . , yk} konečná množina hodnot (doména) D = D1 . . . Dk Omezení (podmínka) c na Y je podmnožina D1 × . . . × Dk tj. relace omezuje hodnoty, kterých mohou proměnné nabývat současně Příklad: proměnné: A,B domény: {0,1} pro A {1,2} pro B omezení: A=B nebo (A,B) {(0,1),(0,2),(1,2)} Omezení c definováno na proměnných y1, . . . yk je splněno, pokud pro hodnoty d1 D1, . . . dk Dk platí (d1, . . . dk) c Hana Rudová, Omezující podmínky, 20. prosince 2006 8 Úvod do CP Omezení (constraint) Dána množina (doménových) proměnných Y = {y1, . . . , yk} konečná množina hodnot (doména) D = D1 . . . Dk Omezení (podmínka) c na Y je podmnožina D1 × . . . × Dk tj. relace omezuje hodnoty, kterých mohou proměnné nabývat současně Příklad: proměnné: A,B domény: {0,1} pro A {1,2} pro B omezení: A=B nebo (A,B) {(0,1),(0,2),(1,2)} Omezení c definováno na proměnných y1, . . . yk je splněno, pokud pro hodnoty d1 D1, . . . dk Dk platí (d1, . . . dk) c 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, 20. prosince 2006 8 Úvod do CP Problém splňování podmínek (CSP) Dána konečná množina proměnných X = {x1, . . . , xn} konečná množina hodnot (doména) D = D1 . . . Dn konečná množina omezení C = {c1, . . . , cm} omezení je definováno na podmnožině X Problém splňování podmínek je trojice (X, D, C) (constraint satisfaction problem) Hana Rudová, Omezující podmínky, 20. prosince 2006 9 Úvod do CP Problém splňování podmínek (CSP) Dána konečná množina proměnných X = {x1, . . . , xn} konečná množina hodnot (doména) D = D1 . . . Dn konečná množina omezení C = {c1, . . . , cm} omezení je definováno na podmnožině X Problém splňování podmínek je trojice (X, D, C) (constraint satisfaction problem) Příklad: proměnné: A,B,C domény: {0,1} pro A {1} pro B {0,1,2} pro C omezení: A=B, B=C Hana Rudová, Omezující podmínky, 20. prosince 2006 9 Úvod do CP Řešení CSP Částečné ohodnocení proměnných (d1, . . . , dk), k < n A in 0..1 některé proměnné mají přiřazenu hodnotu B #= 1 Úplné ohodnocení proměnných (d1, . . . , dn) C in 0..2 všechny proměnné mají přiřazenu hodnotu A #\= B, B #\= C Hana Rudová, Omezující podmínky, 20. prosince 2006 10 Úvod do CP Řešení CSP Částečné ohodnocení proměnných (d1, . . . , dk), k < n A in 0..1 některé proměnné mají přiřazenu hodnotu B #= 1 Úplné ohodnocení proměnných (d1, . . . , dn) C in 0..2 všechny proměnné mají přiřazenu hodnotu A #\= B, B #\= C Řešení CSP úplné ohodnocení proměnných, které splňuje všechna omezení (d1, . . . , dn) D1 × . . . × Dn je řešení (X, D, C) A=0,B=1,C=2 pro každé ci C na xi1, . . . xik platí (di1, . . . dik ) ci Hana Rudová, Omezující podmínky, 20. prosince 2006 10 Úvod do CP Řešení CSP Částečné ohodnocení proměnných (d1, . . . , dk), k < n A in 0..1 některé proměnné mají přiřazenu hodnotu B #= 1 Úplné ohodnocení proměnných (d1, . . . , dn) C in 0..2 všechny proměnné mají přiřazenu hodnotu A #\= B, B #\= C Řešení CSP úplné ohodnocení proměnných, které splňuje všechna omezení (d1, . . . , dn) D1 × . . . × Dn je řešení (X, D, C) A=0,B=1,C=2 pro každé ci C na xi1, . . . xik platí (di1, . . . dik ) ci Hledáme: jedno řešení nebo všechna řešení nebo optimální řešení (vzhledem k objektivní funkci) Hana Rudová, Omezující podmínky, 20. prosince 2006 10 Úvod do CP Přístup CP k programování Formulace daného problému pomocí omezení: modelování Řešení vybrané reprezentace pomocí doménově specifických metod obecných metod Hana Rudová, Omezující podmínky, 20. prosince 2006 11 Úvod do CP Obecné metody A in 0..1, B #= 1, C in 0..3, A #\= B, B #\= C Algoritmy propagace omezení 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 pro výpočet lokální konzistence aproximují tak globální konzistenci Hana Rudová, Omezující podmínky, 20. prosince 2006 12 Úvod do CP Obecné metody A in 0..1, B #= 1, C in 0..3, A #\= B, B #\= C Algoritmy propagace omezení 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 pro výpočet lokální konzistence aproximují tak globální konzistenci 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, 20. prosince 2006 12 Úvod do CP Doménově specifické metody Specializované algoritmy Nazývány řešiče omezení (constraint solvers) Příklady: program pro řešení systému lineárních rovnic knihovny pro lineární programování implementace unifikačního algoritmu Hana Rudová, Omezující podmínky, 20. prosince 2006 13 Úvod do CP Doménově specifické metody Specializované algoritmy Nazývány řešiče omezení (constraint solvers) Příklady: program pro řešení systému lineárních rovnic knihovny pro lineární programování implementace unifikačního algoritmu Programování s omezujícími podmínkami široký pojem zahrnující řadu oblastí 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 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, 20. prosince 2006 13 Úvod do CP Historie 1963 interaktivní grafika (Sutherland: Sketchpad) 1970 sít' omezení (Montanari) 1977 algoritmy pro sítě omezení (Mackworth) Polovina 80. let: logické programování omezujícími podmínkami 1984 ECLi PSe Prolog, ECRC Mnichov, později IC-PARC Londýn 1985 SICStus Prolog, Swedish Institute of Computer Science (SICS) 1987 ILOG, komerční firma, C++ implementace Od 1990: komerční využití Už v roce 1996: výnos řádově stovky milionů dolarů Hana Rudová, Omezující podmínky, 20. prosince 2006 14 Úvod do CP Algebrogram Přiřad'te cifry 0, . . . 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: SEND + MORE MONEY různá písmena mají přiřazena různé cifry S a M nejsou 0 Hana Rudová, Omezující podmínky, 20. prosince 2006 15 Úvod do CP Algebrogram Přiřad'te cifry 0, . . . 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: SEND + MORE MONEY různá písmena mají přiřazena různé cifry S a M nejsou 0 Jediné řešení: 9567 + 1085 10652 Hana Rudová, Omezující podmínky, 20. prosince 2006 15 Úvod do CP Algebrogram Přiřad'te cifry 0, . . . 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: SEND + MORE MONEY různá písmena mají přiřazena různé cifry S a M nejsou 0 Jediné řešení: 9567 + 1085 10652 Proměnné: S,E,N,D,M,O,R,Y Domény: [1..9] pro S,M [0..9] pro E,N,D,O,R,Y Hana Rudová, Omezující podmínky, 20. prosince 2006 15 Úvod do CP Algebrogram: alternativy pro omezení rovnosti 1 omezení rovnosti 1000*S + 100*E + 10*N + D SEND + 1000*M + 100*O + 10*R + E + MORE #= 10000*M + 1000*O + 100*N + 10*E + Y MONEY Hana Rudová, Omezující podmínky, 20. prosince 2006 16 Úvod do CP Algebrogram: alternativy pro omezení rovnosti 1 omezení rovnosti 1000*S + 100*E + 10*N + D SEND + 1000*M + 100*O + 10*R + E + MORE #= 10000*M + 1000*O + 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, P1 + N + R #= 10*P2 + E, P2 + E + O #= 10*P3 + N, P3 + S + M #= 10*P4 + O P4 #= M Hana Rudová, Omezující podmínky, 20. prosince 2006 16 Úvod do CP Algebrogram: alternativy pro omezení nerovnosti 28 omezení nerovnosti: X=Y pro X,Y {S,E,N,D,M,O,R,Y}, X Y Hana Rudová, Omezující podmínky, 20. prosince 2006 17 Úvod do CP Algebrogram: alternativy pro omezení nerovnosti 28 omezení nerovnosti: X=Y pro X,Y {S,E,N,D,M,O,R,Y}, X Y 1 omezení pro nerovnost pro proměnné x1, . . . , xn s doménami D1, . . . , Dn: all_different (x1, . . . , xn) := {(d1, . . . , dn)di = dj pro i = j} použití: all_different(S,E,N,D,M,O,R,Y) Hana Rudová, Omezující podmínky, 20. prosince 2006 17 Úvod do CP Algebrogram: alternativy pro omezení nerovnosti 28 omezení nerovnosti: X=Y pro X,Y {S,E,N,D,M,O,R,Y}, X Y 1 omezení pro nerovnost pro proměnné x1, . . . , xn s doménami D1, . . . , Dn: all_different (x1, . . . , xn) := {(d1, . . . , dn)di = dj pro i = j} použití: all_different(S,E,N,D,M,O,R,Y) Modelování jako problém Celočíselného Programování pro X,Y {S,E,N,D,M,O,R,Y} definuj ZX,Y [0..1] a transformuj X=Y na omezení X-Y 10 - 11×ZX,Y Y-X 11×ZX,Y - 1 Hana Rudová, Omezující podmínky, 20. prosince 2006 17 Úvod do CP Algebrogram: alternativy pro omezení nerovnosti 28 omezení nerovnosti: X=Y pro X,Y {S,E,N,D,M,O,R,Y}, X Y 1 omezení pro nerovnost pro proměnné x1, . . . , xn s doménami D1, . . . , Dn: all_different (x1, . . . , xn) := {(d1, . . . , dn)di = dj pro i = j} použití: all_different(S,E,N,D,M,O,R,Y) Modelování jako problém Celočíselného Programování pro X,Y {S,E,N,D,M,O,R,Y} definuj ZX,Y [0..1] a transformuj X=Y na omezení X-Y 10 - 11×ZX,Y Y-X 11×ZX,Y - 1 X=Y = X 0 c4 : x2 + x5 - x6 = 0 Hana Rudová, Omezující podmínky, 20. prosince 2006 30 Úvod do CP Binární CSP Binární CSP CSP, ve kterém jsou pouze binární podmínky unární podmínky zakódovány do domény proměnné Graf podmínek pro binární CSP není nutné uvažovat hypergraf, stačí graf (podmínka spojuje pouze dva vrcholy) CSP lze transformovat na binární CSP Ekvivalence CSP dva CSP problémy jsou ekvivalentní, pokud mají stejnou množinu řešení Rozšířená ekvivalence CSP ř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, 20. prosince 2006 31 Úvod do CP Duální problém Duální problém: původním omezením odpovídají nové duální proměnné proměnné: k-ární podmínku ci převedeme na duální proměnnou vi s doménou obsahující konzistentní k-tice omezení: pro každou dvojici podmínek ci a cj sdílející proměnné zavedeme binární podmínku mezi vi a vj omezující duální proměnné na k-tice, ve kterých mají sdílené proměnné stejnou hodnotu Příklad proměnné x1, . . . , x6 s doménou {0, 1} omezení c1 : x1 + x2 + x6 = 1 . . . v1 c2 : x1 - x3 + x4 = 1 . . . v2 c3 : x4 + x5 - x6 > 0 . . . v3 c4 : x2 + x5 - x6 = 0 . . . v4 Hana Rudová, Omezující podmínky, 20. prosince 2006 32 Úvod do CP Použití binarizace Konstrukce duálního problému jedna z možných metod binarizace Výhody binarizace získáváme unifikovaný tvar CSP problému řada algoritmů navržena pro binární CSP Ale: značné zvětšení velikosti problému Hana Rudová, Omezující podmínky, 20. prosince 2006 33 Úvod do CP Použití binarizace Konstrukce duálního problému jedna z možných metod binarizace Výhody binarizace získáváme unifikovaný tvar CSP problému řada algoritmů navržena pro binární CSP Ale: značné zvětšení velikosti problému Nebinární podmínky složitější propagační algoritmy lze využít jejich sémantiky pro lepší propagaci příklad: all_different vs. množina binárních nerovností Hana Rudová, Omezující podmínky, 20. prosince 2006 33 Úvod do CP Hranová konzistence Propagace omezení Příklad: proměnné: A,B,C domény: [0..1] pro A [0..1] pro B [0..2] pro C omezení: A=B, B=C, A=C = A[0..1], B[0..1], C=2 Algoritmy pro propagaci omezení (konzistenční techniky) 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, 20. prosince 2006 35 Hranová konzistence Vrcholová konzistence Vrcholová konzistence (node consistency) NC unární podmínky převedeme do domén proměnných Vrchol reprezentující Vi je vrcholově konzistentní: každá hodnota z aktuální domény proměnné Vi splňuje všechny unární podmínky s proměnnou Vi Hana Rudová, Omezující podmínky, 20. prosince 2006 36 Hranová konzistence Vrcholová konzistence Vrcholová konzistence (node consistency) NC unární podmínky převedeme do domén proměnných Vrchol reprezentující Vi je vrcholově konzistentní: každá hodnota z aktuální domény proměnné Vi splňuje všechny unární podmínky s proměnnou Vi CSP problém je vrcholově konzistentní: každý jeho vrchol je vrcholově konzistentní Hana Rudová, Omezující podmínky, 20. prosince 2006 36 Hranová konzistence Hranová konzistence (Arc Consistency AC) Pouze pro binární CSP (až její rozšíření jsou pro nebinární CSP) podmínka odpovídá hraně v grafu podmínek více podmínek na jedné hraně převedeme do jedné podmínky Hrana (Vi, Vj) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Di existuje hodnota y v Dj tak, že ohodnocení [Vi = x, Vj = y] splňuje všechny binární podmínky nad Vi, Vj. Hana Rudová, Omezující podmínky, 20. prosince 2006 37 Hranová konzistence Hranová konzistence (Arc Consistency AC) Pouze pro binární CSP (až její rozšíření jsou pro nebinární CSP) podmínka odpovídá hraně v grafu podmínek více podmínek na jedné hraně převedeme do jedné podmínky Hrana (Vi, Vj) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Di existuje hodnota y v Dj tak, že ohodnocení [Vi = x, Vj = y] splňuje všechny binární podmínky nad Vi, Vj. Hranová konzistence je směrová konzistence hrany (Vi, Vj) nezaručuje konzistenci hrany (Vj, Vi) 1..5 B A last((i, x), j) (x, y) C(i, j) then last((i, x), j) := y else smaž x z Di; DELETED := true return DELETED Hana Rudová, Omezující podmínky, 20. prosince 2006 50 Hranová konzistence Je hranová konzistence dostatečná (úplná)? Použitím AC odstraníme mnoho nekompatibilních hodnot Dostaneme potom řešení problému? NE Víme alespoň zda řešení existuje? NE Hana Rudová, Omezující podmínky, 20. prosince 2006 51 Hranová konzistence Je hranová konzistence dostatečná (úplná)? Použitím AC odstraníme mnoho nekompatibilních hodnot Dostaneme potom řešení problému? NE Víme alespoň zda řešení existuje? NE domain([X,Y,Z],1,2), X #\= Y, Y #\= Z, Z #\= X hranově konzistentní nemá žádné řešení Hana Rudová, Omezující podmínky, 20. prosince 2006 51 Hranová konzistence Je hranová konzistence dostatečná (úplná)? Použitím AC odstraníme mnoho nekompatibilních hodnot Dostaneme potom řešení problému? NE Víme alespoň zda řešení existuje? NE domain([X,Y,Z],1,2), X #\= Y, Y #\= Z, Z #\= X hranově konzistentní nemá žádné řešení Jaký je tedy význam AC? někdy dá řešení přímo nějaká doména se vyprázdní řešení neexistuje všechny domény jsou jednoprvkové máme řešení v obecném případě se alespoň zmenší prohledávaný prostor Hana Rudová, Omezující podmínky, 20. prosince 2006 51 Hranová konzistence Konzistence po cestě Konzistence po cestě (PC path consistency) Jak posílit konzistenci? Budeme se zabývat několika podmínkami najednou. Příklad: A,B,C {0,1}, A=B, B=C, A=C Cesta (V0, V1, . . . , Vm) je konzistentní právě tehdy, když pro každou dvojici hodnot x D0 a y Dm splňující binární podmínky na hraně V0, Vm existuje ohodnocení proměnných V1, . . . Vm-1 takové, že všechny binární podmínky mezi sousedy Vj, Vj+1 jsou splněny CSP je konzistentní po cestě, právě když jsou všechny cesty konzistentní Hana Rudová, Omezující podmínky, 20. prosince 2006 53 Konzistence po cestě Konzistence po cestě (PC path consistency) Jak posílit konzistenci? Budeme se zabývat několika podmínkami najednou. Příklad: A,B,C {0,1}, A=B, B=C, A=C Cesta (V0, V1, . . . , Vm) je konzistentní právě tehdy, když pro každou dvojici hodnot x D0 a y Dm splňující binární podmínky na hraně V0, Vm existuje ohodnocení proměnných V1, . . . Vm-1 takové, že všechny binární podmínky mezi sousedy Vj, Vj+1 jsou splněny CSP je konzistentní po cestě, právě když jsou všechny cesty konzistentní Definice PC nezaručuje, že jsou splněny všechny podmínky nad vrcholy cesty, zabývá se pouze podmínkami mezi sousedy V0 V1 V2 V3 V4 ??? Hana Rudová, Omezující podmínky, 20. prosince 2006 53 Konzistence po cestě PC a cesty délky 2 Zjišt'ování konzistence všech cest není efektivní Stačí ověřit konzistenci cest délky 2 Věta: CSP je PC právě tehdy, když každá cesta délky 2 je PC. Hana Rudová, Omezující podmínky, 20. prosince 2006 54 Konzistence po cestě PC a cesty délky 2 Zjišt'ování konzistence všech cest není efektivní Stačí ověřit konzistenci cest délky 2 Věta: CSP je PC právě tehdy, když každá cesta délky 2 je PC. Důkaz: 1) PC cesty délky 2 jsou PC 2) cesty délky 2 jsou PC 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 + 1 vrcholů V0, V1, . . . , Vn ii) vezmeme libovolné dvě kompatibilní hodnoty x0 D0 a xn Dn iii) podle a) najdeme xn-1 Dn-1 tak, že (x0, xn-1) (xn-1, xn) platí, protože (xn-1, xn),(xn, xn-1) je cesta délky 2 (x0, xn-1), (xn-1, xn) je cesta délky 2, tj. (x0, xn) platí iv) podle indukčního kroku najdeme zbylé hodnoty na cestě V0, V1, . . . , Vn-1 Hana Rudová, Omezující podmínky, 20. prosince 2006 54 Konzistence po cestě PC a cesty délky 2 Zjišt'ování konzistence všech cest není efektivní Stačí ověřit konzistenci cest délky 2 Věta: CSP je PC právě tehdy, když každá cesta délky 2 je PC. Důkaz: 1) PC cesty délky 2 jsou PC 2) cesty délky 2 jsou PC 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 + 1 vrcholů V0, V1, . . . , Vn ii) vezmeme libovolné dvě kompatibilní hodnoty x0 D0 a xn Dn iii) podle a) najdeme xn-1 Dn-1 tak, že (x0, xn-1) (xn-1, xn) platí, protože (xn-1, xn),(xn, xn-1) je cesta délky 2 (x0, xn-1), (xn-1, xn) je cesta délky 2, tj. (x0, xn) platí iv) podle indukčního kroku najdeme zbylé hodnoty na cestě V0, V1, . . . , Vn-1 Definici PC lze tedy upravit tak, že vyžadujeme pouze konzistenci cest délky 2 Hana Rudová, Omezující podmínky, 20. prosince 2006 54 Konzistence po cestě Vztah PC a AC PC AC hrana (i, j) je hranově konzistentní, pokud je (i, j, i) konzistentní po cestě Hana Rudová, Omezující podmínky, 20. prosince 2006 55 Konzistence po cestě Vztah PC a AC PC AC hrana (i, j) je hranově konzistentní, pokud je (i, j, i) konzistentní po cestě AC PC příklad: A,B,C {0,1}, A=B, B=C, A=C je AC, ale není PC, A=0, B=1 nelze rozšířít po cestě (A,C,B) Hana Rudová, Omezující podmínky, 20. prosince 2006 55 Konzistence po cestě Vztah PC a AC PC AC hrana (i, j) je hranově konzistentní, pokud je (i, j, i) konzistentní po cestě AC PC příklad: A,B,C {0,1}, A=B, B=C, A=C je AC, ale není PC, A=0, B=1 nelze rozšířít po cestě (A,C,B) AC vyřazuje nekompatibilní prvky z domény proměnných. Co dělá PC? PC vyřazuje dvojice hodnot 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 B => min(A) = min(B)+1, max(B) = max(A)-1 příklad: A in 4..10, B in 6..18, A #> B min(A) = 6+1 A in 7..10 max(B) = 10-1 B in 6..9 Hana Rudová, Omezující podmínky, 20. prosince 2006 74 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é tedy došlo ke změně mezí domény proměnné Konzistence mezí pro nerovnice A #> B => min(A) = min(B)+1, max(B) = max(A)-1 příklad: A in 4..10, B in 6..18, A #> B min(A) = 6+1 A in 7..10 max(B) = 10-1 B in 6..9 podobně: A #< B, A #>= B, A #=< B Jak je to tedy pro nebinární omezení? Hana Rudová, Omezující podmínky, 20. prosince 2006 74 Propagace pro nebinární omezení Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) Hana Rudová, Omezující podmínky, 20. prosince 2006 75 Propagace pro nebinární omezení Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) změna min(A)vyvolá pouze změnu min(B) a min(C) změna max(A)vyvolá pouze změnu max(B) a max(C), ... Hana Rudová, Omezující podmínky, 20. prosince 2006 75 Propagace pro nebinární omezení Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) změna min(A)vyvolá pouze změnu min(B) a min(C) změna max(A)vyvolá pouze změnu max(B) a max(C), ... Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 Hana Rudová, Omezující podmínky, 20. prosince 2006 75 Propagace pro nebinární omezení Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) změna min(A)vyvolá pouze změnu min(B) a min(C) změna max(A)vyvolá pouze změnu max(B) a max(C), ... Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 min(A)=1+2, max(A)=10+2 A in 3..10 min(B)=1-2, max(B)=10-2 B in 1..8 Hana Rudová, Omezující podmínky, 20. prosince 2006 75 Propagace pro nebinární omezení Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) změna min(A)vyvolá pouze změnu min(B) a min(C) změna max(A)vyvolá pouze změnu max(B) a max(C), ... Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 min(A)=1+2, max(A)=10+2 A in 3..10 min(B)=1-2, max(B)=10-2 B in 1..8 A #> 5 min(A)=6 A in 6..10 min(B)=6-2 B in 4..8 (nové vyvolání A #= B + 2) Hana Rudová, Omezující podmínky, 20. prosince 2006 75 Propagace pro nebinární omezení Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) změna min(A)vyvolá pouze změnu min(B) a min(C) změna max(A)vyvolá pouze změnu max(B) a max(C), ... Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 min(A)=1+2, max(A)=10+2 A in 3..10 min(B)=1-2, max(B)=10-2 B in 1..8 A #> 5 min(A)=6 A in 6..10 min(B)=6-2 B in 4..8 (nové vyvolání A #= B + 2) A #\= 8 A in (6..7) \/ (9..10) (meze stejné, k propagaci A #= B + 2 nedojde) Hana Rudová, Omezující podmínky, 20. prosince 2006 75 Propagace pro nebinární omezení Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) změna min(A)vyvolá pouze změnu min(B) a min(C) změna max(A)vyvolá pouze změnu max(B) a max(C), ... Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 min(A)=1+2, max(A)=10+2 A in 3..10 min(B)=1-2, max(B)=10-2 B in 1..8 A #> 5 min(A)=6 A in 6..10 min(B)=6-2 B in 4..8 (nové vyvolání A #= B + 2) A #\= 8 A in (6..7) \/ (9..10) (meze stejné, k propagaci A #= B + 2 nedojde) Vyzkoušejte si: A #= B - C, A #>= B + C Hana Rudová, Omezující podmínky, 20. prosince 2006 75 Propagace pro nebinární omezení Definice konzistence mezí Hodnota a proměnné x scope(C) má intervalovou podporu t v C, jestliže t C a platí a = t[x] příklad: a = 1, t = (1, 5, 7) Hana Rudová, Omezující podmínky, 20. prosince 2006 76 Propagace pro nebinární omezení Definice konzistence mezí Hodnota a proměnné x scope(C) má intervalovou podporu t v C, jestliže t C a platí a = t[x] příklad: a = 1, t = (1, 5, 7) pro každé y scope(C) platí t[y] [min(Dy), max(Dy)] př. (pokrač.) y = 5, z = 7, Dy = Dz = {1, 2, 4, 5, 10} Hana Rudová, Omezující podmínky, 20. prosince 2006 76 Propagace pro nebinární omezení Definice konzistence mezí Hodnota a proměnné x scope(C) má intervalovou podporu t v C, jestliže t C a platí a = t[x] příklad: a = 1, t = (1, 5, 7) pro každé y scope(C) platí t[y] [min(Dy), max(Dy)] př. (pokrač.) y = 5, z = 7, Dy = Dz = {1, 2, 4, 5, 10} 5 = t[y] i 7 = t[z] mají intervalovou podporu Hana Rudová, Omezující podmínky, 20. prosince 2006 76 Propagace pro nebinární omezení Definice konzistence mezí Hodnota a proměnné x scope(C) má intervalovou podporu t v C, jestliže t C a platí a = t[x] příklad: a = 1, t = (1, 5, 7) pro každé y scope(C) platí t[y] [min(Dy), max(Dy)] př. (pokrač.) y = 5, z = 7, Dy = Dz = {1, 2, 4, 5, 10} 5 = t[y] i 7 = t[z] mají intervalovou podporu Srovnání: doménová podpora GAC pro každé y scope(C) platí t[y] Dy Hana Rudová, Omezující podmínky, 20. prosince 2006 76 Propagace pro nebinární omezení Definice konzistence mezí Hodnota a proměnné x scope(C) má intervalovou podporu t v C, jestliže t C a platí a = t[x] příklad: a = 1, t = (1, 5, 7) pro každé y scope(C) platí t[y] [min(Dy), max(Dy)] př. (pokrač.) y = 5, z = 7, Dy = Dz = {1, 2, 4, 5, 10} 5 = t[y] i 7 = t[z] mají intervalovou podporu Srovnání: doménová podpora GAC pro každé y scope(C) platí t[y] Dy př. (pokrač.) 7 = t[z] nemá doménovou podporu Hana Rudová, Omezující podmínky, 20. prosince 2006 76 Propagace pro nebinární omezení Definice konzistence mezí Hodnota a proměnné x scope(C) má intervalovou podporu t v C, jestliže t C a platí a = t[x] příklad: a = 1, t = (1, 5, 7) pro každé y scope(C) platí t[y] [min(Dy), max(Dy)] př. (pokrač.) y = 5, z = 7, Dy = Dz = {1, 2, 4, 5, 10} 5 = t[y] i 7 = t[z] mají intervalovou podporu Srovnání: doménová podpora GAC pro každé y scope(C) platí t[y] Dy př. (pokrač.) 7 = t[z] nemá doménovou podporu Omezení má konzistentní meze, jestliže každá hodnota a proměnné x scope(C) má intervalovou podporu v C CSP má konzistentní meze všechna jeho omezení mají konzistentní meze Hana Rudová, Omezující podmínky, 20. prosince 2006 76 Propagace pro nebinární omezení Globalní podmínky element(N,List,X) omezení na konkrétní prvek seznamu global_cardinality(List, [Key-Count | _ ]) omezení na počet prvků daného typu v seznamu Hana Rudová, Omezující podmínky, 20. prosince 2006 77 Propagace pro nebinární omezení Globalní podmínky element(N,List,X) omezení na konkrétní prvek seznamu global_cardinality(List, [Key-Count | _ ]) omezení na počet prvků daného typu v seznamu all_distinct(List) všechny proměnné různé Hana Rudová, Omezující podmínky, 20. prosince 2006 77 Propagace pro nebinární omezení Globalní podmínky element(N,List,X) omezení na konkrétní prvek seznamu global_cardinality(List, [Key-Count | _ ]) omezení na počet prvků daného typu v seznamu all_distinct(List) všechny proměnné různé serialized(Starts,Durations) disjunktivní rozvrhování disjoint2(Rectangles) nepřekrývání obdélníků cumulative(Starts,Durations,Resources,Limit) kumulativní rozvrhování Hana Rudová, Omezující podmínky, 20. prosince 2006 77 Propagace pro nebinární omezení Výskyty prvků v seznamu element(N,List,X) N-tý prvek v seznamu List je roven X | ?- A in 2..10, B in 1..3, element( N, [A,B], X ), Hana Rudová, Omezující podmínky, 20. prosince 2006 78 Propagace pro nebinární omezení Výskyty prvků v seznamu element(N,List,X) N-tý prvek v seznamu List je roven X | ?- A in 2..10, B in 1..3, element( N, [A,B], X ), X #< 2. B = 1, N = 2, X = 1, A in 2..10 Hana Rudová, Omezující podmínky, 20. prosince 2006 78 Propagace pro nebinární omezení Výskyty prvků v seznamu element(N,List,X) N-tý prvek v seznamu List je roven X | ?- A in 2..10, B in 1..3, element( N, [A,B], X ), X #< 2. B = 1, N = 2, X = 1, A in 2..10 global_cardinality(List, KeyCounts) pro každý prvek Key-Count seznamu KeyCounts platí: Count prvků seznamu List se rovná klíči Key každé Key je celé číslo a vyskytuje se mezi klíči maximálně jednou každé Count je nezáporné celé číslo nebo doménová proměnná | ?- A in 1..3, B in 1..3, global_cardinality( [A,B], [1-N,2-2]). Hana Rudová, Omezující podmínky, 20. prosince 2006 78 Propagace pro nebinární omezení Výskyty prvků v seznamu element(N,List,X) N-tý prvek v seznamu List je roven X | ?- A in 2..10, B in 1..3, element( N, [A,B], X ), X #< 2. B = 1, N = 2, X = 1, A in 2..10 global_cardinality(List, KeyCounts) pro každý prvek Key-Count seznamu KeyCounts platí: Count prvků seznamu List se rovná klíči Key každé Key je celé číslo a vyskytuje se mezi klíči maximálně jednou každé Count je nezáporné celé číslo nebo doménová proměnná | ?- A in 1..3, B in 1..3, global_cardinality( [A,B], [1-N,2-2]). A = 2, B = 2, N = 0 Hana Rudová, Omezující podmínky, 20. prosince 2006 78 Propagace pro nebinární omezení Příklad: rozvrhování zaměstnanců vytvoření rozvrhu pro zaměstnance pracující na směny A = {R,D,N,Z,V} ráno, den, noc, záloha, volno P = {Petr,Pavel,Marie,...} W = {Po,Út,St,Čt,...} Po Út St Čt . . . Petr R N V R Pavel R Z R N Marie N V D D . . . Hana Rudová, Omezující podmínky, 20. prosince 2006 79 Propagace pro nebinární omezení Příklad: rozvrhování zaměstnanců vytvoření rozvrhu pro zaměstnance pracující na směny A = {R,D,N,Z,V} ráno, den, noc, záloha, volno P = {Petr,Pavel,Marie,...} W = {Po,Út,St,Čt,...} Po Út St Čt . . . Petr R N V R Pavel R Z R N Marie N V D D . . . matice doménových proměnných: PetrPo, PetrUt, ..., PavelPo,... Hana Rudová, Omezující podmínky, 20. prosince 2006 79 Propagace pro nebinární omezení Příklad: rozvrhování zaměstnanců vytvoření rozvrhu pro zaměstnance pracující na směny A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno P = {Petr,Pavel,Marie,...} W = {Po,Út,St,Čt,...} Po Út St Čt . . . Petr R N V R Pavel R Z R N Marie N V D D . . . matice doménových proměnných: PetrPo, PetrUt, ..., PavelPo,... Hana Rudová, Omezující podmínky, 20. prosince 2006 79 Propagace pro nebinární omezení Příklad: rozvrhování zaměstnanců vytvoření rozvrhu pro zaměstnance pracující na směny A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno P = {Petr,Pavel,Marie,...} W = {Po,Út,St,Čt,...} Po Út St Čt . . . Petr R N V R Pavel R Z R N Marie N V D D . . . matice doménových proměnných: PetrPo, PetrUt, ..., PavelPo,... každý den: minimální a maximální počet zaměstnanců každou směnu Hana Rudová, Omezující podmínky, 20. prosince 2006 79 Propagace pro nebinární omezení Příklad: rozvrhování zaměstnanců vytvoření rozvrhu pro zaměstnance pracující na směny A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno P = {Petr,Pavel,Marie,...} W = {Po,Út,St,Čt,...} Po Út St Čt . . . Petr R N V R Pavel R Z R N Marie N V D D . . . matice doménových proměnných: PetrPo, PetrUt, ..., PavelPo,... každý den: minimální a maximální počet zaměstnanců každou směnu R1 in MinRano1..MaxRano1, D1 in MinDen1..MaxDen1, ... Hana Rudová, Omezující podmínky, 20. prosince 2006 79 Propagace pro nebinární omezení Příklad: rozvrhování zaměstnanců vytvoření rozvrhu pro zaměstnance pracující na směny A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno P = {Petr,Pavel,Marie,...} W = {Po,Út,St,Čt,...} Po Út St Čt . . . Petr R N V R Pavel R Z R N Marie N V D D . . . matice doménových proměnných: PetrPo, PetrUt, ..., PavelPo,... každý den: minimální a maximální počet zaměstnanců každou směnu R1 in MinRano1..MaxRano1, D1 in MinDen1..MaxDen1, ... global_cardinality( [PetrPo,PavelPo,MariePo,...], [1-R1,2-D1,...,5-V1] ) Hana Rudová, Omezující podmínky, 20. prosince 2006 79 Propagace pro nebinární omezení Příklad: rozvrhování zaměstnanců vytvoření rozvrhu pro zaměstnance pracující na směny A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno P = {Petr,Pavel,Marie,...} W = {Po,Út,St,Čt,...} Po Út St Čt . . . Petr R N V R Pavel R Z R N Marie N V D D . . . matice doménových proměnných: PetrPo, PetrUt, ..., PavelPo,... každý den: minimální a maximální počet zaměstnanců každou směnu R1 in MinRano1..MaxRano1, D1 in MinDen1..MaxDen1, ... global_cardinality( [PetrPo,PavelPo,MariePo,...], [1-R1,2-D1,...,5-V1] ) pro každého zaměstnance: minimální a maximální počet typu směny za týden Hana Rudová, Omezující podmínky, 20. prosince 2006 79 Propagace pro nebinární omezení Příklad: rozvrhování zaměstnanců vytvoření rozvrhu pro zaměstnance pracující na směny A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno P = {Petr,Pavel,Marie,...} W = {Po,Út,St,Čt,...} Po Út St Čt . . . Petr R N V R Pavel R Z R N Marie N V D D . . . matice doménových proměnných: PetrPo, PetrUt, ..., PavelPo,... každý den: minimální a maximální počet zaměstnanců každou směnu R1 in MinRano1..MaxRano1, D1 in MinDen1..MaxDen1, ... global_cardinality( [PetrPo,PavelPo,MariePo,...], [1-R1,2-D1,...,5-V1] ) pro každého zaměstnance: minimální a maximální počet typu směny za týden R2 in MinRano2..MaxRano2, D2 in MinDen2..MaxDen2, ... Hana Rudová, Omezující podmínky, 20. prosince 2006 79 Propagace pro nebinární omezení Příklad: rozvrhování zaměstnanců vytvoření rozvrhu pro zaměstnance pracující na směny A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno P = {Petr,Pavel,Marie,...} W = {Po,Út,St,Čt,...} Po Út St Čt . . . Petr R N V R Pavel R Z R N Marie N V D D . . . matice doménových proměnných: PetrPo, PetrUt, ..., PavelPo,... každý den: minimální a maximální počet zaměstnanců každou směnu R1 in MinRano1..MaxRano1, D1 in MinDen1..MaxDen1, ... global_cardinality( [PetrPo,PavelPo,MariePo,...], [1-R1,2-D1,...,5-V1] ) pro každého zaměstnance: minimální a maximální počet typu směny za týden R2 in MinRano2..MaxRano2, D2 in MinDen2..MaxDen2, ... global_cardinality( [PetrPo,PetrUt,...,PetrNe], [1-R2,2-D2,...,5-V2] ) Hana Rudová, Omezující podmínky, 20. prosince 2006 79 Propagace pro nebinární omezení Všechny proměnné různé all_distinct(Variables), all_different(Variables) Proměnné v seznamu Variables jsou různé all_distinct a all_different se liší úrovní propagace all_distinct má úplnou propagaci all_different má slabší (neúplnou) propagaci Hana Rudová, Omezující podmínky, 20. prosince 2006 80 Propagace pro nebinární omezení Všechny proměnné různé all_distinct(Variables), all_different(Variables) Proměnné v seznamu Variables jsou různé all_distinct a all_different se liší úrovní propagace all_distinct má úplnou propagaci all_different má slabší (neúplnou) propagaci učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Příklad: učitelé musí učit v různé hodiny Hana Rudová, Omezující podmínky, 20. prosince 2006 80 Propagace pro nebinární omezení Všechny proměnné různé all_distinct(Variables), all_different(Variables) Proměnné v seznamu Variables jsou různé all_distinct a all_different se liší úrovní propagace all_distinct má úplnou propagaci all_different má slabší (neúplnou) propagaci učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Příklad: učitelé musí učit v různé hodiny all_distinct([Jan,Petr,Anna,Ota,Eva,Marie]) Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr in 3..4, Eva in 3..4 Hana Rudová, Omezující podmínky, 20. prosince 2006 80 Propagace pro nebinární omezení Všechny proměnné různé all_distinct(Variables), all_different(Variables) Proměnné v seznamu Variables jsou různé all_distinct a all_different se liší úrovní propagace all_distinct má úplnou propagaci all_different má slabší (neúplnou) propagaci učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Příklad: učitelé musí učit v různé hodiny all_distinct([Jan,Petr,Anna,Ota,Eva,Marie]) Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr in 3..4, Eva in 3..4 all_different([Jan,Petr,Anna,Ota,Eva,Marie]) Jan in 3..6, Petr in 3..4, Anna in 2..5, Ota in 2..4, Eva in 3..4, Marie in 1..6 Hana Rudová, Omezující podmínky, 20. prosince 2006 80 Propagace pro nebinární omezení Naivní propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 Hana Rudová, Omezující podmínky, 20. prosince 2006 81 Propagace pro nebinární omezení Naivní propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Hana Rudová, Omezující podmínky, 20. prosince 2006 81 Propagace pro nebinární omezení Naivní propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: {X1, . . . , Xk} V : card{D1 Dk} k Hana Rudová, Omezující podmínky, 20. prosince 2006 81 Propagace pro nebinární omezení Naivní propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: {X1, . . . , Xk} V : card{D1 Dk} k stačí hledat Hallův interval I: velikost intervalu I je rovna počtu proměnných, jejichž doména je v I Hana Rudová, Omezující podmínky, 20. prosince 2006 81 Propagace pro nebinární omezení Naivní propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: {X1, . . . , Xk} V : card{D1 Dk} k stačí hledat Hallův interval I: velikost intervalu I je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo U = {X1, . . . , Xk}, dom(U) = {D1 Dk} card(U) = card(dom(U)) v dom(U), X (V - U), X = v Hana Rudová, Omezující podmínky, 20. prosince 2006 81 Propagace pro nebinární omezení Naivní propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: {X1, . . . , Xk} V : card{D1 Dk} k stačí hledat Hallův interval I: velikost intervalu I je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo U = {X1, . . . , Xk}, dom(U) = {D1 Dk} card(U) = card(dom(U)) v dom(U), X (V - U), X = v hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné Hana Rudová, Omezující podmínky, 20. prosince 2006 81 Propagace pro nebinární omezení Naivní propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: {X1, . . . , Xk} V : card{D1 Dk} k stačí hledat Hallův interval I: velikost intervalu I je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo U = {X1, . . . , Xk}, dom(U) = {D1 Dk} card(U) = card(dom(U)) v dom(U), X (V - U), X = v hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné Složitost hledání všech podmnožin množiny n proměnných (naivní) O(2n ) Hana Rudová, Omezující podmínky, 20. prosince 2006 81 Propagace pro nebinární omezení Párování v bipartitních grafech Efektivní propagaci pro all_distinct lze založit na párování v bipartitních grafech (Régin 94) Bipartitní graf uzly grafu rozdělené do dvou množin 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 Maximální párování párování, které má maximální počet hran 01 01 01 01 01 01 01 01 01 01 01 01 01 01 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 X a Hana Rudová, Omezující podmínky, 20. prosince 2006 82 Propagace pro nebinární omezení Párování v bipartitních grafech Efektivní propagaci pro all_distinct lze založit na párování v bipartitních grafech (Régin 94) Bipartitní graf uzly grafu rozdělené do dvou množin 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 Maximální párování párování, které má maximální počet hran CSP jako bipartitní graf jedna množina vrcholů reprezentuje proměnné druhá množina vrcholů reprezentuje hodnoty proměnných hrana z proměnné X do hodnoty a říká, že proměnná X může nabývat hodnoty a 01 01 01 01 01 01 01 01 01 01 01 01 01 01 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 111111111111 111111111111 X a Hana Rudová, Omezující podmínky, 20. prosince 2006 82 Propagace pro nebinární omezení all_distinct ­ párování v bipartitních grafech II. sjednocení domén proměnné proměnnýchInicializace vypočti maximální párování odstraň všechny hrany, které nepatří do žádného maximálního párování Hana Rudová, Omezující podmínky, 20. prosince 2006 83 Propagace pro nebinární omezení all_distinct ­ párování v bipartitních grafech II. sjednocení domén proměnné proměnnýchInicializace vypočti maximální párování odstraň všechny hrany, které nepatří do žádného maximálního párování Propagace zmenšené domény odstraň odpovídající hrany vypočti nové maximální párování odstraň všechny hrany, které nepatří do žádného maximálního párování Hana Rudová, Omezující podmínky, 20. prosince 2006 83 Propagace pro nebinární omezení all_distinct ­ párování v bipartitních grafech II. sjednocení domén proměnné proměnnýchInicializace vypočti maximální párování odstraň všechny hrany, které nepatří do žádného maximálního párování Propagace zmenšené domény odstraň odpovídající hrany vypočti nové maximální párování odstraň všechny hrany, které nepatří do žádného maximálního párování Algoritmus založen na doménové konzistenci každé maximální párování definuje doménovou podporu složitost O(n2 k2 ), n . . . počet proměnných, k . . . maximální velikost domény Hana Rudová, Omezující podmínky, 20. prosince 2006 83 Propagace pro nebinární omezení all_distinct ­ párování v bipartitních grafech II. sjednocení domén proměnné proměnnýchInicializace vypočti maximální párování odstraň všechny hrany, které nepatří do žádného maximálního párování Propagace zmenšené domény odstraň odpovídající hrany vypočti nové maximální párování odstraň všechny hrany, které nepatří do žádného maximálního párování Algoritmus založen na doménové konzistenci každé maximální párování definuje doménovou podporu složitost O(n2 k2 ), n . . . počet proměnných, k . . . maximální velikost domény efektivnější algoritmus využívá konzistenci mezí O(n log n) ­ kontrola hraničních bodů Hallových intervalů (Puget 1998) Hana Rudová, Omezující podmínky, 20. prosince 2006 83 Propagace pro nebinární omezení Disjunktivní rozvrhování serialized(Starts,Durations) Rozvržení úloh zadaných startovním časem (seznam Starts) a dobou trvání (seznam nezáporných Durations) tak, aby se nepřekrývaly Hana Rudová, Omezující podmínky, 20. prosince 2006 84 Propagace pro nebinární omezení Disjunktivní rozvrhování serialized(Starts,Durations) Rozvržení úloh zadaných startovním časem (seznam Starts) a dobou trvání (seznam nezáporných Durations) tak, aby se nepřekrývaly příklad s konstantami: serialized([0,3,5],[2,1,1]) Hana Rudová, Omezující podmínky, 20. prosince 2006 84 Propagace pro nebinární omezení Disjunktivní rozvrhování serialized(Starts,Durations) Rozvržení úloh zadaných startovním časem (seznam Starts) a dobou trvání (seznam nezáporných Durations) tak, aby se nepřekrývaly příklad s konstantami: serialized([0,3,5],[2,1,1]) příklad: vytvoření rozvrhu, za předpokladu, že doba trvání hodin není stejná Hana Rudová, Omezující podmínky, 20. prosince 2006 84 Propagace pro nebinární omezení Disjunktivní rozvrhování serialized(Starts,Durations) Rozvržení úloh zadaných startovním časem (seznam Starts) a dobou trvání (seznam nezáporných Durations) tak, aby se nepřekrývaly příklad s konstantami: serialized([0,3,5],[2,1,1]) příklad: vytvoření rozvrhu, za předpokladu, že doba trvání hodin není stejná D in 1..2, C = 3, serialized([Jan,Petr,Anna,Ota,Eva,Marie], [D,D,D,C,C,C]) Hana Rudová, Omezující podmínky, 20. prosince 2006 84 Propagace pro nebinární omezení Disjunktivní rozvrhování: princip algoritmu Hledání hran (edge finding) ­ Baptiste & Le Pape, 1996 Hledáme úlohu, která předchází nebo následuje množinu jiných úloh SB in 6..12, DB#=4, SC in 7..10, DC#=5, SA in 4..14, DA#=2 Co se stane, pokud nebude aktivita A zpracována jako první? C(5) B(4) A(2) 7 15 16 4 6 16 Hana Rudová, Omezující podmínky, 20. prosince 2006 85 Propagace pro nebinární omezení Disjunktivní rozvrhování: princip algoritmu Hledání hran (edge finding) ­ Baptiste & Le Pape, 1996 Hledáme úlohu, která předchází nebo následuje množinu jiných úloh SB in 6..12, DB#=4, SC in 7..10, DC#=5, SA in 4..14, DA#=2 Co se stane, pokud nebude aktivita A zpracována jako první? C(5) B(4) A(2) 7 15 16 4 6 16 Pro A,B,C není dost času, a tedy aktivita A musí být první A(2) B(4) C(5) 4 7 6 16 157 Hana Rudová, Omezující podmínky, 20. prosince 2006 85 Propagace pro nebinární omezení Nepřekrývání obdélníků disjoint2(Rectangles) disjoint1(Lines) disjoint2( [Name(X, Delka, Y, Vyska) | _ ] ) umístění obdélníků ve dvourozměrném prostoru doménové proměnné X,Y,Delka,Vyska mohou být z oboru celých čísel Hana Rudová, Omezující podmínky, 20. prosince 2006 86 Propagace pro nebinární omezení Nepřekrývání obdélníků disjoint2(Rectangles) disjoint1(Lines) disjoint2( [Name(X, Delka, Y, Vyska) | _ ] ) umístění obdélníků ve dvourozměrném prostoru doménové proměnné X,Y,Delka,Vyska mohou být z oboru celých čísel příklad s konstantami: disjoint2([rect(0,3,0,1),rect(1,3,1,2),rect(4,2,2,-2)]) 3 4 5 6 2 3 2 1 1 1 3 2 Hana Rudová, Omezující podmínky, 20. prosince 2006 86 Propagace pro nebinární omezení Nepřekrývání obdélníků disjoint2(Rectangles) disjoint1(Lines) disjoint2( [Name(X, Delka, Y, Vyska) | _ ] ) umístění obdélníků ve dvourozměrném prostoru doménové proměnné X,Y,Delka,Vyska mohou být z oboru celých čísel příklad s konstantami: disjoint2([rect(0,3,0,1),rect(1,3,1,2),rect(4,2,2,-2)]) 3 4 5 6 2 3 2 1 1 1 3 2 příklad: vytvoření rozvrhu za předpokladu, že učitelé učí v různých místnostech D in 1..2, C = 3, disjoint2( class(Jan,D,M1,1), class(Petr,D,M2,1), class(Marie,D,M3,1), ...] ) Hana Rudová, Omezující podmínky, 20. prosince 2006 86 Propagace pro nebinární omezení Kumulativní rozvrhování cumulative(Starts,Durations,Resources,Limit) Úlohy jsou zadány startovním časem (seznam Starts), dobou trvání (seznam Durations) a požadovanou kapacitou zdroje (seznam Resources) Rozvržení úloh tak, aby celková kapacita zdroje nikdy nepřekročila Limit Hana Rudová, Omezující podmínky, 20. prosince 2006 87 Propagace pro nebinární omezení Kumulativní rozvrhování cumulative(Starts,Durations,Resources,Limit) Úlohy jsou zadány startovním časem (seznam Starts), dobou trvání (seznam Durations) a požadovanou kapacitou zdroje (seznam Resources) Rozvržení úloh tak, aby celková kapacita zdroje nikdy nepřekročila Limit Příklad s konstantami: cumulative([0,1,3],[4,2,3],[1,2,2],3) Hana Rudová, Omezující podmínky, 20. prosince 2006 87 Propagace pro nebinární omezení Základní konzistenční algoritmus Základem konzistenčního algoritmu pro nebinární omezení je AC-3 Opakovaně se provádí revize podmínek, dokud se mění domény procedure NonBinary-AC-3(C) Q := C % seznam omezení while Q není prázdná do vyber a smaž c z Q revise(c,Q) end AC-3 Hana Rudová, Omezující podmínky, 20. prosince 2006 88 Propagace pro nebinární omezení Základní konzistenční algoritmus Základem konzistenčního algoritmu pro nebinární omezení je AC-3 Opakovaně se provádí revize podmínek, dokud se mění domény procedure NonBinary-AC-3(C) Q := C % seznam omezení while Q není prázdná do vyber a smaž c z Q revise(c,Q) end AC-3 Speciální revise procedury jsou definovány v závislosti na typu omezení, tj. revise procedura může implementovat obecnou hranovou konzistenci konzistenci mezí konzistenční algoritmy pro globální podmínky jako all_distinct Hana Rudová, Omezující podmínky, 20. prosince 2006 88 Propagace pro nebinární omezení Konzistenční algoritmus s frontou proměnných 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 procedure Nonbinary-AC-3-with-Variables(Q) while Q non empty do vyber a smaž Vj Q for C takové, že Vj scope(C) do W := revise(Vj, C) // W je množina proměnných jejichž, doména se změnila if Vi W taková, že Di = then return fail Q := Q {W} end Non-binary-consistency Hana Rudová, Omezující podmínky, 20. prosince 2006 89 Propagace pro nebinární omezení Implementace konzistenčních algoritmů 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) obecný algoritmus vyvolá revise při libovolné změně domény udržuje doménovou (obecnou hranovou) konzistenci vyvolání revize pouze při změně mezí: konzistence mezí vyvolání revize při instanciaci proměnné Hana Rudová, Omezující podmínky, 20. prosince 2006 90 Propagace pro nebinární omezení Implementace konzistenčních algoritmů 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) obecný algoritmus vyvolá revise při libovolné změně domény udržuje doménovou (obecnou hranovou) konzistenci vyvolání revize pouze při změně mezí: konzistence mezí vyvolání revize při instanciaci proměnné pro každou proměnnou lze použít různé události Je potřeba navrhnout propagaci přes podmínku 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, 20. prosince 2006 90 Propagace pro nebinární omezení Příklad: dispatch_global less_then(A,B) :- fd_global(a2b(A,B),no_state,[min(A)]), Implementace podmínky A fd_min(A,MinA), fd_max(A,MaxA), fd_min(B,MinB), ( MaxA Actions = [exit] ; LowerBoundB is MinA+1, min(B) = min(A)+1 Actions = [B in LowerBoundB..sup] ). clpfd:dispatch_global(b2a(A,B),S,S,Actions) :- fd_max(A,MaxA), fd_min(B,MinB), fd_max(B,MaxB), ( MaxA Actions = [exit] ; UpperBoundA is MaxB-1, max(A) = max(B)-1 Actions = [A in inf..UpperBoundA] ). Hana Rudová, Omezující podmínky, 20. prosince 2006 91 Propagace pro nebinární omezení Implementace vlastních omezení Mechanismus používaný v SICStus Prologu Vestavěný predikát fd_global(+C,+S,+V) sešle omezení C s iniciálním stavem S fd_global(my_constr(A,B),Term,[min(A)]) V říká, kdy se má omezení probudit dom(X) při libovolné změně domény proměnné X min(X)/max(X) při změně minima/maxima proměnné X minmax(X) při změně minima nebo maxima proměnné X val(X) v případě, že proměnná je instanciována na konkrétní hodnotu Hana Rudová, Omezující podmínky, 20. prosince 2006 92 Propagace pro nebinární omezení Implementace vlastních omezení Mechanismus používaný v SICStus Prologu Vestavěný predikát fd_global(+C,+S,+V) sešle omezení C s iniciálním stavem S fd_global(my_constr(A,B),Term,[min(A)]) V říká, kdy se má omezení probudit dom(X) při libovolné změně domény proměnné X min(X)/max(X) při změně minima/maxima proměnné X minmax(X) při změně minima nebo maxima proměnné X val(X) v případě, že proměnná je instanciována na konkrétní hodnotu Uživatel definuje: clpfd:dispatch_global(+C,+S0,-S,-A) vyvoláno při propagaci omezení C se stavem S0 výsledkem je nový stav S (pomocí stavů lze předat informace z minulého volání dispatch_global, např. jaká byla doména některé proměnné v posledním volání) seznam A požadavků na řešič např. X in NewMinX..NewMaxX, X=V, call(Goal), fail, exit implementace nesmí obsahovat rekurzivní volání řešice, tj. omezení (k tomu je určeno A) Hana Rudová, Omezující podmínky, 20. prosince 2006 92 Propagace pro nebinární omezení Směrová konzistence Opakování: řešení bez navracení CSP vyřešíme bez navracení vzhledem k uspořádání proměnných (x1, . . . , xn), jestliže pro každé i n může být každé častečné řešení (x1, . . . , xi) konzistentně rozšířeno o proměnnou xi+1. Hana Rudová, Omezující podmínky, 20. prosince 2006 94 Směrová konzistence Směrová hranová konzistence (pro binární CSP) green white black red white black red blue white white blue black x1 x2 x3 x4 = = = CSP je směrově hranově konzistentní vzhledem k uspořádání proměnných (x1, . . . , xn), právě když je každá hrana (xj, xi) hranově konzistentní pro každé j i. procedure DAC(G,(x1, . . . , xn)) Directed arc consistency DAC for i = n to 1 by -1 do for j < i takové, že existuje hrana (xj, xi) do revise ((j, i))) end DAC Hana Rudová, Omezující podmínky, 20. prosince 2006 95 Směrová konzistence Směrová hranová konzistence (pro binární CSP) green white black red white black red blue white white blue black x1 x2 x3 x4 = = = CSP je směrově hranově konzistentní vzhledem k uspořádání proměnných (x1, . . . , xn), právě když je každá hrana (xj, xi) hranově konzistentní pro každé j i. procedure DAC(G,(x1, . . . , xn)) Directed arc consistency DAC for i = n to 1 by -1 do for j < i takové, že existuje hrana (xj, xi) do revise ((j, i))) end DAC Příklad: x1 = x2, x1 = x3, x3 = x4 D1={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} Po DAC: D1= {white}, D2={green,white,black}, D3={white,blue}, D4={white,blue,black} není AC, ale máme řešení bez navracení vzhledem k (x1, x2, x3, x4) Hana Rudová, Omezující podmínky, 20. prosince 2006 95 Směrová konzistence Směrová hranová konzistence (pro binární CSP) green white black red white black red blue white white blue black x1 x2 x3 x4 = = = CSP je směrově hranově konzistentní vzhledem k uspořádání proměnných (x1, . . . , xn), právě když je každá hrana (xj, xi) hranově konzistentní pro každé j i. procedure DAC(G,(x1, . . . , xn)) Directed arc consistency DAC for i = n to 1 by -1 do for j < i takové, že existuje hrana (xj, xi) do revise ((j, i))) end DAC Příklad: x1 = x2, x1 = x3, x3 = x4 D1={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} Po DAC: D1= {white}, D2={green,white,black}, D3={white,blue}, D4={white,blue,black} není AC, ale máme řešení bez navracení vzhledem k (x1, x2, x3, x4) Opakování revizí není nutné, doména revidované proměnné se v dalších cyklech nemění Složitost O(ek2 ) každá hrana se reviduje jednou se složitostí O(k2 ) Hana Rudová, Omezující podmínky, 20. prosince 2006 95 Směrová konzistence Směrová konzistence po cestě (pro binární CSP) Směrová hranová konzistence pro výpočet řešení bez navracení nestačí příklad: A,B,C {0,1}, A=B, B=C, A=C je AC, tedy i DAC, ale přesto nevíme, že řešení neexistuje CSP je směrově konzistentní po cestě vzhledem k uspořádání proměnných (x1, . . . , xn) právě tehdy, když je každá dvojice {xi, xj} konzistentní po cestě přes xk pro každé k i, j. Hana Rudová, Omezující podmínky, 20. prosince 2006 96 Směrová konzistence Směrová konzistence po cestě (pro binární CSP) Směrová hranová konzistence pro výpočet řešení bez navracení nestačí příklad: A,B,C {0,1}, A=B, B=C, A=C je AC, tedy i DAC, ale přesto nevíme, že řešení neexistuje CSP je směrově konzistentní po cestě vzhledem k uspořádání proměnných (x1, . . . , xn) právě tehdy, když je každá dvojice {xi, xj} konzistentní po cestě přes xk pro každé k i, j. = = = = = = = = x1 x2 x3 x4 x1 x2 x3 x4 = D={red,blue} Directed path consistency DPC Příklad: problém barvení grafu dvěma barvami první graf je AC ale není PC povoluje přiřazení x3 = red, x1 = blue Hana Rudová, Omezující podmínky, 20. prosince 2006 96 Směrová konzistence Směrová konzistence po cestě (pro binární CSP) Směrová hranová konzistence pro výpočet řešení bez navracení nestačí příklad: A,B,C {0,1}, A=B, B=C, A=C je AC, tedy i DAC, ale přesto nevíme, že řešení neexistuje CSP je směrově konzistentní po cestě vzhledem k uspořádání proměnných (x1, . . . , xn) právě tehdy, když je každá dvojice {xi, xj} konzistentní po cestě přes xk pro každé k i, j. = = = = = = = = x1 x2 x3 x4 x1 x2 x3 x4 = D={red,blue} Directed path consistency DPC Příklad: problém barvení grafu dvěma barvami první graf je AC ale není PC povoluje přiřazení x3 = red, x1 = blue PC vynucuje přidání dvou omezení: C13 : x1 = x3 a C24 : x2 = x4 DPC vzhledem k (x1, x2, x3, x4) vynucuje přidání jen C13 : x1 = x3 (řešení bez navracení) Hana Rudová, Omezující podmínky, 20. prosince 2006 96 Směrová konzistence Algoritmus pro DPC = = = = x1 x2 x3 x4D={red,blue} Algoritmus zajišt'ující DPC i DAC zároveň procedure DPC((V,E),(x1, . . . , xn)) E' := E for k = n to 1 by -1 do for i k takové, že existuje hrana (xi, xk) do revise ((i, k))) for i, j k takové, že (xi, xk),(xj, xk) E' revise-3((i, j), k)) E' := E' (xi, xj) return (V,E') Hana Rudová, Omezující podmínky, 20. prosince 2006 97 Směrová konzistence Algoritmus pro DPC = = = = x1 x2 x3 x4D={red,blue} Algoritmus zajišt'ující DPC i DAC zároveň procedure DPC((V,E),(x1, . . . , xn)) E' := E for k = n to 1 by -1 do for i k takové, že existuje hrana (xi, xk) do revise ((i, k))) for i, j k takové, že (xi, xk),(xj, xk) E' revise-3((i, j), k)) E' := E' (xi, xj) return (V,E') Přidání nových hran znamená přidání nových podmínek Nový rys: algoritmus explicitně odkazuje na nově konstruovaný graf Hana Rudová, Omezující podmínky, 20. prosince 2006 97 Směrová konzistence Chování a složitost algoritmu DPC Počítá algoritmus DPC? nutno ověřit, že každý (xi, xj) je konzistentní po cestě vhledem k xk pro i j k (relace pro j i je symetrická relaci pro i j) při procházení xk zpracujeme (xi, xj) tak, že je konzistentní po cestě přes xk tato konzistence může být později porušena pouze pokud doména xk je změněna, ale to už nebude Cik nebo Cjk jsou změněny, ale to už nebudou, protože mohou být změněny pouze při procházení proměnných, které jsou v uspořádání později než xk, ale ty už byly procházeny před xk Hana Rudová, Omezující podmínky, 20. prosince 2006 98 Směrová konzistence Chování a složitost algoritmu DPC Počítá algoritmus DPC? nutno ověřit, že každý (xi, xj) je konzistentní po cestě vhledem k xk pro i j k (relace pro j i je symetrická relaci pro i j) při procházení xk zpracujeme (xi, xj) tak, že je konzistentní po cestě přes xk tato konzistence může být později porušena pouze pokud doména xk je změněna, ale to už nebude Cik nebo Cjk jsou změněny, ale to už nebudou, protože mohou být změněny pouze při procházení proměnných, které jsou v uspořádání později než xk, ale ty už byly procházeny před xk Složitost O(n3 k3 ) cyklus O(n) revise-3 O(k3 ) O(n2 ) u (xi, xk),(xj, xk) máme nejvýše O(n) hran (xi, xk) a nejvýše O(n) hran (xj, xk) Hana Rudová, Omezující podmínky, 20. prosince 2006 98 Směrová konzistence Vlastnosti DPC Víme: z PC plyne DPC, z DPC plyne DAC Z DPC ale neplyne AC! DPC graf AC i PC graf x1E backtracking vyzkouší všechny možnosti pro B,C,D než odhalí A=1 hned po prvním neúspěšném přiřazení E se lze vrátit k přiřazování A Hana Rudová, Omezující podmínky, 20. prosince 2006 121 Prohledávání a pohled dopředu Problémy a vylepšení backtrackingu Thrashing: opakované objevování stejných nekonzistencí a částečných úspěchů při prohledávání Algoritmy pohledu dopředu kontrolují podmínky dopředu 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 E 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=1 hned po prvním neúspěšném přiřazení E se lze vrátit k přiřazování A Algoritmy učení přidávají nová omezení po nalezení slepé větve příklad: A,B,C,D,E in 1..10, B+89) Hana Rudová, Omezující podmínky, 20. prosince 2006 121 Prohledávání a pohled dopředu Problémy a vylepšení backtrackingu Thrashing: opakované objevování stejných nekonzistencí a částečných úspěchů při prohledávání Algoritmy pohledu dopředu kontrolují podmínky dopředu 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 E 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=1 hned po prvním neúspěšném přiřazení E se lze vrátit k přiřazování A Algoritmy učení přidávají nová omezení po nalezení slepé větve příklad: A,B,C,D,E in 1..10, B+89) Neúplná prohledávání: hledání pouze v některých částech stavového prostoru Hana Rudová, Omezující podmínky, 20. prosince 2006 121 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í Hana Rudová, Omezující podmínky, 20. prosince 2006 122 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 většinou lepší přiřadit proměnné, které nejvíce omezují zbytek stavového prostoru příklad: A,B,C,D,E in 1..10, D=A*B*C*E, E>5, lépe je začít s E Hana Rudová, Omezující podmínky, 20. prosince 2006 122 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 většinou lepší přiřadit proměnné, které nejvíce omezují zbytek stavového prostoru příklad: A,B,C,D,E in 1..10, D=A*B*C*E, E>5, lépe je začít s E rozhodnout, kterou hodnotu přiřadit proměnné snaha o výběr hodnoty, která umožní nejvíce voleb v budoucích přiřazeních příklad: A,B,C in 1..10, A*B<10, B=C*2, pro A je lepší vybrat 1 Hana Rudová, Omezující podmínky, 20. prosince 2006 122 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 většinou lepší přiřadit proměnné, které nejvíce omezují zbytek stavového prostoru příklad: A,B,C,D,E in 1..10, D=A*B*C*E, E>5, lépe je začít s E rozhodnout, kterou hodnotu přiřadit proměnné snaha o výběr hodnoty, která umožní nejvíce voleb v budoucích přiřazeních 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, 20. prosince 2006 122 Prohledávání a pohled dopředu Pohled dopředu pro výběr hodnoty procedure Look-Ahead((X, D, C)) rozdíly od backtrackingu i := 1 (inicializace čítače proměnných) Di := Di pro 1 i n (kopírování domény) while 1 i n přiřazení xi := Select-Value-XXX if xi is null (žádná hodnota nebyla vrácena) i := i - 1 (zpětná fáze) nastav všechny Dk, k > i na jejich hodnotu před poslední instanciací xi else i := i + 1 (dopředná fáze) if i = 0 return ,,nekonzistentní'' else return přiřazené hodnoty {x1, . . . , xn} end Look-Ahead Select-Value-XXX se liší dle typu LA algoritmu Ukládáno n kopií každé D pro každou úroveň ve stavovém prostoru jedna kopie Hana Rudová, Omezující podmínky, 20. prosince 2006 123 Prohledávání a pohled dopředu Kontrola dopředu (forward checking) FC procedure Select-Value-Forward-Checking while Di is not empty vyber a smaž libovolný a Di for k, i k n for b Dk if not Consistent(ai-1, xi = a, xk = b) smaž b z Dk Hana Rudová, Omezující podmínky, 20. prosince 2006 124 Prohledávání a pohled dopředu Kontrola dopředu (forward checking) FC procedure Select-Value-Forward-Checking while Di is not empty vyber a smaž libovolný a Di for k, i k n for b Dk if not Consistent(ai-1, xi = a, xk = b) smaž b z Dk if Dk is empty (xi = a vede do slepé větve, nevybírej a) nastav všechny Dk, i < k n na hodnotu před výběrem a else return a return null Hana Rudová, Omezující podmínky, 20. prosince 2006 124 Prohledávání a pohled dopředu Kontrola dopředu (forward checking) FC procedure Select-Value-Forward-Checking while Di is not empty vyber a smaž libovolný a Di for k, i k n for b Dk if not Consistent(ai-1, xi = a, xk = b) smaž b z Dk if Dk is empty (xi = a vede do slepé větve, nevybírej a) nastav všechny Dk, i < k n na hodnotu před výběrem a else return a return null FC je rozšíření backtrackingu FC navíc zajišt'uje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami Hrany z aktuální proměnné do minulých proměnných není nutno testovat Hana Rudová, Omezující podmínky, 20. prosince 2006 124 Prohledávání a pohled dopředu Příklad: kontrola dopředu Omezení: V1, V2, V3 in 1 . . . 3, V1# = 3 × V3 Stavový prostor: 1 2 3 V3 V1 V2 1 11 1 2 3 Hana Rudová, Omezující podmínky, 20. prosince 2006 125 Prohledávání a pohled dopředu Opravdový úplný pohled dopředu (RFLA) procedure Select-Value-Look-Ahead Real Full Look-Ahead while Di is not empty vyber a smaž libovolný a Di repeat Deleted := false Implementace AC-1 algoritmu for j, i < j n Lze nahradit silnějšími AC algoritmy for k, k = j, i < k n for b Dj if neexistuje c Dk taková, že Consistent(ai-1, xi = a, xj = b, xk = c) smaž b z Dj Deleted := true until Deleted = false Hana Rudová, Omezující podmínky, 20. prosince 2006 126 Prohledávání a pohled dopředu Opravdový úplný pohled dopředu (RFLA) procedure Select-Value-Look-Ahead Real Full Look-Ahead while Di is not empty vyber a smaž libovolný a Di repeat Deleted := false Implementace AC-1 algoritmu for j, i < j n Lze nahradit silnějšími AC algoritmy for k, k = j, i < k n for b Dj if neexistuje c Dk taková, že Consistent(ai-1, xi = a, xj = b, xk = c) smaž b z Dj Deleted := true until Deleted = false if k, i < k n takové, že Dk = (nevybírej a) nastav všechny Dj, i < j n na hodnotu před výběrem a else return a return null Hana Rudová, Omezující podmínky, 20. prosince 2006 126 Prohledávání a pohled dopředu Příklad: pohled dopředu Omezení: V1, V2, V3 in 1 . . . 4, V1# > V2, V2# = 3 × V3 Stavový prostor: V3 V1 V2 1 2 3 4 3 1 Hana Rudová, Omezující podmínky, 20. prosince 2006 127 Prohledávání a pohled dopředu Shrnutí: pohledu dopředu pro výběr hodnoty Kontrola dopředu (forward checking) FC FC zajišt'uje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami Opravdový úplný pohled dopředu (real full look-ahead) RFLA často se odkazuje jako LA algoritmus, tj. RFLA=LA LA je rozšíření FC, LA zajišt'uje hranovou konzistenci LA navíc ověřuje i konzistenci všech hran mezi budoucími proměnnými Hana Rudová, Omezující podmínky, 20. prosince 2006 128 Prohledávání a pohled dopředu Shrnutí: pohledu dopředu pro výběr hodnoty Kontrola dopředu (forward checking) FC FC zajišt'uje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami Opravdový úplný pohled dopředu (real full look-ahead) RFLA často se odkazuje jako LA algoritmus, tj. RFLA=LA LA je rozšíření FC, LA zajišt'uje hranovou konzistenci LA navíc ověřuje i konzistenci všech hran mezi budoucími proměnnými Úplný pohled dopředu (full look-ahead) FLA pouze jeden průchod repeat until cyklem algoritmu Hana Rudová, Omezující podmínky, 20. prosince 2006 128 Prohledávání a pohled dopředu Shrnutí: pohledu dopředu pro výběr hodnoty Kontrola dopředu (forward checking) FC FC zajišt'uje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami Opravdový úplný pohled dopředu (real full look-ahead) RFLA často se odkazuje jako LA algoritmus, tj. RFLA=LA LA je rozšíření FC, LA zajišt'uje hranovou konzistenci LA navíc ověřuje i konzistenci všech hran mezi budoucími proměnnými Úplný pohled dopředu (full look-ahead) FLA pouze jeden průchod repeat until cyklem algoritmu Částečný pohled dopředu (partial look-ahead) PLA pouze jeden průchod repeat until cyklem algoritmu nahrazuje for k, k = j, i < k n výrazem for k, j < k n tj. budoucí proměnné porovnávány pouze s těmi, které je následují (DAC) Hana Rudová, Omezující podmínky, 20. prosince 2006 128 Prohledávání a pohled dopředu Srovnání algoritmů prirazene (minule) neprirazene (budouci) 7 6 1 2 3 5 promenne a aktualni4 n BT +LA +FC Backtracking (BT) kontroluje v kroku a podmínky c(V1, Va), . . . , c(Va-1, Va) z minulých proměnných do aktuální proměnné Hana Rudová, Omezující podmínky, 20. prosince 2006 129 Prohledávání a pohled dopředu Srovnání algoritmů prirazene (minule) neprirazene (budouci) 7 6 1 2 3 5 promenne a aktualni4 n BT +LA +FC Backtracking (BT) kontroluje v kroku a podmínky c(V1, Va), . . . , c(Va-1, Va) z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky c(Va, Va+1), . . . , c(Va, Vn) z aktuální proměnné do budoucích proměnných Hana Rudová, Omezující podmínky, 20. prosince 2006 129 Prohledávání a pohled dopředu Srovnání algoritmů prirazene (minule) neprirazene (budouci) 7 6 1 2 3 5 promenne a aktualni4 n BT +LA +FC Backtracking (BT) kontroluje v kroku a podmínky c(V1, Va), . . . , c(Va-1, Va) z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky c(Va, Va+1), . . . , c(Va, Vn) z aktuální proměnné do budoucích proměnných Pohled dopředu (LA) kontroluje v kroku a podmínky l(a l n), k(a k n), k = l : c(Vk, Vl) z aktuální proměnné do budoucích proměnných a mezi budoucími proměnnými Hana Rudová, Omezující podmínky, 20. prosince 2006 129 Prohledávání a pohled dopředu Pohled dopředu pro dynamický výběr hodnoty Výběr hodnoty v doméně proměnné zatím jsme vybírali první konzistentní hodnotu místo toho zkusíme proměnné přiřadit každou z hodnot v doméně a vyzkoušíme efekt použití FC nebo jiného LA algoritmu Hana Rudová, Omezující podmínky, 20. prosince 2006 130 Prohledávání a pohled dopředu Pohled dopředu pro dynamický výběr hodnoty Výběr hodnoty v doméně proměnné zatím jsme vybírali první konzistentní hodnotu místo toho zkusíme proměnné přiřadit každou z hodnot v doméně a vyzkoušíme efekt použití FC nebo jiného LA algoritmu Minimální konflikt výběr hodnoty, která smaže nejmenší počet hodnot z domén budoucích proměnných experimentálně: tato heuristika vykazuje velmi dobré výsledky Hana Rudová, Omezující podmínky, 20. prosince 2006 130 Prohledávání a pohled dopředu Pohled dopředu pro dynamický výběr hodnoty Výběr hodnoty v doméně proměnné zatím jsme vybírali první konzistentní hodnotu místo toho zkusíme proměnné přiřadit každou z hodnot v doméně a vyzkoušíme efekt použití FC nebo jiného LA algoritmu Minimální konflikt výběr hodnoty, která smaže nejmenší počet hodnot z domén budoucích proměnných experimentálně: tato heuristika vykazuje velmi dobré výsledky Maximální velikost domény výběr hodnoty, která způsobí vytvoření největší minimální velikost domény mezi všemi budoucími proměnnými intuice: proměnné, které mají malé domény, způsobí pravděpodobněji nekonzistenci Hana Rudová, Omezující podmínky, 20. prosince 2006 130 Prohledávání a pohled dopředu Výběr proměnné Uspořádání proměnných má velký vliv na velikost stavového prostoru statické uspořádání proměnných triviálně: výběr nejlevější proměnné (tj. proměnné s nejmenším indexem) empirické i teoretické studie ukázaly, že některá statická uspořádání vedou obecně ke zmenšení velikost stavového prostoru dynamické uspořádání proměnných lze využít (výpočtů) algoritmů pohledu dopředu Hana Rudová, Omezující podmínky, 20. prosince 2006 131 Prohledávání a pohled dopředu Výběr proměnné II. Obecný princip výběru proměnné: first-fail ­ dynamické výběr proměnné, která nejvíce omezí zbytek stavového prostoru výbereme proměnnou s nejmenší doménou později už by mohlo být těžší pro tuto proměnnou nalézt správnou hodnotu ?- domain([A,B,C],1,3), A#<3, A#=B+C. Hana Rudová, Omezující podmínky, 20. prosince 2006 132 Prohledávání a pohled dopředu Výběr proměnné II. Obecný princip výběru proměnné: first-fail ­ dynamické výběr proměnné, která nejvíce omezí zbytek stavového prostoru výbereme proměnnou s nejmenší doménou později už by mohlo být těžší pro tuto proměnnou nalézt správnou hodnotu ?- domain([A,B,C],1,3), A#<3, A#=B+C. nejlépe je začít s výběrem A Hana Rudová, Omezující podmínky, 20. prosince 2006 132 Prohledávání a pohled dopředu Výběr proměnné II. Obecný princip výběru proměnné: first-fail ­ dynamické výběr proměnné, která nejvíce omezí zbytek stavového prostoru výbereme proměnnou s nejmenší doménou později už by mohlo být těžší pro tuto proměnnou nalézt správnou hodnotu ?- domain([A,B,C],1,3), A#<3, A#=B+C. nejlépe je začít s výběrem A Minimální šířka ­ statické proměnné uspořádány tak, aby byla minimalizována šířka grafu (minimalizován počet zpětných hran) odzadu vybíráme proměnné s nejmenším počtem hran v aktualizovaném grafu (algoritmus viz dříve) Hana Rudová, Omezující podmínky, 20. prosince 2006 132 Prohledávání a pohled dopředu Výběr proměnné II. Obecný princip výběru proměnné: first-fail ­ dynamické výběr proměnné, která nejvíce omezí zbytek stavového prostoru výbereme proměnnou s nejmenší doménou později už by mohlo být těžší pro tuto proměnnou nalézt správnou hodnotu ?- domain([A,B,C],1,3), A#<3, A#=B+C. nejlépe je začít s výběrem A Minimální šířka ­ statické proměnné uspořádány tak, aby byla minimalizována šířka grafu (minimalizován počet zpětných hran) odzadu vybíráme proměnné s nejmenším počtem hran v aktualizovaném grafu (algoritmus viz dříve) Maximální kardinalita ­ statické první proměnnou (uzel grafu) vybereme náhodně každý uzel je spojen s maximálním počtem už uspořádaných vrcholů Hana Rudová, Omezující podmínky, 20. prosince 2006 132 Prohledávání a pohled dopředu Pohled dopředu pro dynamický výběr proměnné procedure Var-Ord-Look-Ahead((X, D, C)) rozdíly od Look-Ahead i := 1 (inicializace čítače proměnných) Di := Di pro 1 i n (kopírování domény) s := min1 j n Dj (nalezni proměnnou s nejmenší doménou) x1 := xs (přeskládej proměnné tak, aby xs byla první) while 1 i n přiřazení xi := Select-Value-XXX if xi is null (žádná hodnota nebyla vrácena) i := i - 1 (zpětná fáze) nastav všechny Dk, k > i na jejich hodnotu před poslední instanciací xi else if i < n s :=mini latesti latesti := k if not Consistent(ak, xi = a) consistent := false else k := k+1 if consistent return a return null (v doméně xi neexistuje konzistentní hodnota) Hana Rudová, Omezující podmínky, 20. prosince 2006 144 Pohled zpět při prohledávání GBJ: příklad x7 = red vyřadí x1 (tj. latest7 = 1), x7 = blue 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 x3=red dala latest3 na 1, x3=blue dala latest3 na 2 lépe (až k x1) se ale vrátit neumíme, GBJ se v tomto okamžiku vrací k předchozí proměnné Hana Rudová, Omezující podmínky, 20. prosince 2006 145 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í. aj-1 se pak nazývá vnitřní slepá větev. Hana Rudová, Omezující podmínky, 20. prosince 2006 146 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í. aj-1 se pak nazývá vnitřní slepá větev. CBJ skáče zpět v listu slepé větve i ve vnitřní slepé větvi 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 < i), jestliže j > i, 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. uspořádání (x1, x2, . . .) rozsah R1 je (x3, x5, x7), rozsah S1 je (x2, x6, x8, x9) R1 je vzdálenější než S1 Hana Rudová, Omezující podmínky, 20. prosince 2006 146 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í. aj-1 se pak nazývá vnitřní slepá větev. CBJ skáče zpět v listu slepé větve i ve vnitřní slepé větvi 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 < i), jestliže j > i, 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. uspořádání (x1, x2, . . .) rozsah R1 je (x3, x5, x7), rozsah S1 je (x2, x6, x8, x9) R1 je vzdálenější než S1 rozsah R2 je (x3, x5, x8, x9), rozsah S2 je (x2, x6, x8, x9) R2 je vzdálenější než S2 Hana Rudová, Omezující podmínky, 20. prosince 2006 146 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í. aj-1 se pak nazývá vnitřní slepá větev. CBJ skáče zpět v listu slepé větve i ve vnitřní slepé větvi 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 < i), jestliže j > i, 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. uspořádání (x1, x2, . . .) rozsah R1 je (x3, x5, x7), rozsah S1 je (x2, x6, x8, x9) R1 je vzdálenější než S1 rozsah R2 je (x3, x5, x8, x9), rozsah S2 je (x2, x6, x8, x9) R2 je vzdálenější než S2 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, 20. prosince 2006 146 Pohled zpět při prohledávání CBJ: výběr hodnoty procedure Select-Value-CBJ while Di is not empty vyber a smaž libovolný a Di consistent := true k := 1 while k < i consistent if Consistent(ak, xi = a) k := k+1 else R := nejvzdálenější nesplněné omezení přidej proměnné v rozsahu R vyjma xi do Ji consistent := false if consistent return a return null (v doméně xi neexistuje konzistentní hodnota) Hana Rudová, Omezující podmínky, 20. prosince 2006 147 Pohled zpět při prohledávání Algoritmus CBJ procedure CBJ((X, D, C)) rozdíly od backtrackingu i := 1 (inicializace čítače proměnných) Di := Di (kopírování domény) Ji := (inicializace množiny skoků zpět) while 1 i n přiřazení xi := Select-Value-CBJ if xi is null (žádná hodnota nebyla vrácena) ip := i i := index poslední proměnné v Ji (skok zpět) Ji := Ji Jip - {xi} (spoj množiny skoku zpět) (takto upravená Ji se použije ve vnitřní slepé větvi) else i := i + 1 (dopředná fáze) Di := Di Ji := if i = 0 return ,,nekonzistentní'' else return přiřazené hodnoty {x1, . . . , xn} end CBJ j k 00001111 00001111 00001111 00001111 ip Jip i Hana Rudová, Omezující podmínky, 20. prosince 2006 148 Pohled zpět při prohledávání CBJ: příklad x x2 x7 x3 x5 x4 x red blue,green red,blue,green red,blue blue,green red,blue 1 red,green,teal 3 před vstupem do Select-Value-CBJ pro proměnnou x7 je J7 = x3 = x7 je nejvzdálenější omezení, které vyřadilo x7 =red, tedy J7 = {x3} x1 = x7 je nejvzdálenější omezení, které vyřadilo x7 =blue, tedy J7 = {x1, x3} skáčeme zpět na poslední proměnnou v J7, tedy na x3 do J3, která byla zatím prázdná, přidáme x1 doména x3 je prázdná, v J3 je jediná proměnná x1 a na tu se vracíme Hana Rudová, Omezující podmínky, 20. prosince 2006 149 Pohled zpět při prohledávání Algoritmy učení Množiny skoků zpět jsou chybná přiřazení vypočítaná během prohledávání Tato chybná přiřazení 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 nemá cenu uchovávat celou slepou větev ai v proměnné xi+1 na toto přiřazení už později nenarazíme uchováme chybná přiřazení na podmnožině proměnných {x1, . . . , xi} Prořezávání stavového prostoru čím menší chybná přiřazení se podaří uchovat, tím rychlejší bude prohledávání Zvětšování množiny omezení cena za prořezávání stavového prostoru nesmí přerůst cenu za zvětšování množiny omezení Hana Rudová, Omezující podmínky, 20. prosince 2006 150 Pohled zpět při prohledávání Učení skoku zpět (jumpback learning) 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 ai-1 přidáme omezení zakazující ai-1[Ji] projekce na Ji Hana Rudová, Omezující podmínky, 20. prosince 2006 151 Pohled zpět při prohledávání Učení skoku zpět (jumpback learning) 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 ai-1 přidáme omezení zakazující ai-1[Ji] projekce na Ji po dosažení listu slepé větve v x6 je J6 = {x3, x4, x5} red vyřadila x6 = x5, blue vyřadila x6 = x3, green vyřadila x6 = x4 Hana Rudová, Omezující podmínky, 20. prosince 2006 151 Pohled zpět při prohledávání Učení skoku zpět (jumpback learning) 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 ai-1 přidáme omezení zakazující ai-1[Ji] projekce na Ji po dosažení listu slepé větve v x6 je J6 = {x3, x4, x5} red vyřadila x6 = x5, blue vyřadila x6 = x3, green vyřadila x6 = x4 a5[J6] tedy zakazuje přiřazení [ x3,blue , x4,green , x5,red ] později při procházení stromu lze např. ze znalosti x3 =blue, x4 =green odvodit x5 =blue Hana Rudová, Omezující podmínky, 20. prosince 2006 151 Pohled zpět při prohledávání Další algoritmy systematického prohledávání Redundance backtrackingu Redundantní práce: opakování výpočtu, jehož výsledek už máme k dispozici B A D C=10 D=1 D=10 C=1 D C=10 D=1 D=10 C=1 D C=10 D=1 D=10 C=1 C D C=10 D=1 D=10 C=1 C D C=10C=1 D=1 D=10 C C C A=1 B=4B=1 B=2 B=3 B=5 A,B,C,D in 1..10, A+8 do vyber X z Unlabelled ValuesX := DX - hodnoty nekonzistentní s Labelled použitím Constraints Hana Rudová, Omezující podmínky, 20. prosince 2006 160 Systematické prohledávní Dynamický backtracking: algoritmus procedure DB(Variables, Constraints) Labelled := ; Unlabelled := Variables while Unlabelled <> do vyber X z Unlabelled ValuesX := DX - hodnoty nekonzistentní s Labelled použitím Constraints if ValuesX = then necht' E je vysvětlení konfliktu (množina konfliktních proměnných) if E = then failure else necht' 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í Y Hana Rudová, Omezující podmínky, 20. prosince 2006 160 Systematické prohledávní Dynamický backtracking: algoritmus procedure DB(Variables, Constraints) Labelled := ; Unlabelled := Variables while Unlabelled <> do vyber X z Unlabelled ValuesX := DX - hodnoty nekonzistentní s Labelled použitím Constraints if ValuesX = then necht' E je vysvětlení konfliktu (množina konfliktních proměnných) if E = then failure else necht' 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í Y else vyber V z ValuesX Unlabelled := Unlabelled - X Labelled := Labelled X/V return Labelled Hana Rudová, Omezující podmínky, 20. prosince 2006 160 Systematické prohledávní Dynamický backtracking: algoritmus procedure DB(Variables, Constraints) Labelled := ; Unlabelled := Variables while Unlabelled <> do vyber X z Unlabelled ValuesX := DX - hodnoty nekonzistentní s Labelled použitím Constraints if ValuesX = then necht' E je vysvětlení konfliktu (množina konfliktních proměnných) if E = then failure else necht' 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í Y else vyber V z ValuesX Unlabelled := Unlabelled - X Labelled := Labelled 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, 20. prosince 2006 160 Systematické prohledávní Neúplná stromová prohledávání Prohledávání do hloubky Depth first search (DFS) 1 2 3 4 567 Hana Rudová, Omezující podmínky, 20. prosince 2006 162 Neúplná stromová prohledávání Prohledávání do hloubky Depth first search (DFS) 1 2 3 4 567 Reálné problémy mají často tak velké prostory možných ohodnocení, že není možné je celé prohledat. Je možné prohledat jen omezený prostor Neúplná stromová prohledávání Hana Rudová, Omezující podmínky, 20. prosince 2006 162 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 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í rychleji Hana Rudová, Omezující podmínky, 20. prosince 2006 163 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 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í rychleji Neúplné algoritmy často odvozeny od algoritmu úplného (DFS) 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 prostředek může být globální (pro celý strom) i lokální (pro daný podstrom nebo uzel) opakovaní běhu algoritmu (restart) běh předešlého neúplného prohledávání opakujeme s jiným nastavením parametrů při opakování běhu lze využívat algoritmy učení Hana Rudová, Omezující podmínky, 20. prosince 2006 163 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í) 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 nich Hana Rudová, Omezující podmínky, 20. prosince 2006 164 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í) 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 nich Randomizovaný backtracking s učením 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, 20. prosince 2006 164 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 ,,omezený počet navštívených listů" Při neúspěchu zvětšíme počet návratů o jedna (opakování) Příklad: BBS(6) 6 2 4 31 5 Hana Rudová, Omezující podmínky, 20. prosince 2006 165 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 ,,omezený počet navštívených listů" Při neúspěchu zvětšíme počet návratů o jedna (opakování) Příklad: BBS(6) 6 2 4 31 5 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, 20. prosince 2006 165 Neúplná stromová prohledávání Omezení hloubky Depth-bounded search (DBS) Omezíme hloubku prohledávaného stromu (přerušení) do dané hloubky stromu se zkouší všechny alternativy ve zbytku stromu se může použít jiná neúplná metoda Při neúspěchu zvětšíme hloubku prohledávání o jedna (opakování) Příklad: DBS(1,BBS(0)) Hana Rudová, Omezující podmínky, 20. prosince 2006 166 Neúplná stromová prohledávání Omezení hloubky Depth-bounded search (DBS) Omezíme hloubku prohledávaného stromu (přerušení) do dané hloubky stromu se zkouší všechny alternativy ve zbytku stromu se může použít jiná neúplná metoda Při neúspěchu zvětšíme hloubku prohledávání o jedna (opakování) Příklad: DBS(1,BBS(0)) Implementace udržujeme pořadové číslo přiřazované proměnné je-li pořadové číslo větší než daná mez, zkouší se pouze jedna alterantiva ­ BBS(0) Hana Rudová, Omezující podmínky, 20. prosince 2006 166 Neúplná stromová prohledávání Prohledávání s kreditem Credit search (CS) Omezený kredit (počet návratů) pro prohledávání (přerušení) kredit se rovnoměrně dělí mezi alternativní větve prohleldávání jednotkový kredit zakazuje možnost volby (hodnoty) Při neúspěchu navýšíme kredit o jedna (opakování) Příklad: CS(12) 2 1 1 1 12 1 1 1 1 6 6 1 1 1 1 1 11 1 1 1 1 1 Hana Rudová, Omezující podmínky, 20. prosince 2006 167 Neúplná stromová prohledávání Prohledávání s kreditem Credit search (CS) Omezený kredit (počet návratů) pro prohledávání (přerušení) kredit se rovnoměrně dělí mezi alternativní větve prohleldávání jednotkový kredit zakazuje možnost volby (hodnoty) Při neúspěchu navýšíme kredit o jedna (opakování) Příklad: CS(12) 2 1 1 1 12 1 1 1 1 6 6 1 1 1 1 1 11 1 1 1 1 1 Implementace v každém uzlu se nejednotkový kredit (rovnoměrně) rozdělí mezi alternativní podstromy při jednotkovém kreditu se neberou alternativy Hana Rudová, Omezující podmínky, 20. prosince 2006 167 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 Při neúspěchu zvýšíme povolený počet voleb o jedna (opakování) Příklad: IB(2) Implementace 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, 20. prosince 2006 168 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í doporučují hodnotu pro přiřazení často vedou římo k řešení Co dělat, když heuristika neuspěje? 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ře Hana Rudová, Omezující podmínky, 20. prosince 2006 169 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í doporučují hodnotu pro přiřazení často vedou římo k řešení Co dělat, když heuristika neuspěje? 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ře Pozorování: počet porušení heuristiky na úspěšné cestě je malý 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, 20. prosince 2006 169 Neúplná stromová prohledávání Zotavení se z chyb heuristiky Heuristika doporučuje hodnotu pro přiřazení Diskrepance = porušení heuristiky 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čátky jsou prozkoumány dříve Hana Rudová, Omezující podmínky, 20. prosince 2006 170 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í) 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(1), heuristika doporučuje vydat se levou větví 6 54 3 2 1Diskrepance pro nebinární domény nedoporučené hodnoty se berou jako jedna diskrepance (zde) výběr každé další hodnoty proměnné je jedna diskrepance (tj. třetí hodnota = dvě diskrepance, čtvrtá hodnota = tři diskrepance, . . . ) Hana Rudová, Omezující podmínky, 20. prosince 2006 171 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 fail Hana Rudová, Omezující podmínky, 20. prosince 2006 172 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 fail procedure LDS-PROBE(Unlabelled,Labelled,Constraints,D) if Unlabelled = {} then return Labelled select X Unlabelled ValuesX := DX - {values inconsistent with Labelled using Constraints} if ValuesX = {} then return fail else select HV ValuesX using heuristic if D>0 then for V ValuesX-{HV} do R := LDS-PROBE(Unlabelled-{X}, Labelled {X/V}, Constraints, D-1) if R = fail then return R return LDS-PROBE(Unlabelled-{X}, Labelled {X/HV}, Constraints, D) end LDS-PROBE Hana Rudová, Omezující podmínky, 20. prosince 2006 172 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 search (ILDS) daný počet diskrepancí na cestě (přerušení) cesty s diskrepancemi na konci prozkoumány dříve Při neúspěchu navýšíme počet diskrepancí o jedna (opakování) Příklad: ILDS(1), heuristika doporučuje vydat se levou větví 1 2 3 4 5 Hana Rudová, Omezující podmínky, 20. prosince 2006 173 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 Unlabelled ValuesX := DX - {values inconsistent with Labelled using Constraints} if ValuesX = {} then return fail else select HV ValuesX using heuristic if D<|Unlabelled| then R := ILDS-PROBE(Unlabelled-{X}, Labelled {X/HV}, Constraints, D) if R = fail then return R if D>0 then for V ValuesX-{HV} do R := ILDS-PROBE(Unlabelled-{X}, Labelled {X/V}, Constraints, D-1) if R = fail then return R end ILDS-PROBE Hana Rudová, Omezující podmínky, 20. prosince 2006 174 Neúplná stromová prohledávání Hloubkou omezené diskrepance ILDS bere cesty s diskrepancemi na konci dříve Depth-bounded discrepancy search (DDS) Diskrepance povoleny pouze do dané hloubky (přerušení) v této hloubce je vždy diskrepance, tj. zabrání se procházení větví z předchozí iterace hloubka zároveň omezuje maximální počet diskrepancí cesty s diskrepancemi na konci 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 1 2 3 4 Hana Rudová, Omezující podmínky, 20. prosince 2006 175 Neúplná stromová prohledávání Srovnání prohledavacích algoritmů Srovnání prohledávacích algoritmů A B znamená, že uzly prohledávacího stromu B jsou i v stromě A Hana Rudová, Omezující podmínky, 20. prosince 2006 177 Srovnání prohledávacích algoritmů Srovnání prohledávacích algoritmů A B znamená, že uzly prohledávacího stromu B jsou i v stromě A za předpokladu stejného uspořádání hodnot i proměnných Existuje lepší srovnání? Jaké algoritmy používat pro daný problém? Experimentální porovnání na různých sadách problémů (benchmarks) reálné problémy nahodně vygenerované problémy aplikačně založené náhodné problémy Kriteria CPU čas velikost generovaného prohledávacího stromu počet volání procedury (např. Consistent) Hana Rudová, Omezující podmínky, 20. prosince 2006 177 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 knihovna problémů pro omezující podmínky (otevřená pro nové problémy) 45 problémů z oblasti jako je rozvrhování, návrh a konfigurace, kombinatorika, bioinformatika, hry popis problému, reference na jeho řešení, data, výsledky někdy i řešení nebo podrobné studie různých možností řešení příklady rozvrh pro 1997/98 Atlantic Coast Conference (ACC), basketball, 9 týmů dopravní signalizace v čase na zadaných křižovatkách Problém: výsledky lze stále velice obtížně zobecnit na další problémy pro jeden problém je lepší jeden algoritmus, pro další problém jiný algoritmus Hana Rudová, Omezující podmínky, 20. prosince 2006 178 Srovnání prohledávacích algoritmů Náhodné problémy Algoritmy porovnávány na umělých, náhodně vygenerovaných problémech lze generovat problémy různé obtížnosti (fáze přechodu) libovolný počet datových instancí lze testovat, co se stane (např. s parametry algoritmu) při změnách problému Náhodné binární CSP (random binary CSP) parametry (n, m, p1, p2) n počet proměnných m počet hodnot v doméně proměnných p1 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, 20. prosince 2006 179 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 problémy lze náhodně generovat s různým nastavením parametrů Výhody zaměřené na reálné problémy generování řady problémů umožňuje statistické porovnání Příklad: shop scheduling problémy n úloh, každá úloha se skládá z m operací m strojů, na kterých lze operace provádět operace jedné úlohy nesmí být prováděny zároveň 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, 20. prosince 2006 180 Srovnání prohledávacích algoritmů Fáze přechodu Náhodný k-SAT problém formule pevné délky jsou generovány výběrem m klauzulí každá klauzule délky k je uniformně náhodně generována z množiny všech klauzulí Obtížnost nalezení řešení při malém počtu klauzulí je většina problémů splnitelná a snadno řešitelná při velkém počtu klauzulí je detekována snadno nesplnitelnost většiny problémů nalezení řešení je nejobtížnější za předpokladu, že cca 50 % problémů je splnitelná Hana Rudová, Omezující podmínky, 20. prosince 2006 181 Srovnání prohledávacích algoritmů Fáze přechodu Náhodný k-SAT problém formule pevné délky jsou generovány výběrem m klauzulí každá klauzule délky k je uniformně náhodně generována z množiny všech klauzulí Obtížnost nalezení řešení při malém počtu klauzulí je většina problémů splnitelná a snadno řešitelná při velkém počtu klauzulí je detekována snadno nesplnitelnost většiny problémů nalezení řešení je nejobtížnější za předpokladu, že cca 50 % problémů je splnitelná Fenomén fáze předchodu (phase transition) fáze přechodu z obtížně řešitelných problémů na snadno řešitelné problémů počet volání poměr počtu klauzulí vůči počtu proměných Využití fáze přechodu: lze generovat problémy různé obtížnosti Hana Rudová, Omezující podmínky, 20. prosince 2006 181 Srovnání prohledávacích algoritmů Lokální prohledávání Lokální prohledávání (LS) Princip 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ů LS: milión královen za minutu, nejpropracovanější backtracking: pár set Hana Rudová, Omezující podmínky, 20. prosince 2006 183 Lokální prohledávání Lokální prohledávání (LS) Princip 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ů LS: milión královen za minutu, nejpropracovanější backtracking: pár set Přibližná metoda prohledávání neúplná metoda nezaručuje nalezení (vyloučení existence) řešení i když existuje (neexistuje) malé pamět'ové nároky Hana Rudová, Omezující podmínky, 20. prosince 2006 183 Lokální prohledávání Terminologie lokálního prohledávání Stav : ohodnocení všech proměnných Evaluace E: hodnota objektivní funkce (počet nesplněných podmínek=počet konfliktů) Globální optimum: stav s nejlepší evaluací Hana Rudová, Omezující podmínky, 20. prosince 2006 184 Lokální prohledávání Terminologie lokálního prohledávání Stav : ohodnocení všech proměnných Evaluace E: hodnota objektivní funkce (počet nesplněných podmínek=počet konfliktů) Globální optimum: stav s nejlepší evaluací Lokální změna: změna hodnoty (jedné) proměnné Okolí o: množina stavů lišící se od daného stavu o jednu lokální změnu Lokální optimum: stav, v jehož okolí jsou stavy s horší evaluací; není globálním optimum Hana Rudová, Omezující podmínky, 20. prosince 2006 184 Lokální prohledávání Terminologie lokálního prohledávání Stav : ohodnocení všech proměnných Evaluace E: hodnota objektivní funkce (počet nesplněných podmínek=počet konfliktů) Globální optimum: stav s nejlepší evaluací Lokální změna: změna hodnoty (jedné) proměnné Okolí o: množina stavů lišící se od daného stavu o jednu lokální změnu Lokální optimum: stav, v jehož okolí jsou stavy s horší evaluací; není globálním optimum Striktní lokální optimum: stav, v jehož okolí jsou pouze stavy s horší evaluací; není globálním optimum Ne-striktní lokální optimum: stav, v jehož okolí exisují stavy se stejnou evaluací; není globálním optimum Plateau: množina stavů se stejnou evaluací Hana Rudová, Omezující podmínky, 20. prosince 2006 184 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 := náhodné ohodnocení proměnných for i := 1 to MaxPokusu while GPodminka do for j := 1 to MaxZmen while LPodminka do if E()=0 then return vyber o() if akceptovatelne() then := := novyStav() return nejlepší Hana Rudová, Omezující podmínky, 20. prosince 2006 185 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 := náhodné ohodnocení proměnných for i := 1 to MaxPokusu while GPodminka do for j := 1 to MaxZmen while LPodminka do if E()=0 then return vyber o() if akceptovatelne() then := := novyStav() return nejlepší Jak stanovit MaxPokusu,MaxZmen? pokračovat dokud existuje přiřazení s lepší evaluací restart (MaxPokusu>1) v některých případech diskutabilní Hana Rudová, Omezující podmínky, 20. prosince 2006 185 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 × (d - 1) Útěk ze striktního lokálního minima pomocí restartu procedure HC(MaxZmen) restart: := náhodné ohodnocení proměnných for j := 1 to MaxZmen do if E() = 0 then return if je striktní lokální optimum then goto restart else := stav z o() s nejlepší evaluací goto restart end HC Hana Rudová, Omezující podmínky, 20. prosince 2006 186 Lokální prohledávání Metoda minimalizace konfliktů (MC) Okolí u HC je poměrně velké: n × (d - 1) ale pouze změna konfliktní proměnné může přinést zlepšení 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 procedure MC(MaxZmen) := náhodné ohodnocení proměnných PocetZmen := 0 while E() > 0 PocetZmen 0 PocetZmen 0 PocetZmen 0 PocetZmen @1 = 1 => @0.5 = 2 => @0.1 c3: max(A + B) @(A + B)/10 Hana Rudová, Omezující podmínky, 20. prosince 2006 208 Optimalizace & soft omezení: modely Fuzzy CSP Fuzzy množiny: příslušnost prvku k množině zadána číslem z intervalu [0, 1] Fuzzy omezení: fuzzy relace c(d1, . . . , dk) 0, 1 udává úroveň preference DA = DB = {1, 2, 3} c1: A = 1 @(1,0.7) c2: min( abs(A - B) ), abs(A - B) = 0 => @1 = 1 => @0.5 = 2 => @0.1 c3: max(A + B) @(A + B)/10 Fuzzy CSP (X, D, Cf ) Cf je množina fuzzy omezení X uspořádaná množina proměnných Hana Rudová, Omezující podmínky, 20. prosince 2006 208 Optimalizace & soft omezení: modely Kombinace a projekce omezení Projekce n-tic (d1, . . . , dl) Y X příklad: (1, 2, 3, 4, 5) (A,B,C,D,E) (D,A,E) = (4, 1, 5) Hana Rudová, Omezující podmínky, 20. prosince 2006 209 Optimalizace & soft omezení: modely Kombinace a projekce omezení Projekce n-tic (d1, . . . , dl) Y X příklad: (1, 2, 3, 4, 5) (A,B,C,D,E) (D,A,E) = (4, 1, 5) Kombinace c = cX cY , dom(c) = Z = X Y c, cX, cY omezení nad Z, X, Y c(d1, . . . , dk) = min(cX ((d1, . . . , dk) Z X), cY ((d1, . . . , dk) Z Y )) udává, jaká je úroveň splnění všech přiřazení Z vzhledem k cX a cY příklad kombinace c1 c2 c3 pro (1, 3) c1c2c3(1, 3) = min(c1((1)), c2((1, 3)), c3((1, 3))) = min(1, 0.1, 0.4) = 0.1 Hana Rudová, Omezující podmínky, 20. prosince 2006 209 Optimalizace & soft omezení: modely Kombinace a projekce omezení Projekce n-tic (d1, . . . , dl) Y X příklad: (1, 2, 3, 4, 5) (A,B,C,D,E) (D,A,E) = (4, 1, 5) Kombinace c = cX cY , dom(c) = Z = X Y c, cX, cY omezení nad Z, X, Y c(d1, . . . , dk) = min(cX ((d1, . . . , dk) Z X), cY ((d1, . . . , dk) Z Y )) udává, jaká je úroveň splnění všech přiřazení Z vzhledem k cX a cY příklad kombinace c1 c2 c3 pro (1, 3) c1c2c3(1, 3) = min(c1((1)), c2((1, 3)), c3((1, 3))) = min(1, 0.1, 0.4) = 0.1 Projekce c = cY X, dom(c) = X, X Y c, cX, cY omezení nad X, X, Y c(dx1, . . . , dxk) = max ((dy1,...,dyl)Dy1××Dyl)((dy1,...,dyl)Y X=(dx1,...,dxk)) cY (dy1, . . . , dyl) udává, jaká je úroveň splnění všech přiřazení X vzhledem k cY příklad projekce c3 (B) na (1) c3(B) (1) = max(c3(1, 1), c3(2, 1), c3(3, 1)) = max(0.2, 0.3, 0.4) = 0.4 Hana Rudová, Omezující podmínky, 20. prosince 2006 209 Optimalizace & soft omezení: modely Řešení fuzzy CSP Úroveň splnění přiřazení (d1, . . . , dn) dána jako C(d1, . . . , dn) Hana Rudová, Omezující podmínky, 20. prosince 2006 210 Optimalizace & soft omezení: modely Řešení fuzzy CSP Úroveň splnění přiřazení (d1, . . . , dn) dána jako C(d1, . . . , dn) Řešení ­ přiřazení (d1, . . . , dn) takové, že max (d1,...,dn)D1××Dn C(d1, . . . , dn) = C(P) Hana Rudová, Omezující podmínky, 20. prosince 2006 210 Optimalizace & soft omezení: modely Řešení fuzzy CSP Úroveň splnění přiřazení (d1, . . . , dn) dána jako C(d1, . . . , dn) Řešení ­ přiřazení (d1, . . . , dn) takové, že max (d1,...,dn)D1××Dn C(d1, . . . , dn) = C(P) příklad: C = c1 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 Hana Rudová, Omezující podmínky, 20. prosince 2006 210 Optimalizace & soft omezení: modely Řešení fuzzy CSP Úroveň splnění přiřazení (d1, . . . , dn) dána jako C(d1, . . . , dn) Řešení ­ přiřazení (d1, . . . , dn) takové, že max (d1,...,dn)D1××Dn C(d1, . . . , dn) = C(P) příklad: C = c1 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 (3, 3) je řešení, C(P) = 0.6 Hana Rudová, Omezující podmínky, 20. prosince 2006 210 Optimalizace & soft omezení: modely Řešení fuzzy CSP Úroveň splnění přiřazení (d1, . . . , dn) dána jako C(d1, . . . , dn) Řešení ­ přiřazení (d1, . . . , dn) takové, že max (d1,...,dn)D1××Dn C(d1, . . . , dn) = C(P) příklad: C = c1 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 (3, 3) je řešení, C(P) = 0.6 Úroveň nekonzistence 1 - C(P) C(P) je úroveň konzistence také jako projekce na prázdnou množinu proměnných C Hana Rudová, Omezující podmínky, 20. prosince 2006 210 Optimalizace & soft omezení: modely Příklad: řešení fuzzy CSP Viz dříve: C = c1 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 {A,B} C {A,B} (3, 3) = max( C(3, 3)) = 0.6, C {A,B} (2, 2) = 0.4,. . . Hana Rudová, Omezující podmínky, 20. prosince 2006 211 Optimalizace & soft omezení: modely Příklad: řešení fuzzy CSP Viz dříve: C = c1 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 {A,B} C {A,B} (3, 3) = max( C(3, 3)) = 0.6, C {A,B} (2, 2) = 0.4,. . . C {A} C {A} (1) = max( C(1, 1), C(1, 2), C(1, 3)) = max(0.2, 0.3, 0.1) = 0.3 C {A} (2) = max( C(2, 1), C(2, 2), C(2, 3)) = max(0.3, 0.4, 0.5) = 0.5 C {A} (3) = max( C(3, 1), C(3, 2), C(3, 3)) = max(0.1, 0.5, 0.6) = 0.6 Hana Rudová, Omezující podmínky, 20. prosince 2006 211 Optimalizace & soft omezení: modely Příklad: řešení fuzzy CSP Viz dříve: C = c1 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 {A,B} C {A,B} (3, 3) = max( C(3, 3)) = 0.6, C {A,B} (2, 2) = 0.4,. . . C {A} C {A} (1) = max( C(1, 1), C(1, 2), C(1, 3)) = max(0.2, 0.3, 0.1) = 0.3 C {A} (2) = max( C(2, 1), C(2, 2), C(2, 3)) = max(0.3, 0.4, 0.5) = 0.5 C {A} (3) = max( C(3, 1), C(3, 2), C(3, 3)) = max(0.1, 0.5, 0.6) = 0.6 C C () = max( C(1, 1), C(1, 2), C(1, 3), C(2, 1), C(2, 2), C(2, 3), C(3, 1), C(3, 2), C(3, 3)) = 0.6 Hana Rudová, Omezující podmínky, 20. prosince 2006 211 Optimalizace & soft omezení: modely Omezení nad polookruhy Semiring-based CSP c-polookruh A, +, ×, 0, 1 A množina polookruhu (množina preferencí) 0 A (úplné nesplnění), 1 A (úplné splnění) + komutativní, idempotentní, asociativní operace s jednotkovým prvkem 0, s absorbujím prvkem 1 × komutativní, asociativní operace, distributivní nad +, s jednotkovým prvkem 1, s absorbujím prvkem 0 Částečné uspořádání S: a S b právě tehdy, když a + b = b používá se k výběru ,,lepšího" přiřazení max u fuzzy CSP 0 minimum, 1 maximum, × se používá ke kombinaci preferencí několika omezení min u fuzzy CSP Hana Rudová, Omezující podmínky, 20. prosince 2006 212 Optimalizace & soft omezení: modely Instance omezení nad polookruhy Přístup A + × 0 1 uspořádání kombinace CSP {0, 1} 0 1 Hana Rudová, Omezující podmínky, 20. prosince 2006 213 Optimalizace & soft omezení: modely Instance omezení nad polookruhy Přístup A + × 0 1 uspořádání kombinace CSP {0, 1} 0 1 Fuzzy CSP 0, 1 max min 0 1 Hana Rudová, Omezující podmínky, 20. prosince 2006 213 Optimalizace & soft omezení: modely Instance omezení nad polookruhy Přístup A + × 0 1 uspořádání kombinace CSP {0, 1} 0 1 Fuzzy CSP 0, 1 max min 0 1 CSP s váhami N {+} min + + 0 Hana Rudová, Omezující podmínky, 20. prosince 2006 213 Optimalizace & soft omezení: modely Instance omezení nad polookruhy Přístup A + × 0 1 uspořádání kombinace CSP {0, 1} 0 1 Fuzzy CSP 0, 1 max min 0 1 CSP s váhami N {+} min + + 0 Důležité vlastnosti: striktní monotonie: a, b, c A : (a < c) (b = 0) (a × b) < (c × b) fakt, že něco lze lokálně zlepšit nelze globálně ignorovat CSP s váhami př. a = 0.3, c = 0.4, b = 0.2 pro fuzzy CSP: není striktní monotonie Hana Rudová, Omezující podmínky, 20. prosince 2006 213 Optimalizace & soft omezení: modely Instance omezení nad polookruhy Přístup A + × 0 1 uspořádání kombinace CSP {0, 1} 0 1 Fuzzy CSP 0, 1 max min 0 1 CSP s váhami N {+} min + + 0 Důležité vlastnosti: striktní monotonie: a, b, c A : (a < c) (b = 0) (a × b) < (c × b) fakt, že něco lze lokálně zlepšit nelze globálně ignorovat CSP s váhami př. a = 0.3, c = 0.4, b = 0.2 pro fuzzy CSP: není striktní monotonie idempotence: a A : a × a = a 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 > 1@10, x > 1@10, x = 0@, přiřazení x = 0 má pro omezení s váhami blevel . . . 20 Hana Rudová, Omezující podmínky, 20. prosince 2006 213 Optimalizace & soft omezení: modely Instance omezení nad polookruhy Přístup A + × 0 1 uspořádání kombinace CSP {0, 1} 0 1 Fuzzy CSP 0, 1 max min 0 1 CSP s váhami N {+} min + + 0 Důležité vlastnosti: striktní monotonie: a, b, c A : (a < c) (b = 0) (a × b) < (c × b) fakt, že něco lze lokálně zlepšit nelze globálně ignorovat CSP s váhami př. a = 0.3, c = 0.4, b = 0.2 pro fuzzy CSP: není striktní monotonie idempotence: a A : a × a = a 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 > 1@10, x > 1@10, x = 0@, přiřazení x = 0 má pro omezení s váhami blevel . . . 20 striktní monotonie a idempotence × zároveň lze pouze pro dvouprvkové A, tj. pro CSP Hana Rudová, Omezující podmínky, 20. prosince 2006 213 Optimalizace & soft omezení: modely Instance omezení nad polookruhy Přístup A + × 0 1 uspořádání kombinace CSP {0, 1} 0 1 Fuzzy CSP 0, 1 max min 0 1 CSP s váhami N {+} min + + 0 Důležité vlastnosti: striktní monotonie: a, b, c A : (a < c) (b = 0) (a × b) < (c × b) fakt, že něco lze lokálně zlepšit nelze globálně ignorovat CSP s váhami př. a = 0.3, c = 0.4, b = 0.2 pro fuzzy CSP: není striktní monotonie idempotence: a A : a × a = a 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 > 1@10, x > 1@10, x = 0@, přiřazení x = 0 má pro omezení s váhami blevel . . . 20 striktní monotonie a idempotence × zároveň lze pouze pro dvouprvkové A, tj. pro CSP Existující vztahy: CSP fuzzy CSP na dvouprvkové A fuzzy CSP lze polynomiálně transformovat na CSP s váhami Hana Rudová, Omezující podmínky, 20. prosince 2006 213 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 V, def : D|con| A Soft problém je (C, con) nad (S, D, V), kde con V, C množina omezení Hana Rudová, Omezující podmínky, 20. prosince 2006 214 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 V, def : D|con| A Soft problém je (C, con) nad (S, D, V), kde con V, C množina omezení Projekce n-tic t X Y příklad: (1, 2, 3, 4, 5) (A,B,C,D,E) (D,A,E) = (4, 1, 5) Hana Rudová, Omezující podmínky, 20. prosince 2006 214 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 V, def : D|con| A Soft problém je (C, con) nad (S, D, V), kde con V, C množina omezení Projekce n-tic t X Y příklad: (1, 2, 3, 4, 5) (A,B,C,D,E) (D,A,E) = (4, 1, 5) Kombinace c = c1 c2 c1 = (def 1, con1) and c2 = (def 2, con2) c = (def , con), con = con1 con2, def (t) = def 1(t con con1 ) × def 2(t con con2 ) Hana Rudová, Omezující podmínky, 20. prosince 2006 214 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 V, def : D|con| A Soft problém je (C, con) nad (S, D, V), kde con V, C množina omezení Projekce n-tic t X Y příklad: (1, 2, 3, 4, 5) (A,B,C,D,E) (D,A,E) = (4, 1, 5) Kombinace c = c1 c2 c1 = (def 1, con1) and c2 = (def 2, con2) c = (def , con), con = con1 con2, def (t) = def 1(t con con1 ) × def 2(t con con2 ) příklad: CSP s váhami: A = 0, 1 , + min, × +, +, 0 zadáno omezení c1 na xy: aa 2, ab 4, ba 1, bb 0, zadáno omezení c2 na x: a 0, b 1 kombinace c = c1 c2: aa 2(=2+0) ab 4(=4+0) ba 2(=1+1) bb 1(=0+1) Hana Rudová, Omezující podmínky, 20. prosince 2006 214 Optimalizace & soft omezení: modely Řešení pro omezení nad polookruhy Projekce c I c = (def , con), I V c = (def , con ), con = con I def (t ) = t/tcon Icon=t def (t) příklad (pokračování): c1 na xy: aa 2, ab 4, ba 1, bb 0, projekce c1 {x}: a 2, b 0 Hana Rudová, Omezující podmínky, 20. prosince 2006 215 Optimalizace & soft omezení: modely Řešení pro omezení nad polookruhy Projekce c I c = (def , con), I V c = (def , con ), con = con I def (t ) = t/tcon Icon=t def (t) příklad (pokračování): c1 na xy: aa 2, ab 4, ba 1, bb 0, projekce c1 {x}: a 2, b 0 Úroveň splnění problému P = (C, con) udává omezení Sol(P) = ( C) con kombinace všech omezení v C a následovně projekce na proměnné v con pro každé přiřazení proměnných v con vrací omezení Sol(P) jeho úroveň splnění příklad (pokračování): c1 na xy: aa 2, ab 4, ba 1, bb 0 c2 na x: a 0, b 1 problém P1 = ({c1, c2}, {x, y}): Sol(P1) = (c1 c2){x,y}: aa 2, ab 4, ba 2, bb 1 Hana Rudová, Omezující podmínky, 20. prosince 2006 215 Optimalizace & soft omezení: modely Řešení pro omezení nad polookruhy Projekce c I c = (def , con), I V c = (def , con ), con = con I def (t ) = t/tcon Icon=t def (t) příklad (pokračování): c1 na xy: aa 2, ab 4, ba 1, bb 0, projekce c1 {x}: a 2, b 0 Úroveň splnění problému P = (C, con) udává omezení Sol(P) = ( C) con kombinace všech omezení v C a následovně projekce na proměnné v con pro každé přiřazení proměnných v con vrací omezení Sol(P) jeho úroveň splnění příklad (pokračování): c1 na xy: aa 2, ab 4, ba 1, bb 0 c2 na x: a 0, b 1 problém P1 = ({c1, c2}, {x, y}): Sol(P1) = (c1 c2){x,y}: aa 2, ab 4, ba 2, bb 1 problém P2 = ({c1, c2}, {x}): Sol(P2) = (c1 c2){x}: a 2, b 1 Hana Rudová, Omezující podmínky, 20. prosince 2006 215 Optimalizace & soft omezení: modely Řešení pro omezení nad polookruhy Projekce c I c = (def , con), I V c = (def , con ), con = con I def (t ) = t/tcon Icon=t def (t) příklad (pokračování): c1 na xy: aa 2, ab 4, ba 1, bb 0, projekce c1 {x}: a 2, b 0 Úroveň splnění problému P = (C, con) udává omezení Sol(P) = ( C) con kombinace všech omezení v C a následovně projekce na proměnné v con pro každé přiřazení proměnných v con vrací omezení Sol(P) jeho úroveň splnění příklad (pokračování): c1 na xy: aa 2, ab 4, ba 1, bb 0 c2 na x: a 0, b 1 problém P1 = ({c1, c2}, {x, y}): Sol(P1) = (c1 c2){x,y}: aa 2, ab 4, ba 2, bb 1 problém P2 = ({c1, c2}, {x}): Sol(P2) = (c1 c2){x}: a 2, b 1 Úroveň konzistence: blevel(P) = Sol(P) příklad (pokračování): blevel(P1) = blevel(P2) = 1 Hana Rudová, Omezující podmínky, 20. prosince 2006 215 Optimalizace & soft omezení: modely Optimalizace & soft omezení: algoritmy Soft propagace Klasická propagace: eliminace nekonzistentních hodnot z domén proměnných Soft propagace: propagace preferencí (cen) nad k-ticemi hodnot proměnných snaha o získání realističtějších preferencí výpočet realističtějších příspěvků pro cenovou funkci Hana Rudová, Omezující podmínky, 20. prosince 2006 217 Optimalizace & soft omezení: algoritmy Soft propagace Klasická propagace: eliminace nekonzistentních hodnot z domén proměnných Soft propagace: propagace preferencí (cen) nad k-ticemi hodnot proměnných snaha o získání realističtějších preferencí výpočet realističtějších příspěvků pro cenovou funkci C je soft k-konzistentní, jestliže pro všechny podmnožiny (k - 1) proměnných W a libovolnou další proměnnou y platí {ci | ci C coni W} = ({ci | ci C coni (W {y})}) W 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, 20. prosince 2006 217 Optimalizace & soft omezení: algoritmy Soft hranová konzistence (SAC) k = 2, W = {x} : cx = ({cy, cxy, cx}) x Hana Rudová, Omezující podmínky, 20. prosince 2006 218 Optimalizace & soft omezení: algoritmy Soft hranová konzistence (SAC) k = 2, W = {x} : cx = ({cy, cxy, cx}) x CSP: libovolná hodnota v doméně x může být rozšířena o hodnotu v doméně y tak, že je cxy splněno hodnoty a v doméně x, které nelze rozšířit na y, mají def ((a)) = 0 Hana Rudová, Omezující podmínky, 20. prosince 2006 218 Optimalizace & soft omezení: algoritmy Soft hranová konzistence (SAC) k = 2, W = {x} : cx = ({cy, cxy, cx}) x CSP: libovolná hodnota v doméně x může být rozšířena o hodnotu v doméně y tak, že je cxy splněno hodnoty a v doméně x, které nelze rozšířit na y, mají def ((a)) = 0 Fuzzy CSP: úroveň preference všech hodnot x v cx je stejná jako úroveň preference daná ({cy, cxy, cx}) x Hana Rudová, Omezující podmínky, 20. prosince 2006 218 Optimalizace & soft omezení: algoritmy Soft hranová konzistence (SAC) k = 2, W = {x} : cx = ({cy, cxy, cx}) x CSP: libovolná hodnota v doméně x může být rozšířena o hodnotu v doméně y tak, že je cxy splněno hodnoty a v doméně x, které nelze rozšířit na y, mají def ((a)) = 0 Fuzzy CSP: úroveň preference všech hodnot x v cx je stejná jako úroveň preference daná ({cy, cxy, cx}) x Příklad na fuzzy CSP: A = 0, 1 , + max, × min, 0, 1 x, y {a, b} cx : a . . . 0.9, b . . . 0.1, cy : a . . . 0.9, b . . . 0.5, cxy : aa . . . 0.8, ab . . . 0.2, ba . . . 0, bb . . . 0 není SAC: cx dává 0.9 na x = a, ale ({cy, cxy, cx}) x dává 0.8 {cy, cxy, cx} dává na (a, a) : min(0.9, 0.8, 0.9) = 0.8 {cy, cxy, cx} dává na (a, b) : min(0.5, 0.2, 0.9) = 0.2 projekce ({cy, cxy, cx}) x dává na (a) : max(0.8, 0.2) = 0.8 Hana Rudová, Omezující podmínky, 20. prosince 2006 218 Optimalizace & soft omezení: algoritmy Výpočet SAC Základní algoritmus pro výpočet SAC: pro každé x a y změnit definici cx tak, aby korespondovala s ({cy, cxy, cx}) x iterace až do dosažení stability Hana Rudová, Omezující podmínky, 20. prosince 2006 219 Optimalizace & soft omezení: algoritmy Výpočet SAC Základní algoritmus pro výpočet SAC: pro každé x a y změnit definici cx tak, aby korespondovala s ({cy, cxy, cx}) x iterace až do dosažení stability × idempotentní (fuzzy CSP) zajištěna ekvivalence, tj. původní i nový (po dosažení SAC) problém mají stejné řešení zajištěno ukončení algoritmu Hana Rudová, Omezující podmínky, 20. prosince 2006 219 Optimalizace & soft omezení: algoritmy Výpočet SAC Základní algoritmus pro výpočet SAC: pro každé x a y změnit definici cx tak, aby korespondovala s ({cy, cxy, cx}) x iterace až do dosažení stability × idempotentní (fuzzy CSP) zajištěna ekvivalence, tj. původní i nový (po dosažení SAC) problém mají stejné řešení zajištěno ukončení algoritmu × není idempotentní (CSP s váhami) pro každé u, v A existuje w A taková, že v × w = u 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í Hana Rudová, Omezující podmínky, 20. prosince 2006 219 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í přímé zahrnutí optimalizačního kriteria do evaluace (hodnota obj. funkce) stromové prohledávání metoda větví a mezí + její rozšíření Hana Rudová, Omezující podmínky, 20. prosince 2006 220 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í přímé zahrnutí optimalizačního kriteria do evaluace (hodnota obj. funkce) stromové prohledávání metoda větví a mezí + její rozšíření CSP s omezeními: minimalizace součtu vah omezení min cC c(d) velmi častá optimalizační úloha váha (cena) omezení: 0 = úplné splnění, (0, ) částečné nesplnění, úplné nesplnění hodnota cenové funkce: cena přiřazení/řešení maximalizace je duální problém algoritmy pro fuzzy CSP na podobných principech Hana Rudová, Omezující podmínky, 20. prosince 2006 220 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 C1 Opakované řešení CSP (i = 1 . . .) s přidáním omezení cC c(d) < Ci Když řešení nového CSP neexistuje, pak poslední Ci dává optimum Hana Rudová, Omezující podmínky, 20. prosince 2006 221 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 C1 Opakované řešení CSP (i = 1 . . .) s přidáním omezení cC c(d) < Ci Když řešení nového CSP neexistuje, pak poslední Ci dává optimum Výpočetně zbytečně náročné Efektivní rozšíření obtížné Hana Rudová, Omezující podmínky, 20. prosince 2006 221 Optimalizace & soft omezení: algoritmy Metoda větví a mezí (branch&bound) BB Prohledávání stromu do hloubky přiřazené=minulé proměnné P, nepřiřazené=budoucí proměnné F omezení pouze na minulých proměnných CP , omezení na minulých i budoucích proměnných CPF, omezení pouze na budoucích proměnných CF Hana Rudová, Omezující podmínky, 20. prosince 2006 222 Optimalizace & soft omezení: algoritmy Metoda větví a mezí (branch&bound) BB Prohledávání stromu do hloubky přiřazené=minulé proměnné P, nepřiřazené=budoucí proměnné F omezení pouze na minulých proměnných CP , omezení na minulých i budoucích proměnných CPF, omezení pouze na budoucích proměnných CF Výpočet mezí horní mez UB: cena nejlepšího dosud nalezeného řešení dolní mez LB: dolní odhad minimální ceny pro současné částečné přiřazení Hana Rudová, Omezující podmínky, 20. prosince 2006 222 Optimalizace & soft omezení: algoritmy Metoda větví a mezí (branch&bound) BB Prohledávání stromu do hloubky přiřazené=minulé proměnné P, nepřiřazené=budoucí proměnné F omezení pouze na minulých proměnných CP , omezení na minulých i budoucích proměnných CPF, omezení pouze na budoucích proměnných CF Výpočet mezí horní mez UB: cena nejlepšího dosud nalezeného řešení dolní mez LB: dolní odhad minimální ceny pro současné částečné přiřazení Ořezávání: LB UB 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 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 vyšší než 9 Hana Rudová, Omezující podmínky, 20. prosince 2006 222 Optimalizace & soft omezení: algoritmy Metoda větví a mezí: výběr hodnoty Algorimus metody větví a mezí generický algoritmus rozšiřitelný jako implementace backtrackingu 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 použití při rozšíření o jednu proměnnou LB(ai-1, a) Hana Rudová, Omezující podmínky, 20. prosince 2006 223 Optimalizace & soft omezení: algoritmy Metoda větví a mezí: výběr hodnoty Algorimus metody větví a mezí generický algoritmus rozšiřitelný jako implementace backtrackingu 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 použití při rozšíření o jednu proměnnou LB(ai-1, a) Optimistický výběr hodnoty procedure Select-Value-BB while Di is not empty vyber a smaž libovolný a Di takový, že min LB(ai-1, a) if Consistent(ai-1, xi = a) a LB(ai-1, a) < UB return a (jinak ořezej a) return null (konzistentní hodnota neexistuje) Hana Rudová, Omezující podmínky, 20. prosince 2006 223 Optimalizace & soft omezení: algoritmy Algoritmus metody větví a mezí procedure Branch-Bound((X, D, C), UB, f) rozdíly od backtrackingu i := 1, Di := Di (inicializace čítače proměnných, kopírování domény) Reseni := null (řešení dosud nenalezeno) repeat while 1 i n přiřazení xi := Select-Value-BB if xi is null (žádná hodnota nebyla vrácena) i := i - 1 (zpětná fáze) else i := i + 1 (dopředná fáze) Di := Di if i = 0 if Reseni is not null return UB, Reseni else return ,,nekonzistentní'' else Reseni := x1, . . . , xn (uložení hodnot dosud nejlepšího přiřazení) spočítej cenu současného přiřazení W = c C c(x), UB:=min{W, UB} i := 1, nastav Dk na Dk pro k = 1 . . . n until true end Branch-Bound Hana Rudová, Omezující podmínky, 20. prosince 2006 224 Optimalizace & soft omezení: algoritmy NC algoritmus Projekce ceny hodnot (j, ) pro každou proměnnou j do dolní hranice LB ceny řešení LB=8 3 2 02 4 5 LB=6 (j,1) (j,3) (j,2) j j 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, 20. prosince 2006 225 Optimalizace & soft omezení: algoritmy NC algoritmus Projekce ceny hodnot (j, ) pro každou proměnnou j do dolní hranice LB ceny řešení LB=8 3 2 02 4 5 LB=6 (j,1) (j,3) (j,2) j j Smazání hodnot (j, a) převyšující (nebo rovné) horní hranici UB LB=8 0 2 3 0 LB=8 UB=10 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, 20. prosince 2006 225 Optimalizace & soft omezení: algoritmy AC algoritmus (A) Projekce ceny hrany (i, a)(j, b) do ceny hodnoty (i, a), pokud je tato cena zahrnuta ve všech hranách (i, a)(j, ) 2 LB=6 UB=11 i ij j 1 4 2 3 1 2 2 4 2 3 1 1 1 1 22 2 LB=6 UB=11 (A) (i, 2)(j, 1) - (i, 2)(j, 2) - (i, 2) (i, 2)(j, 3) - Hana Rudová, Omezující podmínky, 20. prosince 2006 226 Optimalizace & soft omezení: algoritmy AC algoritmus (A) Projekce ceny hrany (i, a)(j, b) do ceny hodnoty (i, a), pokud je tato cena zahrnuta ve všech hranách (i, a)(j, ) 2 LB=6 UB=11 i ij j 1 4 2 3 1 2 2 4 2 3 1 1 1 1 22 2 LB=6 UB=11 (A) (i, 2)(j, 1) - (i, 2)(j, 2) - (i, 2) (i, 2)(j, 3) - NC algoritmus (B) projekce ceny hodnot pro každou proměnnou (C) smazání hodnot s cenou UB UB=11 i ij j 1 UB=11 0 0 2 1 2 0 LB=9 LB=9 1 2 0 0 0 1 (B) (C) Hana Rudová, Omezující podmínky, 20. prosince 2006 226 Optimalizace & soft omezení: algoritmy min cC c(d) Dolní mez Kvalita dolní meze: velmi důležitá pro efektivitu BB Dolní mez lze ovlivnit pomocí ceny minulých proměnných 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 lokální ceny budoucích proměnných AC globální ceny budoucích proměnných prohledávání ruská panenka Hana Rudová, Omezující podmínky, 20. prosince 2006 227 Optimalizace & soft omezení: algoritmy Prohledávání ruská panenka (Russion doll search) n po sobě jdoucích BB prohledávání, každé má navíc jednu proměnnou první podproblém obsahuje pouze n-tou proměnnou statické uspořádání proměnných i-tý podproblém obsahuje posledních i proměnných ((n - i + 1) . . . n) podproblémy řešeny pomocí BB s využitím LB a UB z předchozích běhů Hana Rudová, Omezující podmínky, 20. prosince 2006 228 Optimalizace & soft omezení: algoritmy Prohledávání ruská panenka (Russion doll search) n po sobě jdoucích BB prohledávání, každé má navíc jednu proměnnou první podproblém obsahuje pouze n-tou proměnnou statické uspořádání proměnných i-tý podproblém obsahuje posledních i proměnných ((n - i + 1) . . . n) podproblémy řešeny pomocí BB s využitím LB a UB z předchozích běhů Při řešení podproblému (n - i + 1) problém zahrnuje proměnné xi, xi+1, . . . , xn mějme částečné přiřazení pro tento podproblém (ai, ai+1, . . . , ai+j) s nepřiřazenými proměnnými xi+j+1, . . . , xn Hana Rudová, Omezující podmínky, 20. prosince 2006 228 Optimalizace & soft omezení: algoritmy Prohledávání ruská panenka (Russion doll search) n po sobě jdoucích BB prohledávání, každé má navíc jednu proměnnou první podproblém obsahuje pouze n-tou proměnnou statické uspořádání proměnných i-tý podproblém obsahuje posledních i proměnných ((n - i + 1) . . . n) podproblémy řešeny pomocí BB s využitím LB a UB z předchozích běhů Při řešení podproblému (n - i + 1) problém zahrnuje proměnné xi, xi+1, . . . , xn mějme částečné přiřazení pro tento podproblém (ai, ai+1, . . . , ai+j) s nepřiřazenými proměnnými xi+j+1, . . . , xn do dolní meze lze zahrnout optimální cenu (n - i - j) podproblému LB((ai, ai+1, . . . , ai+j)) = dist((ai, ai+1, . . . , ai+j)) + optim(xi+j+1, . . . , xn) optimální řešení přechozích problémů použita pro: výběr hodnoty, pro zlepšení iniciální horní meze Hana Rudová, Omezující podmínky, 20. prosince 2006 228 Optimalizace & soft omezení: algoritmy Prohledávání ruská panenka (Russion doll search) n po sobě jdoucích BB prohledávání, každé má navíc jednu proměnnou první podproblém obsahuje pouze n-tou proměnnou statické uspořádání proměnných i-tý podproblém obsahuje posledních i proměnných ((n - i + 1) . . . n) podproblémy řešeny pomocí BB s využitím LB a UB z předchozích běhů Při řešení podproblému (n - i + 1) problém zahrnuje proměnné xi, xi+1, . . . , xn mějme částečné přiřazení pro tento podproblém (ai, ai+1, . . . , ai+j) s nepřiřazenými proměnnými xi+j+1, . . . , xn do dolní meze lze zahrnout optimální cenu (n - i - j) podproblému LB((ai, ai+1, . . . , ai+j)) = dist((ai, ai+1, . . . , ai+j)) + optim(xi+j+1, . . . , xn) optimální řešení přechozích problémů použita pro: výběr hodnoty, pro zlepšení iniciální horní meze Vnořená prohledávání se vyplatí vzhledem k prořezání stavového prostoru Hana Rudová, Omezující podmínky, 20. prosince 2006 228 Optimalizace & soft omezení: algoritmy Dynamické problémy: změny a nejistota Literatura: Constraint solving in uncertain and dynamic environments: A survey. Gérard Verfaillie, Narendra Jussien. Constraints, 10:3, 253-281, Kluwer Academic Publishers, 2005. http://www.springerlink.com/content/j566801727184h84/fulltext.pdf Změny a nejistota v problémech Definice vyřešených problémů se může změnit a je nutné nalézt nové řešení pro upravený problém Změny mohou být dány např. vstupem od uživatele příklad: školní rozvrhování nové požadavky na rozvrh na základě už vygenerovaného rozvrhu Nejistota může být dána např. prostředím příklad: plán cesty může být narušen počasím Zachycení nejistoty je možné částečně realizovat i pomocí soft omezení fuzzy CSP Na změny a nejistotu se lze připravit off-line i s ní pracovat on-line Hana Rudová, Omezující podmínky, 20. prosince 2006 230 Dynamické problémy Architektura systému Hana Rudová, Omezující podmínky, 20. prosince 2006 231 Dynamické problémy Architektura systému: popis Reaktivní část reakce v rámci striktně limitovaného času (hard) real-time část On-line poradní (deliberative) část omezení na čas nejsou tak striktní soft real-time část Off-line poradní (deliberative) čast bez specifických časových požadavků na výpočet Hana Rudová, Omezující podmínky, 20. prosince 2006 232 Dynamické problémy Příklad: cestování Systém managementu cestovaní v autě na dlouhé vzdálenosti směrování, zastávky, rezervace, schůzky, doplnění paliva, údržba Architektura systému fyzický systém (physical system) = auto uživatel (user) = řidič fyzické prostředí (physical environmet) = silnice, provoz, počasí další entity (other entities) = hotely, restaurace, garáže, další lidé, ... Nejistota a změny závisí na aktuální dostupnosti entit řidiči (změny v cílech nebo v akutálním plánu) autě (neočekávané poruchy) fyzickém prostřední (dopravní zácpy) Hana Rudová, Omezující podmínky, 20. prosince 2006 233 Dynamické problémy Aplikační oblasti Obecně on-line plánování a rozvrhování Reálné aplikace online computer vision, failure diagnosis, situation tracking s nejistotou, co bylo pozorováno; změny v množině pozorování počítačový návrh systému nebo konfigurace nejistota o prostředí používání systému, změny dané uživatelem a návrhařem management uživatelského rozhraní změny jako důsledek akcí uživatele nebo sw interaktivní nebo distribuované řešení problému nejistota a změny plynoucí z rozhodnutí uživatele a okolí Nezávisle na aplikační doméně interaktivní specifikace problému, ladění CP programu při neuspořádaném lokálním prohledávání (dyn. backtracking, iterativní dopředné prohl.) se změnami plynoucími z přiřazení/zrušení přiřazení proměnných Hana Rudová, Omezující podmínky, 20. prosince 2006 234 Dynamické problémy Hlavní požadavky Omezit co nejvíce potřebu online řešení problému online řešení spotřebovává čas i zdroje a narušuje řešení, pokud časté změny příklad: řidič nechce měnit trasu nebo plán v důsledku po sobě jdoucích změna Omezit co nejvíce změny v produkovaném řešení příliš důležité změny jsou nežádoucí příklad: řidič nechce úplně měnit trasu nebo plán v důsledku malé změny Omezit co nejvíce výpočetní čas a zdroje pro online řešení o novém řešení je nutné informovat včas příklad: řidič nesmí být informován o změně směru na dálnici, když už minul daný exit Stále produkovat konzistentní a optimální řešení Hana Rudová, Omezující podmínky, 20. prosince 2006 235 Dynamické problémy Dynamický problém splňování (DCSP) Teoretický přístup k modelování, velmi obecný přístup Jedná se o posloupnost CSP nový CSP vznikne změnou definice předchozího typy změn: přidání nebo odstranění proměnných, přidání nebo odebrání hodnot z domény, přidání nebo odebrání omezení, změna rozsahu proměnných pro omezení, změna definice omezení Hana Rudová, Omezující podmínky, 20. prosince 2006 236 Dynamické problémy Dynamický problém splňování (DCSP) Teoretický přístup k modelování, velmi obecný přístup Jedná se o posloupnost CSP nový CSP vznikne změnou definice předchozího typy změn: přidání nebo odstranění proměnných, přidání nebo odebrání hodnot z domény, přidání nebo odebrání omezení, změna rozsahu proměnných pro omezení, změna definice omezení Všechny typy změn lze zachytit prostřednictvím přidání/odstranění omezení Dynamický problém splňování (DCSP) je posloupnost {P0, P1, . . . , Pn}, kde každé Pi je CSP daný množinou omezení Ci (z ní plynou domény a proměnné) Cai je množina přidaných omezení Cri je množina odebraných omezení a platí: Cri Ci-1 a Ci = Cai Ci-1\Cri Hana Rudová, Omezující podmínky, 20. prosince 2006 236 Dynamické problémy Řešící metody Reaktivní metody nepoužívají žádný model budoucích změn pokud nastane změna, snaží se maximálně vyhnout počítání (reasoning) od úplného začátku nevýhoda: nedostatek robusnosti generovaného řešení možná výhoda: schopnost reagovat na libovolný typ změny znovu použití řešení znovu použití počítání Hana Rudová, Omezující podmínky, 20. prosince 2006 237 Dynamické problémy Řešící metody Reaktivní metody nepoužívají žádný model budoucích změn pokud nastane změna, snaží se maximálně vyhnout počítání (reasoning) od úplného začátku nevýhoda: nedostatek robusnosti generovaného řešení možná výhoda: schopnost reagovat na libovolný typ změny znovu použití řešení znovu použití počítání Proaktivní metody: snaha produkovat robusní řešení, která mají šanci zůstat řešeními i navzdory změnám flexibilní řešení, která mohou být snadno adaptována změně Hana Rudová, Omezující podmínky, 20. prosince 2006 237 Dynamické problémy Možné informace k znovu použití Lokální konzistence nebo nekonzistence částečného přiřazení vzhledem k dané úrovni konzistence Globální konzistence nebo nekonzistence částečného přiřazení schopnost/neschopnost rozšíření na řešení Konzistence nebo nekonzistence úplného řešení zda, je nebo není řešení Konzistence nebo nekonzistence problému globální konzistence nebo nekonzistence prázdného přiřazení V podstatě metody znovu použití řešení využívají informace o konzistenci metody znovu použití počítání využívají informace o nekonzistenci Hana Rudová, Omezující podmínky, 20. prosince 2006 238 Dynamické problémy Metody znovu použití řešení (solution reuse) Stromové prohledávání prohledávání stromu do hloubky, prohledávání s omezenými diskrepancemi (LDS) použití předchozího řešení jako heuristiku pro výběr hodnot Lokální prohledávání asi nejvhodnější pro dynamické problémy předchozí řešení použito jako počáteční přiřazení Perturbace řešení princip: off-line připravit posloupnost metod, které mohou být přímo použity při změně předchozího řešení pro acyklické sítě omezení zahrnující pouze dataflow omezení několik vstupních proměnných, jedna výstupní proměnná, která je funkcí ostatních algoritmy v oblasti uživatelských rozhraní Hana Rudová, Omezující podmínky, 20. prosince 2006 239 Dynamické problémy Metody znovu použití řešení II Zrušení přiřazení hodnot a znovu přiřazení algoritmus: lokální změny (local changes), iterativní dopředné prohledávání princip (rekurzivní proces): 1. nalezení nesplněných omezení 2. zrušení přiřazení alespoň jedné proměnné pro nesplněné omezení 3. znovu přiřazení těchto proměnných: (a) výběr hodnoty a nalezení nesplněných omezení (b) zrušení přiřazení alespoň jedné proměnné pro nesplněné omezení (c) znovu přiřazení hodnot tak, že se vyhneme zrušení přiřazení proměnných, které způsobily prvotní zrušení (2) rozšíření iterativního dopředného prohledávání zrušíme přiřazení hodnot, které jsou v konfliktu s novými omezeními pustíme algoritmus se vzniklým částečným přiřazení a upravenou množinou omezení upravíme evaluační funkci tak, že přidáme kritérium počtu hodnot přiřazených odlišně Hana Rudová, Omezující podmínky, 20. prosince 2006 240 Dynamické problémy Znovu použití počítání (reasoning reuse) Lze použít v případě, že 1. předchozí problem P byl vyřešen a byla dokázána jeho konzistence nebo nekonzistence 2. toto řešení vygenerovalo množinu implikovaných omezení I (důsledků tzv. iniciáních omezení v P) 3. nastala změna v definici P, vznikl P ale 4. vzhledem k relaxaci problému, není garantována platnost I pro P Hana Rudová, Omezující podmínky, 20. prosince 2006 241 Dynamické problémy Znovu použití počítání (reasoning reuse) Lze použít v případě, že 1. předchozí problem P byl vyřešen a byla dokázána jeho konzistence nebo nekonzistence 2. toto řešení vygenerovalo množinu implikovaných omezení I (důsledků tzv. iniciáních omezení v P) 3. nastala změna v definici P, vznikl P ale 4. vzhledem k relaxaci problému, není garantována platnost I pro P Dvoufázový proces 1. množina omezení I I, která mohou být neplatná je z I odstraněna 2. nová množina I je generována z P a I\I Kritický faktor: co nejvíce omezit odstraňování omezení ve fázi (1) Metody se liší způsobem určení I , použití grafu podmínek, constraint justification, constraint explanation Hana Rudová, Omezující podmínky, 20. prosince 2006 241 Dynamické problémy Grafové metody pro znovu použití počítání Používají graf podmínek k určení, zda by omezení mohlo být neplatné Pokud je iniciální omezení c smazáno nebo pokud je odstraněno implikované omezení c z I pak mohou být neplatná všechna omezení, která byla generována použitím c v závislosti na grafu podmínek Příklad: hranová konzistence pokud je přidána hodnota do domény proměnné v všechna odstranění z domén proměnných, která jsou spojena z v mohou být neplatná Hana Rudová, Omezující podmínky, 20. prosince 2006 242 Dynamické problémy Ospravedlnění omezení (constraint justification) Ospravedlnění implikovaného omezení c = omezení c, které toto omezení přímo generovalo Příklad: hranová konzistence ospravedlnění odstranění val z domény v je omezení, které svazuje v z další proměnnou v, která nemá žádnou podporu pro val Hana Rudová, Omezující podmínky, 20. prosince 2006 243 Dynamické problémy Ospravedlnění omezení (constraint justification) Ospravedlnění implikovaného omezení c = omezení c, které toto omezení přímo generovalo Příklad: hranová konzistence ospravedlnění odstranění val z domény v je omezení, které svazuje v z další proměnnou v, která nemá žádnou podporu pro val Jakmile je iniciální nebo implikované omezení c odstraněno, všechna implikovaná omezení, která obsahují c v ospravedlnění, mohou být neplatná Příklad (pokračování): jakmile je do domény v přidána další hodnota, odstranění hodnoty v , nemusí být nyní korektní a je potřeba ověřit Hana Rudová, Omezující podmínky, 20. prosince 2006 243 Dynamické problémy Vysvětlení omezení (constraint explanation) Liší se od ospravedlnění omezení typem informace zaznamenávané s každým implikovaným omezením c Zaznamenávaná informace = vysvětlení omezení jedná se o množinu C iniciálních omezení, které c logicky implikují Tj. vysvětlení omezení představují úplnější informaci Pokud je odstraněno iniciální omezení c, pak jsou všechna implikovaná omezení, která obsahují c, smazána najednou bez propagace Hana Rudová, Omezující podmínky, 20. prosince 2006 244 Dynamické problémy Komentáře ke složitosti Ospravedlnění omezení a vysvětlení omezení náročnější než grafové metody Ospravedlnění omezení přesnější než grafové metody u ospravedlnění omezení je třeba prověřit méně omezení Vysvětlení omezení přesnější než ospravedlnění omezení u vysvětlení omezení není třeba prověřit navíc žádné omezení (úplná metoda) Nejhorší čas. složitost metod znovu použití stejná jako při výpočtu od začátku Nejhorší prostorová složitost ospravedlnění a vysvětlení je polynomiální velikost ospravedlnění a vysvětlení je limitováno počtem omezení pouze jedno vysvětlení nebo ospravedlnění je svázáno s každám implikovaným omezením Experimenálně ale metody znovu použití přináší zlepšení Hana Rudová, Omezující podmínky, 20. prosince 2006 245 Dynamické problémy Robusní řešení Výpočet robusního řešení robusní řešení zůstává řešením navzdory změnám výpočet robusního řešení bere v úvahu model budoucích změn dosud navržené metody se liší především v použitém modelu nejistoty Kvalitativní model změn Wallace & Freuder 1998 bereme v úvahu informace o možných ztrátách hodnoty z domény nebo kombinace hodnot z omezení heuristika pak využívá takové hodnoty/kombinace hodnot, které spíše zůstanou platné Hana Rudová, Omezující podmínky, 20. prosince 2006 246 Dynamické problémy Robusní řešení Výpočet robusního řešení robusní řešení zůstává řešením navzdory změnám výpočet robusního řešení bere v úvahu model budoucích změn dosud navržené metody se liší především v použitém modelu nejistoty Kvalitativní model změn Wallace & Freuder 1998 bereme v úvahu informace o možných ztrátách hodnoty z domény nebo kombinace hodnot z omezení heuristika pak využívá takové hodnoty/kombinace hodnot, které spíše zůstanou platné Mixed CSP Fargier et al. 1996 rozhodovací proměnné (lze řídit/měnit hodnotu) ... decision, controllable variables stavové proměnné (nelze řídit) ... state, uncontrollable variables základní cíl: nalézt hodnoty rozhodovacích proměnných nezávisle na hodnotě stavových proměnných Hana Rudová, Omezující podmínky, 20. prosince 2006 246 Dynamické problémy Robusní řešení II Stochastické (stochastic) CSP Walsh 2002 rozhodovací proměnné + stavové proměnné nově: pravděpodobnostní rozdělení spojedno s doménou každé stavové proměnné nalézt hodnoty rozhodovacích proměnných tak, aby byla maximalizována pravděpodobnost konzistence v reálném světě Hana Rudová, Omezující podmínky, 20. prosince 2006 247 Dynamické problémy Robusní řešení II Stochastické (stochastic) CSP Walsh 2002 rozhodovací proměnné + stavové proměnné nově: pravděpodobnostní rozdělení spojedno s doménou každé stavové proměnné nalézt hodnoty rozhodovacích proměnných tak, aby byla maximalizována pravděpodobnost konzistence v reálném světě Pravděpodobnostní (probabilistic) CSP Fargier & Lang 1993 pravděpodobnost existence pro každé omezení základní cíl: nalézt řešení maximalizující pravděpodobnost konzistence v reálném světě instance Omezení nad polookruhy Hana Rudová, Omezující podmínky, 20. prosince 2006 247 Dynamické problémy Flexibilní řešení Přístupy v této oblasti zatím dost nesourodé záměnost hodnot (value interchangability) Freuder 1991 může být chápáno jako základ pro generování flexibilních řešení hodnoty proměnné lze vyměnit např. bez porušení dalších omezení Hana Rudová, Omezující podmínky, 20. prosince 2006 248 Dynamické problémy Flexibilní řešení Přístupy v této oblasti zatím dost nesourodé záměnost hodnot (value interchangability) Freuder 1991 může být chápáno jako základ pro generování flexibilních řešení hodnoty proměnné lze vyměnit např. bez porušení dalších omezení Množina řešení formou kartézského součinu Lesaint 1993 příklad: proměnné x, y, z, omezení x < z {x = {1, 2}, y = 3, z = {2, 3}} je flexibilnější než {x = 1, y = 3, z = 2} Hana Rudová, Omezující podmínky, 20. prosince 2006 248 Dynamické problémy Flexibilní řešení Přístupy v této oblasti zatím dost nesourodé záměnost hodnot (value interchangability) Freuder 1991 může být chápáno jako základ pro generování flexibilních řešení hodnoty proměnné lze vyměnit např. bez porušení dalších omezení Množina řešení formou kartézského součinu Lesaint 1993 příklad: proměnné x, y, z, omezení x < z {x = {1, 2}, y = 3, z = {2, 3}} je flexibilnější než {x = 1, y = 3, z = 2} Kompaktní reprezentace množiny řešení pomocí automatu Vempaty 1992 konstrukce automatu generujícího všechna řešení off-line umožňuje rychlou reakci on-line Hana Rudová, Omezující podmínky, 20. prosince 2006 248 Dynamické problémy Flexibilní řešení II Super-řešení (supersolution) Hebrard et al. 2004 (a, b) super-řešení s má následující vlastnost: když změníme v řešení s nejvýše a proměnných hodnotu, stačí opravit nejvýše b dalších proměnných a máme opět řešení příklad: x, z {1, 2}, y, t {1, 2, 3}, x < y y = t y = z x = 1, y = 3, z = 1, t = 3 je (1, 1)-super-řešení žádná změna pro další proměnné, pokud x ztratí hodnotu 1 jedna změna, pokud y ztratí hodnotu 3 žádná změna, pokud z ztratí hodnotu 1 jedna změna, pokud t ztratí hodnotu 3 ostatní řešení jsou (1, 2) nebo (1, 3)-super-řešení, tj. (1, 1)-super-řešení preferováno Hana Rudová, Omezující podmínky, 20. prosince 2006 249 Dynamické problémy Budoucnost Řada studií o změnách a nejistotě zaměřená na specifické aspekty (jako efektivní udržování řešení, AC, způsob generování robusních řešení) je třeba globální studie požadavků Dekrementální propagace omezení (odebrání omezení) je třeba její přidání do řešičů Stavové proměnné je třeba jejich přidání do řešičů Kombinace reaktivních a proaktivních přístupů jak nalézt flexibilní a robusní řešení a přitom uchovávat informaci pro snadnou adaptaci řešení . . . Hana Rudová, Omezující podmínky, 20. prosince 2006 250 Dynamické problémy 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.cuni.cz/~bartak/podminky/prednaska.html Apt K., CWI, Holandsko. Průsvitky ke knize Principles of Constraint Programming http://homepages.cwi.nl/~apt/pcp/ Dechter R., University of California, USA. Průsvitky ke knize Constraint processing http://www.ics.uci.edu/~dechter/books/materials.html Constraint solving in uncertain and dynamic environments: A survey. Gérard Verfaillie, Narendra Jussien. Constraints, 10:3, 253-281, Kluwer Academic Publishers, 2005. http://ai.uwaterloo.ca/~vanbeek/Constraints/Papers/VerfaillieJ05.pdf Hana Rudová, Omezující podmínky, 20. prosince 2006 251 Zdroje