Úvod do programování s omezujícími podmínkami (pokračování) Polynomiální a NP-úplné problémy m Polynomiální problémy existuje algoritmus polynomiální složitosti pro řešení problému NP-úplné problémy 3 řešitelné nedeterministickým polynomiálním algoritmem 3 potenciální řešení lze ověřit v polynomiálním čase 3 v nejhorším případě exponenciální složitost (pokud neplatí P=NP) Hana Rudová, Omezující podmínky, 23. září 201 9 2 Úvod do CP Složitost: polynomiální problémy 3 Lineární rovnice nad reálnými čísly 3 proměnné nad doménami z R, omezení: lineární rovnice «• Gaussova eliminace M polynomiální složitost Hana Rudová, Omezující podmínky, 23. září 201 9 3 Úvod do CP Složitost: polynomiální problémy Lineární rovnice nad reálnými čísly S proměnné nad doménami z R, omezení: lineární rovnice M Gaussova eliminace 3 polynomiální složitost Lineární nerovnice nad reálnými čísly 3 lineární programování, simplexová metoda často stačí polynomiální složitost Hana Rudová, Omezující podmínky, 23. září 201 9 3 Úvod do CP Složitost: NP-úplné problémy m Boolean omezení 0/1 proměnné 3 omezení = Boolean formule (konjunkce, disjunkce, implikace, ...) * příklad: proměnné A,B,C, omezení (A v B), (C => A), CSP problém (A v B) a (C => A) Hana Rudová, Omezující podmínky, 23. září 201 9 4 Úvod do CP Složitost: NP-úplné problémy m Boolean omezení 0/1 proměnné M omezení = Boolean formule (konjunkce, disjunkce, implikace, ...) &> příklad: proměnné A,B, C, omezení (A v B), (C => A), CSP problém (A v B) a (C => A) M problém splnitelnosti Boolean formule (SAT problém): NP-úplný n proměnných: Hana Rudová, Omezující podmínky, 23. září 201 9 4 Úvod do CP Složitost: NP-úplné problémy Boolean omezení 0/1 proměnné omezení = Boolean formule (konjunkce, disjunkce, implikace, ...) A příklad: proměnné A,B, C, omezení (A v B), (C => A), CSP problém (A v B) a (C => A) M problém splnitelnosti Boolean formule (SAT problém): NP-úplný n proměnných: 2n možností Hana Rudová, Omezující podmínky, 23. září 201 9 4 Úvod do CP Složitost: NP-úplné problémy Boolean omezení 0/1 proměnné omezení = Boolean formule (konjunkce, disjunkce, implikace, ...) 3 příklad: proměnné A,B, C, omezení (A v B), (C => A), CSP problém (A v B) a (C => A) M problém splnitelnosti Boolean formule (SAT problém): NP-úplný n proměnných: 2n možností Omezení nad konečnými doménami obecný CSP problém 3 problém splnitelnosti nad obecnými relacemi 3 NP-úplný problém n proměnných, d maximální velikost domény: Hana Rudová, Omezující podmínky, 23. září 201 9 4 Úvod do CP Složitost: NP-úplné problémy Boolean omezení 0/1 proměnné omezení = Boolean formule (konjunkce, disjunkce, implikace, ...) 3 příklad: proměnné A,B, C, omezení (A v B), (C => A), CSP problém (A v B) a (C => A) M problém splnitelnosti Boolean formule (SAT problém): NP-úplný n proměnných: 2n možností Omezení nad konečnými doménami obecný CSP problém 3 problém splnitelnosti nad obecnými relacemi 3 NP-úplný problém 3 n proměnných, d maximální velikost domény: dn možností Hana Rudová, Omezující podmínky, 23. září 201 9 4 Úvod do CP Složitost a úplnost 3 Úplné vs. neúplné algoritmy 3 úplný algoritmus prozkoumává množinu všech řešení neúplný algoritmus: neprozkoumává celou množinu řešení 3 nevím jako možná odpověď, ziskem může být efektivita příklad: neúplný polynomiální algoritmus pro NP-úplný problém Hana Rudová, Omezující podmínky, 23. září 201 9 5 Úvod do CP Složitost a úplnost Úplné vs. neúplné algoritmy úplný algoritmus prozkoumává množinu všech řešení «• neúplný algoritmus: neprozkoumává celou množinu řešení 3 nevírn jako možná odpověď, ziskem může být efektivita «• příklad: neúplný polynomiální algoritmus pro NP-úplný problém m Složitost řešiče Gaussova eliminace (P), SAT řešiče (NP), obecný CSP řešič (NP) Hana Rudová, Omezující podmínky, 23. září 201 9 5 Úvod do CP Složitost a úplnost m Úplné vs. neúplné algoritmy M úplný algoritmus prozkoumává množinu všech řešení neúplný algoritmus: neprozkoumává celou množinu řešení ± nevím jako možná odpověď, ziskem může být efektivita příklad: neúplný polynomiální algoritmus pro NP-úplný problém Složitost řešiče 3 Gaussova eliminace (P), SAT řešiče (NP), obecný CSP řešič (NP) Složitost algoritmů propagace omezení většinou polynomiální neúplné algoritmy Hana Rudová, Omezující podmínky, 23. září 201 9 5 Úvod do CP Složitost a úplnost 3 Úplné vs. neúplné algoritmy úplný algoritmus prozkoumává množinu všech řešení «• neúplný algoritmus: neprozkoumává celou množinu řešení ± nevím jako možná odpověď, ziskem může být efektivita M příklad: neúplný polynomiální algoritmus pro NP-úplný problém Složitost řešiče Gaussova eliminace (P), SAT řešiče (NP), obecný CSP řešič (NP) Složitost algoritmů propagace omezení většinou polynomiální neúplné algoritmy 3 Složitost prohledávacích algoritmů 3 úplné algoritmy, příklady: backtracking, generuj & testuj neúplné algoritmy, neprohledávají celý prostor řešení, příklad: omezení času prohledávání Hana Rudová, Omezující podmínky, 23. září 2019 5 Úvod do CP Grafová reprezentace CSP 3 Reprezentace podmínek M intenzionální (matematická/logická formule) M extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) Hana Rudová, Omezující podmínky, 23. září 201 9 6 Úvod do CP Grafová reprezentace CSP Reprezentace podmínek 3 intenzionální (matematická/logická formule) 3 extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) 3 Graf: vrcholy, hrany (hrana spojuje dva vrcholy) 3 Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholů) Reprezentace CSP pomocí hypergrafu podmínek 3 vrchol = proměnná, hyperhrana = podmínka Hana Rudová, Omezující podmínky, 23. září 201 9 6 Úvod do CP Grafová reprezentace CSP Reprezentace podmínek 3 intenzionální (matematická/logická formule) M extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) 3 Graf: vrcholy, hrany (hrana spojuje dva vrcholy) 3 Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholů) Reprezentace CSP pomocí hypergrafu podmínek 3 vrchol = proměnná, hyperhrana = podmínka Binární CSP Binární CSP CSP, ve kterém jsou pouze binární podmínky 3 unární podmínky zakódovány do domény proměnné Graf podmínek pro binární CSP 3 není nutné uvažovat hypergraf, stačí graf (podmínka spojuje pouze dva vrcholy) CSP lze transformovat na binární CSP Ekvivalence CSP dva CSP problémy jsou ekvivalentní, pokud mají stejnou množinu řešení Rozšířená ekvivalence CSP 3 řešení problémů lze mezi sebou „syntakticky" převést 3 např: obecný CSP převedeme na binární CSP a porovnáme tyto binární CSP Hana Rudová, Omezující podmínky, 23. září 2019 7 Úvod do CP Duální problém Duální problém: původním omezením odpovídají nové duální proměnné proměnné: fc-ární podmínku q převedeme na duální proměnnou Ví s doménou obsahující konzistentní fc-tice 3 omezení: pro každou dvojici podmínek q a Cj sdílející proměnné zavedeme binární podmínku Ríj mezi Ví a Vj omezující duální proměnné na fc-tice, ve kterých mají sdílené proměnné stejnou hodnotu Příklad proměnné X\,... ,Xq s doménou {0,1} omezení c\ : X\ + x2 + Xq = 1... v\ c2 : X\ - x3 + x4 = 1... v2 c3 : x4 + Xs - Xq > 0 . . . v3 c4 : x2 + Xs - Xq = 0 . . . v4 (0,0,1), (0,1,0), R21 & R33 (1,0,0) R11 ^SS\SR33 (0,0,1), (1,0,0), (1,1,1) R31 (0,0,0), (0,1,1), (1,0,1) R22 & R33 (0,1,0), (1,0,0), (1,1,0), (1,1,1) Hana Rudová, Omezující podmínky, 23. září 201 9 8 Úvod do CP Použití binarizace 3 Konstrukce duálního problému M jedna z možných metod binarizace Výhody binarizace 3 získáváme unifikovaný tvar CSP problému řada algoritmů navržena pro binární CSP M pro výukové účely je vysvětlení na binárních CSP vhodné M algoritmy jsou přehlednější a jednodušší na pochopení -i* verze pro nebinární podmínky je často přímým rozšířením obecné verze ±* a tyto algoritmy jsou i aplikovatelné s pomocí binarizace na obecné CSP Ale: značné zvětšení velikosti problému Hana Rudová, Omezující podmínky, 23. září 201 9 9 Úvod do CP Použití binarizace 3 Konstrukce duálního problému M jedna z možných metod binarizace Výhody binarizace 3 získáváme unifikovaný tvar CSP problému řada algoritmů navržena pro binární CSP 3 pro výukové účely je vysvětlení na binárních CSP vhodné 3 algoritmy jsou přehlednější a jednodušší na pochopení -i* verze pro nebinární podmínky je často přímým rozšířením obecné verze ±* a tyto algoritmy jsou i aplikovatelné s pomocí binarizace na obecné CSP Ale: značné zvětšení velikosti problému Nebinární podmínky 3 složitější propagační algoritmy 3 lze využít jejich sémantiky pro lepší propagaci příklad: al l_di f f erent vs. množina binárních nerovností Hana Rudová, Omezující podmínky, 23. září 2019 9 Úvod do CP Hranová konzistence Propagace omezení Příklad: S proměnné: A,B,C .•domény: A g {0,1} B=0 C g {0,1,2,3} M omezení: A^B, B^C, A^C =^> A=l, B=0, C g {2,3} Algoritmy pro propagaci omezení (konzistenční algoritmy) umožňují odstranit nekonzistentní hodnoty z domén proměnných zjednodušují problém udržují ekvivalenci mezi původním a zjednodušeným problémem Hana Rudová, Omezující podmínky, 23. září 201 9 Hranová konzistence Vrcholová konzistence Vrcholová konzistence (node consistency) NC 3 unární podmínky převedeme do domén proměnných Vrchol reprezentující Vije vrcholově konzistentní: každá hodnota z aktuální domény proměnné Ví splňuje všechny unární podmínky s proměnnou Ví Hana Rudová, Omezující podmínky, 23. září 201 9 12 Hranová konzistence Vrcholová konzistence Vrcholová konzistence (node consistency) NC S unární podmínky převedeme do domén proměnných Vrchol reprezentující Vije vrcholově konzistentní: M každá hodnota z aktuální domény proměnné Ví splňuje všechny unární podmínky s proměnnou Ví 3 CSP problém je vrcholově konzistentní: M každý jeho vrchol je vrcholově konzistentní Hana Rudová, Omezující podmínky, 23. září 201 9 12 Hranová konzistence Hranová konzistence (Arc Consistency AC) 3 Pouze pro binární CSP (až její rozšíření jsou pro nebinární CSP) podmínka odpovídá hraně v grafu podmínek více podmínek najedná hraně převedeme dojedná podmínky Hrana (Ví, V}) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Dí existuje hodnota y v D j tak, že ohodnocení [Ví = x,Vj = y] splňuje všechny binární podmínky nad Ví, V/. Hana Rudová, Omezující podmínky, 23. září 201 9 13 Hranová konzistence Hranová konzistence (Arc Consistency AC) Pouze pro binární CSP (až její rozšíření jsou pro nebinární CSP) podmínka odpovídá hraně v grafu podmínek více podmínek najedná hraně převedeme dojedná podmínky Hrana (Ví, V}) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Dí existuje hodnota y v D j tak, že ohodnocení [Ví = x,Vj = y] splňuje všechny binární podmínky nad Ví, V/. Hranová konzistence je směrová M konzistence hrany (VuVj) nezaručuje konzistenci hrany (Ví,Ví) A již zrevidované hrany opět nekonzistentní Revize hrany opakujeme, dokud dochází ke zmenšení nějaké domény & procedure AC-l(G) repeat Changed := false for V hranu (í, j) g G do Changed := revise((í,j)) or Changed until not(Changed) end AC-1 Hana Rudová, Omezující podmínky, 23. září 2019 15 Hranová konzistence Algoritmus AC-1 Jak udělat CSP hranově konzistentní? Provedeme revizi každé hrany A již zrevidované hrany opět nekonzistentní Revize hrany opakujeme, dokud dochází ke zmenšení nějaké domény 3 procedure AC-l(G) repeat Changed := false for V hranu (í, j) g G do Changed := revi se((í, j)) or Changed until not(Changed) end AC-1 => AB, BA, BC, CB, Hana Rudová, Omezující podmínky, 23. září 2019 15 Hranová konzistence Algoritmus AC-1 Jak udělat CSP hranově konzistentní? Provedeme revizi každé hrany A již zrevidované hrany opět nekonzistentní Revize hrany opakujeme, dokud dochází ke zmenšení nějaké domény 3 procedure AC-l(G) repeat Changed := false for V hranu (í, j) g G do Changed := revise((í,j)) or Changed until not(Changed) end AC-1 => AB, BA, BC, CB, AB, BA, BC, CB, Hana Rudová, Omezující podmínky, 23. září 2019 15 Hranová konzistence Algoritmus AC-1 Jak udělat CSP hranově konzistentní? Provedeme revizi každé hrany A již zrevidované hrany opět nekonzistentní Revize hrany opakujeme, dokud dochází ke zmenšení nějaké domény 3 procedure AC-l(G) repeat Changed := false for V hranu (í, j) g G do Changed := revi se((í, j)) or Changed until not(Changed) end AC-1 => AB, BA, BC, CB, AB, BA, BC, CB, AB, BA, BC, CB Hana Rudová, Omezující podmínky, 23. září 2019 15 Hranová konzistence Složitost AC-1 proceduře AC-l(G) repeat Changed := false for V hranu (í,j) g G do Changed := revi se((í, j)) or Changed until not(Changed) end AC-1 k maximální velikost domény, e počet hran, n počet proměnných Hana Rudová, Omezující podmínky, 23. září 201 9 16 Hranová konzistence Složitost AC-1 proceduře AC-l(G) repeat Changed := false for V hranu (í,j) g G do Changed := revise((í,j)) or Changed until not(Changed) end AC-1 k maximální velikost domény, e počet hran, n počet proměnných Složitost 0(enk3) Hana Rudová, Omezující podmínky, 23. září 201 9 16 Hranová konzistence Složitost AC-1 proceduře AC-l(G) repeat Changed := false for V hranu (í,j) g G do Changed := revi se((í, j)) or Changed until not(Changed) end AC-1 3 k maximální velikost domény, e počet hran, n počet proměnných 3 Složitost 0(enk3) 3 cyklus přes všechny hrany 0(e) Hana Rudová, Omezující podmínky, 23. září 201 9 16 Hranová konzistence Složitost AC-1 proceduře AC-l(G) repeat Changed := false for V hranu (í,j) g G do Changed := revi se((í, j)) or Changed until not(Changed) end AC-1 k maximální velikost domény, e počet hran, n počet proměnných Složitost 0(enk3) M cyklus přes všechny hrany 0(e) M revi se 0(k2) Hana Rudová, Omezující podmínky, 23. září 201 9 16 Hranová konzistence Složitost AC-1 procedure AC-l(G) repeat Changed := false for V hranu (i,j) e G do Changed := revi se((i, j)) or Changed until not(Changed) end AC-1 k maximální velikost domény, e počet hran, n počet proměnných Složitost 0(enk3) M cyklus přes všechny hrany O(e) M revi se 0(k2) 3 jeden cyklus smaže (v nejhorším případě) právě jednu hodnotu z domény proměnné, celkem nk hodnot (každá proměnná má v doméně až k hodnot) => O(nk) Hana Rudová, Omezující podmínky, 23. září 2019 16 Hranová konzistence Neefektivita AC-1 I když zmenšíme jedinou doménu, provádí se revize všech hran. Tyto hrany ale revizí nemusí být vůbec zasaženy. Jaké hrany tedy revidovat po zmenšení domény? Hana Rudová, Omezující podmínky, 23. září 201 9 17 Hranová konzistence Neefektivita AC-1 I když zmenšíme jedinou doménu, provádí se revize všech hran. Tyto hrany ale revizí nemusí být vůbec zasaženy. Jaké hrany tedy revidovat po zmenšení domény? ty, jejichž konzistence může být zmenšením domény proměnné narušena jsou to hrany (í, k), které vedou do proměnné Vk se zmenšenou doménou ti'V (k,m) Vk ... proměnná se zmenšenou doménou (i2,k) (m,k) při revizi (k,m) došlo ke zmenšení domény Vk hranu (m, k) vedoucí z proměnné Vm, která zmenšení domény způsobila, není třeba revidovat (změna sejí nedotkne) Hana Rudová, Omezující podmínky, 23. září 201 9 17 Hranová konzistence Neefektivita AC-1 I když zmenšíme jedinou doménu, provádí se revize všech hran. Tyto hrany ale revizí nemusí být vůbec zasaženy. Jaké hrany tedy revidovat po zmenšení domény? ty, jejichž konzistence může být zmenšením domény proměnné narušena jsou to hrany (í, k), které vedou do proměnné Vk se zmenšenou doménou ti'V (k,m) Vk ... proměnná se zmenšenou doménou (i2,k) (m,k) při revizi (k,m) došlo ke zmenšení domény Vk 3 hranu (m, k) vedoucí z proměnné Vm, která zmenšení domény způsobila, není třeba revidovat (změna sejí nedotkne) M příklad: Vk < Vm, Vk in 1 ..1 0, Vm in 2..11, smazání 11 z Vm, tj. Vk in 1 ..1 0, Vm in 2..1 0, důsledek: doména Vk se změní, smaže se 1 0, tj. Vk in 1 ..9, Vm in 2..1 0, a teď reaguji na změnu Vk revizemi (Ví, Vk)'. je tedy zbytečné dělat revizi (Vm, Vk) Hana Rudová, Omezující podmínky, 23. září 2019 17 Hranová konzistence Algoritmus AC-3 Opakování revizí můžeme dělat pomocí fronty 3 stačí jediná fronta hran, které je potřeba (znova) zrevidovat 3 přidáváme tam jen hrany, jejichž konzistence mohla být narušena zmenšením domény V V m Rudová, Omezující podmínky, 23. září 201 9 18 Hranová konzistence Algoritmus AC-3 Opakování revizí můžeme dělat pomocí fronty 3 stačí jediná fronta hran, které je potřeba (znova) zrevidovat přidáváme tam jen hrany, jejichž konzistence mohla být narušena zmenšením domény V procedure AC-3(G) Q := {(í,j) I (í,j) g hrany(G), i ± j] while Q non empty do vyber a smaž (fc,m) z Q if revise((fc,m)) then Q := Q u {(í, k) e hrany(G), i ± k, i ± m} end while end AC-3 V m % seznam hran pro revizi % přidání pouze hran, které % dosud nejsou ve frontě Hana Rudová, Omezující podmínky, 23. září 201 9 18 Hranová konzistence Algoritmus AC-3 Opakování revizí můžeme dělat pomocí fronty 3 stačí jediná fronta hran, které je potřeba (znova) zrevidovat přidáváme tam jen hrany, jejichž konzistence mohla být narušena zmenšením domény V V m procedure AC-3(G) Q := {(í,j) I (í,j) g hrany(G), i ± j] while Q non empty do vyber a smaž (fc,m) z Q if revise((fc,m)) then Q := Q u {(í, k) g hrany(G), i ± k, i ± m} end while . _ ^ „ ©á^ O (k) 3 jakmile je omezení přidáno do fronty, doména (fc) jedné z jeho dvou proměnných (2) byla redukována alespoň o jednu hodnotu 3 Technika AC-3 je dnes asi nejpoužívánější, ale stále není optimální Hana Rudová, Omezující podmínky, 23. září 201 9 19 Hranová konzistence Podpora hodnoty 3 AC-3: při každé revizi hrany testujeme množství dvojic hodnot na konzistenci vzhledem k podmínce. Tyto testy znova opakujeme při každé další revizi hrany. Hana Rudová, Omezující podmínky, 23. září 201 9 20 Hranová konzistence Podpora hodnoty 3 AC-3: při každé revizi hrany testujeme množství dvojic hodnot na konzistenci vzhledem k podmínce. Tyto testy znova opakujeme při každé další revizi hrany. a - -.a VI — i i | b ■v. ^ —n*"**^ -1 — -b C ' ___-*C" . i i i i. cľ z^Z-__----- Ví V 2 v Hana Rudová, Omezující podmínky, 23. září 201 9 20 Hranová konzistence Podpora 3 AC-3: při každé revizi hrany testujeme vzhledem k podmínce. Tyto testy znova opakujeme při každé M Při revizi hrany (V2,Vi) vyřadíme hodnotu z domény proměnné V2. M Nyní musíme prozkoumat doménu V3, zda některá z hodnot a, b, c, d neztratila svoji podporu ve V2. hodnoty množství dvojic hodnot na konzistenci další revizi hrany. Hana Rudová, Omezující podmínky, 23. září 201 9 20 Hranová konzistence Podpora hodnoty AC-3: při každé revizi hrany testujeme množství dvojic hodnot na konzistenci vzhledem k podmínce. Tyto testy znova opakujeme při každé další revizi hrany. 3 Při revizi hrany (V2,Vi) vyřadíme hodnotu a z domény proměnné V2. M Nyní musíme prozkoumat doménu V3, zda některá z hodnot a, b, c, d neztratila svoji podporu ve V2. Hodnoty a, b, c není třeba znova kontrolovat <= mají ve V2 také jinou podporu než a. Hana Rudová, Omezující podmínky, 23. září 201 9 20 Hranová konzistence Podpora hodnoty AC-3: při každé revizi hrany testujeme množství dvojic hodnot na konzistenci vzhledem k podmínce. Tyto testy znova opakujeme při každé další revizi hrany. 3 Při revizi hrany (V2,Vi) vyřadíme hodnotu a z domény proměnné V2. M Nyní musíme prozkoumat doménu V3, zda některá z hodnot a, b, c, d neztratila svoji podporu ve V2. M Hodnoty a, b, c není třeba znova kontrolovat <= mají ve V2 také jinou podporu než a. Podpora (support) pro a e Di = {(j,b) \ b e D j, (a, b) e Cíj} M a e D2 má podpory {(3, a), (3, b), (3, d)} M d e d3 má pouze jedinou podporu {{2, a)} M b g D2 má podpory {(1,a), (1, c), (3, a), (3, c)} Podpory spočítáme jen jednou. Při opakovaných revizích je budeme používat. Hana Rudová, Omezující podmínky, 23. září 2019 20 Hranová konzistence Algoritmus na inicializaci podpor & Udržujeme seznam hodnot, které sami podporujeme (víme komu říct, když zmizíme). S j y. množina dvojic (í, a), pro které je (j,b) podporou Udržujeme počet vlastních podpor (víme, co nám chybí). counter[(í, j), a]: počet podpor, které má hodnota a e Di u proměnné V j procedure initial i ze (G) Q := {}, S := {} // vyprázdněni datových struktur for each (Ví, V)) e h rany (G) do for each a e Di do total := 0 for each b e D j do if (a,b) konzistentní' vzhledem k aj then total := total+1 Sj,fc := Sjtb u {{í,a)} counter [(í, j), a] := total if counter[(í,j),a] = 0 then smaž a z Di Q := Q u i(í,a)} return Q // Q je fronta se smazanými hodnotami Hana Rudová, Omezující podmínky, 23. září 2019 21 Hranová konzistence Aktualizace podpor během výpočtu Situace po zpracování hrany (Ví, V}) algoritmem initialize counter^ j} 2 2 1 ; Sj,_ , -b3 , Hana Rudová, Omezující podmínky, 23. září 201 9 22 Hranová konzistence Aktualizace podpor během výpočtu Situace po zpracování hrany (Ví, V}) algoritmem initialize counter^ j} 2 2 1 ; Sj,_ , -b3 , Využití struktur s podporami: 1. Předpokládejme, že b3 je vyřazena z domény V). 2. Zjistíme v S j #3, pro které hodnoty je b3 podporou (tj. (í, a2), (í, a3>). 3. Snížíme counter u těchto hodnot (odstraníme jim jednu podporu). 4. Pokud je některý counter vynulován (a3), potom příslušnou hodnotu vyřadíme z domény a pokračujeme s ní od kroku (1). counter(j $ i 2 a1 — 1 a2= 0 j b1 , b2 í<^a3> __J Hana Rudová, Omezující podmínky, 23. září 201 9 22 Hranová konzistence Algoritmus AC-4 proceduře AC-4(G) Q := i nitialize(G) while not empty(Q) do vyber a smaž libovolný (j,b) gQ for each (í, a) e Sjtb do counter[(í,j),a] : = counter[(í,j),a] - 1 if (counter[(í,j),a] = 0) a (a e D{) then smaž a z Di Q := Q u {<í,a>} Hana Rudová, Omezující podmínky, 23. září 201 9 23 Hranová konzistence Algoritmus AC-4 procedure AC-4(G) Q := initialize (G) while not empty(Q) do vyber a smaž libovolný {j,b) gQ for each {í,a) e Sjtb do counter [(í, j), a] := counter [(í, j), a] - 1 if (counter [(í, j), a] = 0) a (a e D ť) then smaž a z Di Q := Q u i(í,a)} 3 Složitost 0(ek2) => algoritmus optimální v nejhorším případě M složitost i ni ti al i ze Hana Rudová, Omezující podmínky, 23. září 201 9 23 Hranová konzistence Algoritmus AC-4 procedure AC-4(G) Q := i nitialize(G) while not empty(Q) do vyber a smaž libovolný (j,b) gQ for each (í, a) e Sjtb do counter[(í,j),a] : = counter[(í,j),a] - 1 if (counter[(í,j),a] = 0) a (a e D{) then smaž a z Di Q := Q u {<í,a>} Složitost 0(ek2) =^> algoritmus optimální v nejhorším případě složitost initialize 0(ek2) <= (Ví, V}) g hrany(G), a g Dif b g Dj složitost while cyklu Hana Rudová, Omezující podmínky, 23. září 201 9 23 Hranová konzistence Algoritmus AC-4 proceduře AC-4(G) Q := i nitialize(G) while not empty(Q) do vyber a smaž libovolný (j,b) gQ for each (í, a) e Sjtb do counter[(í,j),a] : = counter[(í,j),a] - 1 if (counter[(í,j),a] = 0) a (a e D{) then smaž a z Di Q := Q u {<í,a>} Složitost 0(ek2) =^> algoritmus optimální v nejhorším případě složitost initialize 0(ek2) <= (Ví, V}) g hrany(G), a g Dif b g Dj složitost while cyklu 0(ek2): postupně musím odebrat všechny podpory a těch je 0(ek2) Hana Rudová, Omezující podmínky, 23. září 201 9 23 Hranová konzistence Algoritmus AC-4 procedure AC-4(G) Q := i nitialize(G) while not empty(Q) do vyber a smaž libovolný (j,b) gQ for each (í, a) e Sjtb do counter[(í,j),a] : = counter[(í,j),a] - 1 if (counter[(í,j),a] = 0) a (a e D{) then smaž a z Di Q := Q u {<í,a>} Složitost 0(ek2) =^> algoritmus optimální v nejhorším případě složitost initialize 0(ek2) <= (Ví, V}) g hrany(G), a g Dif b g Dj složitost while cyklu 0(ek2): postupně musím odebrat všechny podpory a těch je 0(ek2) 3 Paměťová náročnost, není nejlepší v průměrném případě (inicializace zůstává) Hana Rudová, Omezující podmínky, 23. září 201 9 23 Hranová konzistence Další AC algoritmy Existuje řada dalších algoritmů pro zajištění hranové konzistence 3 AC-5, AC-6, AC-7, ... m AC-6 (Bessiěre, Cordier) 3 zlepšuje paměťovou náročnost a průměrný čas AC-4 drží si pouze jednu podporu, další podpory hledá až při ztrátě aktuální podpory m AC-3.1: AC-3 hledá podpory vždy od začátku, jak to vylepšit? AC-2001: AC-3 s frontou proměnných místo fronty omezení Porovnání: «• AC-3 není (teoreticky) optimální AC-4 je (teoreticky) optimální, ale (prakticky) pomalý AC-6/7 jsou (prakticky) rychlejší než AC-4, ale složité 3 AC-2001: v praxi je časté využití fronty proměnných Hana Rudová, Omezující podmínky, 23. září 2019 24 Hranová konzistence AC-3.1: optimální algoritmus AC-3 3 Co je na AC-3 neefektivní? hledání podpor v REVISE, které vždy začíná od nuly! if „neexistuje y e D j takové, že (x, y) je konzistentní" then AC-3.1 (Zhang, Yap) M běh stejný jako u AC-3 pro každou hodnotu si pamatuje poslední nalezenou podporu (last) v každém směru a hledání začíná u ní proceduře EXIST((i,x),j) y := last{{í,x),j) if y G Dj then return true while y := next(y,Dj) a y ± níl do i f (x, y) e a j then % aj omezeni s proměnými í, j last{{í,x),j) := y return true return false Hana Rudová, Omezující podmínky, 23. září 2019 25 Hranová konzistence AC-2001: jiný optimální algoritmus AC-3 procedure AC-2001(G) Používá verzi AC-3 s frontou proměnných Q := {í\ í e vrcholy (G)} % seznam vrcholů pro revizi while neprazdna(Q) do vyber a smaž j z Q for Ví g vrcholy (G) takové, že (í, j) e hrany (G) do if REVISE2001 (í,j) then if Di = 0 then return fail Q := Q u {í} return true Hana Rudová, Omezující podmínky, 23. září 201 9 26 Hranová konzistence AC-2001: jiný optimální algoritmus AC-3 procedure AC-2001(g) Používá verzi AC-3 s frontou proměnných Q := {í\ í e vrcholy (G)} % seznam vrcholů pro revizi while neprazdna(Q) do vyber a smaž j z Q for Ví g vrcholy (G) takové, že (í, j) e hrany (G) do if REVISE2001 (í,j) then if Di = 0 then return fail Q := Q u {í} return true procedure REVISE2001 (í, j) DELETED := false for Vx e Di do if last((í,x),j) é D j then Algoritmus fakticky pracuje s rozdílovými množinami, tj. pro každou proměnnou si pamatuje, jaké hodnoty byly smazány z domény od poslední revize (podobně jako AC-3.1) if 3y eDj a y > last((í,x)J) a (x,y) e a then last((í,x), j) := y else smaž x z Dů DELETED := true return DELETED Hana Rudová, Omezující podmínky, 23. září 201 9 26 Hranová konzistence Je hranová konzistence dostatečná (úplná)? Použitím AC odstraníme mnoho nekompatibilních hodnot 3 Dostaneme potom řešení problému? NE M Víme alespoň zda řešení existuje? NE Hana Rudová, Omezující podmínky, 23. září 201 9 27 Hranová konzistence Je hranová konzistence dostatečná (úplná)? Použitím AC odstraníme mnoho nekompatibilních hodnot 3 Dostaneme potom řešení problému? NE M Víme alespoň zda řešení existuje? NE 3 X,Y,Z e {1,2}, X+Y, Y + Z, Z + X M hranově konzistentní M nemá žádné řešení Hana Rudová, Omezující podmínky, 23. září 201 9 27 Hranová konzistence Je hranová konzistence dostatečná (úplná)? Použitím AC odstraníme mnoho nekompatibilních hodnot 3 Dostaneme potom řešení problému? NE M Víme alespoň zda řešení existuje? NE 3 X,Y,Z e {1,2}, X+Y, Y + Z, Z + X M hranově konzistentní M nemá žádné řešení Jaký je tedy význam AC? 3 někdy dá řešení přímo i* nějaká doména se vyprázdní => řešení neexistuje všechny domény jsou jednoprvkové => máme řešení M v obecném případě se alespoň zmenší prohledávaný prostor Hana Rudová, Omezující podmínky, 23. září 201 9 27 Hranová konzistence Konzistence po cestě Konzistence po cestě (PC path consistency) m Příklad: X, Y, Z e {1,2}, X ± Y, Y + Z, Z + X m Jak posílit konzistenci? Budeme se zabývat několika podmínkami najednou. Cesta (Vo, Vi,..., Vm) je konzistentní právě tehdy, když pro každou dvojici hodnot x e Do a y e Dm splňující binární podmínky na hraně Vo, Vm existuje ohodnocení proměnných Ví,... Vm-i takové, že všechny binární podmínky mezi sousedy Vj, yJ+i jsou splněny. CSP je konzistentní po cestě, právě když jsou všechny cesty konzistentní. Hana Rudová, Omezující podmínky, 23. září 201 9 29 Konzistence po cestě Konzistence po cestě (PC path consistency) m Příklad: X,Y,Z e {1,2}, X ± Y, Y ±Z, Z±X m Jak posílit konzistenci? Budeme se zabývat několika podmínkami najednou. Cesta (Vo, Vi,..., Vm) je konzistentní právě tehdy, když pro každou dvojici hodnot x e Do a y e Dm splňující binární podmínky na hraně Vo, Vm existuje ohodnocení proměnných Ví,... Vm-i takové, že všechny binární podmínky mezi sousedy Vj, yJ+i jsou splněny. CSP je konzistentní po cestě, právě když jsou všechny cesty konzistentní. Definice PC nezaručuje, že jsou splněny všechny podmínky nad vrcholy cesty, zabývá se pouze podmínkami mezi sousedy l Hana Rudová, Omezující podmínky, 23. září 201 9 29 Konzistence po cestě PC a cesty délky 2 3 Zjišťování konzistence všech cest není efektivní Stačí ověřit konzistenci cest délky 2 Věta: CSPje PC právě tehdy, když každá cesta délky 2 je PC. Hana Rudová, Omezující podmínky, 23. září 201 9 30 Konzistence po cestě PC a cesty délky 2 3 Zjišťování konzistence všech cest není efektivní Stačí ověřit konzistenci cest délky 2 Věta: CSPje PC právě tehdy, když každá cesta délky 2 je PC. Důkaz: 1) PC => cesty délky 2 jsou PC 2) cesty délky 2 jsou PC => V n cesty délky n jsou PC => PC indukcí podle délky cesty a) n = 2 platí triviálně b) n + 1 (za předpokladu, že platí pro n) i) vezmeme libovolných n+ 2 vrcholů Vo, V\,..., Vn+\ ii) vezmeme libovolné dvě kompatibilní hodnoty xq g Do a xn+\ e D (kompatibilní = splňující všechny bin.podmínky mezi Xo a xn+\) iii) podle a) jsou všechny cesty délky 2 PC, a tedy i Vo, Vn, Vn+\ je PC najdeme tedy xn e Dn tak, že (xo,xn) a (xn, xn+\) jsou konzistentní iv) podle indukčního kroku najdeme zbylé hodnoty na cestě Vo,Vi,...,V1 Hana Rudová, Omezující podmínky, 23. září 201 9 30 Konzistence po cestě PC a cesty délky 2 3 Zjišťování konzistence všech cest není efektivní 3 Stačí ověřit konzistenci cest délky 2 Věta: CSPje 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 => V n cesty délky n jsou PC => PC indukcí podle délky cesty a) n = 2 platí triviálně b) n + 1 (za předpokladu, že platí pro n) i) vezmeme libovolných n+ 2 vrcholů Vo, V\,..., Vn+\ ii) vezmeme libovolné dvě kompatibilní hodnoty xq e Do a xn+\ e D (kompatibilní = splňující všechny bin.podmínky mezi Xo a xn+\) iii) podle a) jsou všechny cesty délky 2 PC, a tedy i Vo, Vn, Vn+\ je PC najdeme tedy xn e Dn tak, že (xo,xn) a (xn, xn+\) jsou konzistentní iv) podle indukčního kroku najdeme zbylé hodnoty na cestě Vo,V\,...,Vn 3 Definici PC lze tedy upravit tak, že vyžadujeme pouze konzistenci cest délky 2 Hana Rudová, Omezující podmínky, 23. září 2019 30 Konzistence po cestě Vztah PC a AC PC => AC pokud je cesta (í, j, i) konzistentní (PC), pak je i hrana (í, j) konzistentní (AC), tj. z PC tedy plyne AC PC: ke každé „dvojici hodnot" pro í, i najdu hodnotu v j => AC: ke každé hodnotě v i tedy najdu hodnotu v j Hana Rudová, Omezující podmínky, 23. září 201 9 31 Konzistence po cestě Vztah PC a AC PC => AC -» pokud je cesta (í,j,í) konzistentní (PC), pak je i hrana (i, j) konzistentní (AC), tj. z PC tedy plyne AC S> PC: ke každé „dvojici hodnot" pro i, i najdu hodnotu v j => AC: ke každé hodnotě v i tedy najdu hodnotu v j ^ AC ^ PC M příklad: X,Y, Z e {1,2}, X^Y, Y^Z, Z^X je AC, ale není PC, X=0, Y=l nelze rozšířit po cestě (X,Z,Y) Hana Rudová, Omezující podmínky, 23. září 201 9 31 Konzistence po cestě Vztah PC a AC PC => AC M pokud je cesta (í,j,í) konzistentní (PC), pak je i hrana (í, j) konzistentní (AC), tj. z PC tedy plyne AC 3 PC: ke každé „dvojici hodnot" pro í, i najdu hodnotu v j => AC: ke každé hodnotě v i tedy najdu hodnotu v j m AC 4> PC 3 příklad: X,Y, Z e {1,2}, X^Y, Y^Z, Z^X ^ je AC, ale není PC, X=0, Y=l nelze rozšířit po cestě (X,Z,Y) AC vyřazuje nekompatibilní prvky z domény proměnných. Co dělá PC? 3 PC vyřazuje dvojice hodnot PC si pamatuje podmínky explicitně PC si pamatuje, které dvojice hodnot jsou v relaci 3 PC dělá všechny relace nad dvojicemi implicitní (A A+1