Algoritmy pro CSP (pokračování) Řešení nebinárních podmínek k-konzistence má exponenciální složitost, v reálu se nepoužívá S n-árními podmínkami se pracuje přímo M Podmínka je obecně hranově konzistentní (GAC), právě když pro každou proměnnou Ví z této podmínky a každou hodnou x e Di existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí M A + B #= C, A in 1..3, B in 2..4, C in 3.. 7 je obecně hranově konzistentní Hana Rudová, Logické programování I, 30. dubna 201 3 2 Algoritmy pro CSP Řešení nebinárních podmínek k-konzistence má exponenciální složitost, v reálu se nepoužívá S n-árními podmínkami se pracuje přímo M Podmínka je obecně hranově konzistentní (GAC), právě když pro každou proměnnou Ví z této podmínky a každou hodnou x e Di existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí M A + B #= C, A in 1..3, B in 2..4, C in 3.. 7 je obecně hranově konzistentní M Využívá se sémantika podmínek speciální typy konzistence pro globální omezení ± viz all_di stinct 3 konzistence mezí propagace pouze při změně nejmenší a největší hodnoty v doméně proměnné Pro různé podmínky lze použít různý druh konzistence 3 A# B => min(A) = min(B)+l, max(B) = max(A)-l 3 příklad: A in 4.. 10, B in 6.. 18, A #> B mi n (A) = 6+1 => A in 7.. 10 max(B) = 10-1 => B in 6. .9 Hana Rudová, Logické programování I, 30. dubna 201 3 4 Algoritmy pro CSP Konzistence mezí Bounds consistency BC: slabší než obecná hranová konzistence 3 podmínka má konzistentní meze (BC), právě když pro každou proměnnou Vj z této podmínky a každou hodnou x e D j existuje ohodnocení zbylých proměnných v podmínce tak, že je podmínka splněna a pro vybrané ohodnocení yi proměnné Ví platí min(Di) < yi< max(Di) M stačí propagace pouze při změně minimální nebo maximální hodnoty (při změně mezí) v doméně proměnné M Konzistence mezí pro nerovnice S A #> B => min(A) = min(B)+l, max(B) = max(A)-l 3 příklad: A in 4.. 10, B in 6.. 18, A #> B mi n (A) = 6+1 => A in 7.. 10 max(B) = 10-1 => B in 6. .9 * podobně: A #< B, A #>= B, A #=< B Hana Rudová, Logické programování I, 30. dubna 201 3 4 Algoritmy pro CSP Konzistence mezí a aritmetická omezení M 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á, Logické programování I, 30. dubna 201 3 5 Algoritmy pro CSP Konzistence mezí a aritmetická omezení M A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = mi n(A)-max(C), max(B) = max(A)-mi n(C) mi n(C) = mi n(A)-max(B), max(C) = max(A)-mi n(B) 3 změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) 3 změna max (A)vyvolá pouze změnu max(B) a max(C) , ... Hana Rudová, Logické programování I, 30. dubna 201 3 5 Algoritmy pro CSP Konzistence mezí a aritmetická omezení M A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = mi n(A)-max(C), max(B) = max(A)-mi n(C) mi n(C) = mi n(A)-max(B), max(C) = max(A)-mi n(B) 3 změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) 3 změna max (A)vyvolá pouze změnu max(B) a max(C) , ... 3 Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 => Hana Rudová, Logické programování I, 30. dubna 201 3 5 Algoritmy pro CSP Konzistence mezí a aritmetická omezení M 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) 3 změna mi n(A)vyvolá pouze změnu mi n(B) amin(C) 3 změna max(A)vyvolá pouze změnu max(B) a max(C) , ... 3 Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 => min(A)=l+2, max(A)=10+2 => A in 3. . 10 => min(B)=l-2, max(B)=10-2 => B in 1..8 Hana Rudová, Logické programování I, 30. dubna 201 3 5 Algoritmy pro CSP Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = mi n(A)-max(C), max(B) = max(A)-mi n(C) mi n(C) = mi n(A)-max(B), max(C) = max(A)-mi n(B) 3 změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) 3 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)=l+2, max(A)=10+2 => A in 3. . 10 => min(B)=l-2, max(B)=10-2 => B in 1..8 A #> 5 => min(A)=6 => A in 6..10 => mi n (B) =6-2 ^> B in 4.. 8 (nové vyvolání A #= B + 2) Hana Rudová, Logické programování I, 30. dubna 201 3 5 Algoritmy pro CSP Konzistence mezí a aritmetická omezení M A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = mi n(A)-max(C), max(B) = max(A)-mi n(C) mi n(C) = mi n(A)-max(B), max(C) = max(A)-mi n(B) 3 změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) 3 změna max (A)vyvolá pouze změnu max(B) a max(C) , ... 3 Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 => min(A)=l+2, max(A)=10+2 => A in 3. . 10 => min(B)=l-2, max(B)=10-2 => B in 1..8 A #> 5 => min(A)=6 => A in 6..10 ^> mi n (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á, Logické programování I, 30. dubna 201 3 5 Algoritmy pro CSP Konzistence mezí a aritmetická omezení M 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) 3 změna mi n(A)vyvolá pouze změnu mi n(B) amin(C) 3 změna max(A)vyvolá pouze změnu max(B) a max(C) , ... 3 Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 => min(A)=l+2, max(A)=10+2 => A in 3. . 10 => min(B)=l-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) 3 Vyzkoušejte si: A #= B - C, A #>= B + C Hana Rudová, Logické programování I, 30. dubna 201 3 5 Algoritmy pro CSP Globální podmínky M Propagace je lokální M pracuje se s jednotlivými podmínkami 3 interakce mezi podmínkami je pouze přes domény proměnných M Jak dosáhnout více, když je silnější propagace drahá? M Seskupíme několik podmínek do jedné tzv. globální podmínky Propagaci přes globální podmínku řešíme speciálním algoritmem navrženým pro danou podmínku M Příklady: M all_di stinct omezení: hodnoty všech proměnných různé 3 serialized omezení: rozvržení úloh zadaných startovním časem a dobou trvání tak, aby se nepřekrývaly Hana Rudová, Logické programování I, 30. dubna 201 3 6 Algoritmy pro CSP Propagace pro al l_di sti nct M U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 30. dubna 201 3 7 Algoritmy pro CSP Propagace pro al l_di sti nct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 30. dubna 201 3 7 Algoritmy pro CSP Propagace pro al l_di sti nct M U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) M Konzistence: V{Xi,... ,Xk} c V : card{Di u ■ ■ ■ u Dk} > k učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 30. dubna 201 3 7 Algoritmy pro CSP Propagace pro al l_di sti nct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max {2,3,4} nelze pro XI, X3, X6 Jan 3 6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) Petr 4 Konzistence: V{Xi,... ,Xk} c V : card{Di u ■ ■ ■ u D^} > k Anna 2 5 stačí hledat Hallúv interval I: velikost intervalu / je rovna Ota 4 počtu proměnných, jejichž doména je v / Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 30. dubna 201 3 7 Algoritmy pro CSP Propagace pro al l_di sti nct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: V{Xi,... ,Xk} c V : card{Di u ■ ■ ■ u Dk} > k stačí hledat Hallúv interval I: velikost intervalu / je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo M U = {Xi.....Xfe}, dom(U) = {Dľ u ■ ■ ■ u Dk} učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 card(U) = card(dom(U)) => Vv g dom(U), VX g (V - U),X ± v Hana Rudová, Logické programování I, 30. dubna 201 3 7 Algoritmy pro CSP Propagace pro al l_di sti nct M U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) M Konzistence: V{Xi,... ,Xk} c V : card{Di u ■ ■ ■ u Dk} > k stačí hledat Hallúv interval I: velikost intervalu / je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo M U = {Xi.....Xfe}, dom(U) = {Dľ u ■ ■ ■ u Dk} M card(U) = card(dom(U)) => Vv e dom(U), VX e (V - U),X + v 3 hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 30. dubna 201 3 7 Algoritmy pro CSP Propagace pro al l_di sti nct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: V{Xi,... ,Xk} c V : card{Di u ■ ■ ■ u Dk} > k stačí hledat Hallúv interval I: velikost intervalu / je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo M U = {Xi.....Xfe}, dom(U) = {Dľ u ■ ■ ■ u Dk} M card(U) = card(dom(U)) => Vv e dom(U), VX e (V - U),X + v 3 hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Složitost: 0(2n) - hledání všech podmnožin množiny n proměnných (naivní) Hana Rudová, Logické programování I, 30. dubna 201 3 7 Algoritmy pro CSP Propagace pro al l_di sti nct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: V{Xi,... ,Xk} c V : card{Di u ■ ■ ■ u Dk} > k stačí hledat Hallúv interval I: velikost intervalu / je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo M U = {Xi.....Xfe}, dom(U) = {Dľ u ■ ■ ■ u Dk} M card(U) = card(dom(U)) => Vv e dom(U), VX e (V - U),X + v 3 hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné Složitost: 0(2n) - hledání všech podmnožin množiny n proměnných (naivní) O(nlogn) - kontrola hraničních bodů Hallových intervalů (1998) učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 30. dubna 201 3 Algoritmy pro CSP Prohledávání + konzistence M Splňování podmínek prohledáváním prostoru řešení M podmínky jsou užívány pasivně jako test M přiřazuji hodnoty proměnných a zkouším co se stane * vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj Hana Rudová, Logické programování I, 30. dubna 201 3 8 Algoritmy pro CSP Prohledávání + konzistence M Splňování podmínek prohledáváním prostoru řešení M podmínky jsou užívány pasivně jako test M přiřazuji hodnoty proměnných a zkouším co se stane 3 vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj 3 úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) M zbytečně pomalé (exponenciální): procházím i „evidentně" špatná ohodnocení Hana Rudová, Logické programování I, 30. dubna 201 3 8 Algoritmy pro CSP Prohledávání + konzistence M Splňování podmínek prohledáváním prostoru řešení M podmínky jsou užívány pasivně jako test M přiřazuji hodnoty proměnných a zkouším co se stane M vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj 3 úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) M zbytečně pomalé (exponenciální): procházím i „evidentně" špatná ohodnocení Konzistenční (propagační) techniky 3 umožňují odstranění nekonzistentních hodnot z domény proměnných M neúplná metoda (v doméně zůstanou ještě nekonzistentní hodnoty) M relativně rychlé (polynomiální) Hana Rudová, Logické programování I, 30. dubna 201 3 8 Algoritmy pro CSP Prohledávání + konzistence M Splňování podmínek prohledáváním prostoru řešení M podmínky jsou užívány pasivně jako test M přiřazuji hodnoty proměnných a zkouším co se stane M vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj 3 úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) M zbytečně pomalé (exponenciální): procházím i „evidentně" špatná ohodnocení Konzistenční (propagační) techniky 3 umožňují odstranění nekonzistentních hodnot z domény proměnných M neúplná metoda (v doméně zůstanou ještě nekonzistentní hodnoty) M relativně rychlé (polynomiální) Používá se kombinace obou metod 3 postupné přiřazování hodnot proměnným M po přiřazení hodnoty odstranění nekonzistentních hodnot konzistenčními technikami Hana Rudová, Logické programování I, 30. dubna 201 3 8 Algoritmy pro CSP Prohledávání do hloubky M Základní prohledávací algoritmus pro problémy splňování podmínek Prohledávání stavového prostoru do hloubky (depth first search) M Dvě fáze prohledávání s navracením M dopředná fáze: proměnné jsou postupně vybírány, rozšiřuje se částečné řešení přiřazením konzistení hodnoty (pokud existuje) další proměnné & po vybrání hodnoty testujeme konzistenci M zpětná fáze: pokud neexistuje konzistentní hodnota pro aktuální proměnnou, algoritmus se vrací k předchozí přiřazené hodnotě Hana Rudová, Logické programování I, 30. dubna 201 3 9 Algoritmy pro CSP Prohledávání do hloubky M Základní prohledávací algoritmus pro problémy splňování podmínek Prohledávání stavového prostoru do hloubky (depth first search) M Dvě fáze prohledávání s navracením M dopředná fáze: proměnné jsou postupně vybírány, rozšiřuje se částečné řešení přiřazením konzistení hodnoty (pokud existuje) další proměnné 3 po vybrání hodnoty testujeme konzistenci M zpětná fáze: pokud neexistuje konzistentní hodnota pro aktuální proměnnou, algoritmus se vrací k předchozí přiřazené hodnotě M Proměnné dělíme na 3 minulé - proměnné, které už byly vybrány (a mají přiřazenu hodnotu) M aktuální - proměnná, která je právě vybrána a je jí přiřazována hodnota 3 budoucí - proměnné, které budou vybrány v budoucnosti Hana Rudová, Logické programování I, 30. dubna 201 3 9 Algoritmy pro CSP Základní algoritmus prohledávání do hloubky M Pro jednoduchost proměnné očíslujeme a ohodnocujeme je v daném pořadí Na začátku voláno jako 1 abel i ng (G, 1) proceduře labeling(G,a) if a > |uzly(G)| then return uzly(G) for Vx e Da do if consistent(G,a) then % consistent(G,a) je nahrazeno FC(G,a), LA(G,a), R := label ing(G,a + 1) if R ^ fail then return R return fail end labeling Po přiřazení všech proměnných vrátíme jejich ohodnocení M Procedury consistent uvedeme pouze pro binární podmínky Hana Rudová, Logické programování I, 30. dubna 201 3 10 Algoritmy pro CSP Backtracking (BT) M Backtracking ověřuje v každém kroku konzistenci podmínek vedoucích z minulých proměnných do aktuální proměnné M Backtracking tedy zajišťuje konzistenci podmínek & na všech minulých proměnných M na podmínkách mezi minulými proměnnými a aktuální proměnnou Hana Rudová, Logické programování I, 30. dubna 201 3 Algoritmy pro CSP Backtracking (BT) M Backtracking ověřuje v každém kroku konzistenci podmínek vedoucích z minulých proměnných do aktuální proměnné M Backtracking tedy zajišťuje konzistenci podmínek M na všech minulých proměnných M na podmínkách mezi minulými proměnnými a aktuální proměnnou 3 procedure BT(G,a) Q-={(Ví, V a) £ hrany(G) , í < a} % hrany vedoucí z minulých proměnných do aktuální Consistent := true while Q neni prázdná A Consistent do vyber a smaž libovolnou hranu (Vfe,Vm) z Q Consistent := not revise(Vk,Vm) % pokud vyřadíme prvek, bude doména prázdná return Consistent end BT Hana Rudová, Logické programování I, 30. dubna 201 3 Algoritmy pro CSP Příklad: backtracking 3 červené čtverečky: chybný pokus o instanciaci, řešení neexistuje 3 nevyplněná kolečka: nalezeno řešení 3 černá kolečka: vnitřní uzel, máme pouze částečné přiřazení Hana Rudová, Logické programování I, 30. dubna 2013 12 Algoritmy pro CSP Kontrola dopředu (FC - forward checking) M FC je rozšíření backtrackingu FC navíc zajišťuje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami Hana Rudová, Logické programování I, 30. dubna 201 3 Algoritmy pro CSP Kontrola dopředu (FC - forward checking) M FC je rozšíření backtrackingu FC navíc zajišťuje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami M procedure FC(G,a) Q-={(Ví, V a) £ hrany(G) , í > a} % přidání hran z budoucích do aktuální proměnné Consistent := true while Q neni prázdná A Consistent do vyber a smaž libovolnou hranu (Vfe,Vm) z Q if revise((Vfc,Vm)) then Consistent := (\Dk\ > 0) % vyprázdnění domény znamená nekonzistenci return Consistent end FC Hrany z minulých proměnných do aktuální proměnné není nutno testovat Hana Rudová, Logické programování I, 30. dubna 201 3 Algoritmy pro CSP Příklad: kontrola dopředu Omezení: Vi, V2, V3 in 1... 3, c : Vi# = 3 x V3 Stavový prostor: Hana Rudová, Logické programování I, 30. dubna 201 3 14 Algoritmy pro CSP Pohled dopředu (LA - looking ahead) M LA je rozšíření FC, navíc ověřuje konzistenci hran mezi budoucími proměnnými 3 proceduře LA(G,a) Q := {(VuVa) e hrany(G), í > a} % začínáme s hranami do a Consistent := true while Q neni prázdná A Consistent do vyber a smaž libovolnou hranu (Vfe,Vm) z Q if revise((Vfc,Vm)) then Q := Q u {(VuVk)\(Vi,Vk) e hrany(G), í^k,í^m,í> a} Consistent := (|Dfe| > 0) return Consistent end LA Hana Rudová, Logické programování I, 30. dubna 201 3 Algoritmy pro CSP Pohled dopředu (LA - looking ahead) M LA je rozšíření FC, navíc ověřuje konzistenci hran mezi budoucími proměnnými 3 procedure LA(G,a) Q := {(VuVa) g hrany(G), í > a} % začínáme s hranami do a Consistent := true while Q neni prázdná A Consistent do vyber a smaž libovolnou hranu (Vfe,Vm) z Q if revise((Vfc,Vm)) then Q := Q u {(Ví, V*) I (Ví, Vjk) e hrany(G), i ŕ k, i ŕ m,í > a} Consistent := (|Dfc| > 0) return Consistent end LA M Hrany z minulých proměnných do aktuální proměnné opět netestujeme 3 Tato LA procedura je založena na AC-3, lze použít i jiné AC algoritmy M LA udržuje hranovou konzistenci: protože ale LA(G,a) používá AC-3, musíme zajistit iniciální konzistenci pomocí AC-3 ještě před startem prohledávání Hana Rudová, Logické programování I, 30. dubna 2013 15 Algoritmy pro CSP Příklad: pohled dopředu (pomocí AC-3) Omezení: V1.V2.V3 in 1...4, cl:Vi#>V2, c2 : V2# = 3 x V3 Stavový prostor (spouští se iniciální konzistence se před startem prohledávání) • c1 => V1 in 2..4 Y2in 1..3 c2 => V2=3 V3= 1 c1 => V1= 4 V< 4, V2 3, V3 1, Hana Rudová, Logické programování I, 30. dubna 201 3 16 Algoritmy pro CSP Přehled algoritmů Backtracking (BT) kontroluje v kroku a podmínky c(Vi,VJ,...,c(Va_i,Va) z minulých proměnných do aktuální proměnné proměnné 3"§. --~í =3 &) C N CD CD CD aktuálni ^ CD o =q-c a) o N ^ CD CD Hana Rudová, Logické programování I, 30. dubna 201 3 1 7 Algoritmy pro CSP Přehled algoritmů Backtracking (BT) kontroluje v kroku a podmínky c(Vi,VJ,...,c(Va_i,Va) z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky C(Va+l, Va),...,C(Vn,Va) a z budoucích proměnných do aktuální proměnné FC LA n Hana Rudová, Logické programování I, 30. dubna 201 3 Přehled algoritmů Backtracking (BT) kontroluje v kroku a podmínky c(Vi,VJ,...,c(Va_i,Va) z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky C(Va+l, Va),...,C(Vn,Va) z budoucích proměnných do aktuální proměnné Pohled dopředu (LA) kontroluje v kroku a podmínky Vř(a < l < n), Vfc(a < k < ri),k + l: c(Vk,Vi) z budoucích proměnných do aktuální proměnné LA a mezi budoucími proměnnými 1 j proměnné T \ 3 5. aktuálni Hana Rudová, Logické programování I, 30. dubna 201 3 1 7 Algoritmy pro CSP Cvičení 1. Jak vypadá stavový prostor řešení pro následující omezení A in 1 ..4, B in 3..4, C in 3..4, B #< C, A #= C při použití kontroly dopředu a uspořádání proměnných A,B,C? Popište, jaký typ propagace proběhne v jednotlivých uzlech. 2. Jak vypadá stavový prostor řešení pro následující omezení A in 1 ..4, B in 3..4, C in 3..4, B #< C, A #= C při použití pohledu dopředu a uspořádání proměnných A,B,C? Popište, jaký typ propagace proběhne v jednotlivých uzlech. 3. Jak vypadá stavový prostor řešení pro následující omezení domain([A,B,C],0,l), A#= B-l, C #= A*A při použití backtrackingu a pohledu dopředu a uspořádání proměnných A,B,C? Popište, jaký typ propagace proběhne v jednotlivých uzlech. Hana Rudová, Logické programování I, 30. dubna 2013 18 Algoritmy pro CSP Cvičení 1. Jaká jsou pravidla pro konzistenci mezí u omezení X#= Y+5? Jaké typy propagací pak proběhnou v následujícím příkladě při použití konzistence mezí? X in 1 ..20, Y in 1 ..20, X #= Y + 5, Y #> 1 0. 2. Ukažte, jak je dosaženo hranové konzistence v následujícím příkladu: domain([X,Y,Z],l ,5]), X #< Y, Z#= Y+l . Hana Rudová, Logické programování I, 30. dubna 201 3 19 Algoritmy pro CSP