Řešení nebinárních podmínek Algoritmy pro CSP (pokračování) 1 k-konzistence má exponenciální složitost, v reálu se nepoužívá 1 S n-árními podmínkami se pracuje přímo 1 Podmínka je obecně hranově konzistentní (CAC), právě když pro každou proměnnou Ví z této podmínky a každou hodnou xeDj existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí ■A + B #= C, A in 1..3, B in 2..4, C in 3..7je obecně hranově konzistentní 1 Využívá se sémantika podmínek ■ speciální typy konzistence pro globální omezení ■ viz al 1_di sti nct ■ konzistence mezí ■ propagace pouze při změně nejmenší a největší hodnoty v doméně proměnné 1 Pro různé podmínky lze použít různý druh konzistence ■ A# B=> min(A) = min(B)+l, max(B) = max(A)-l ■ 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 2013 4 Algoritmy pro CSP Konzistence mezí a aritmetická omezení Globální podmínky 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) amin(C) ■ změna max(A)vyvolá pouze změnu max(B) amax(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 => 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 ■ Propagace je lokální ■ pracuje se s jednotlivými podmínkami ■ interakce mezi podmínkami je pouze přes domény proměnných ■ Jak dosáhnout více, když je silnější propagace drahá? ■ 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 ■ Příklady: ■ a"l"l_distinct omezení: hodnoty všech proměnných různé ■ 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 2013 Algoritmy pro CSP Propagace pro all_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 J: velikost intervalu / je rovna počtu proměnných, jejichž doména je v J Inferenční pravidlo ■ U = {Xi,...,Xk}, dom(U) = {Di u ■ ■ ■ uDk] • card(U) = card(dom(U)) ^Vve dom(U), VX e (V - U),X ± v ■ hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné Složitost: 0(2") - hledání všech podmnožin množiny n proměnných (naivní) O(nlogn) - kontrola hraničních bodů Hallových intervalů (1 998) učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Hana Rudová, Logické programování I, 30. dubna 201 3 Algoritmy pro CSP Hana Rudová, Logické programování I, 30. dubna 201 3 Algoritmy pro CSP Prohledávání + konzistence Splňování podmínek prohledáváním prostoru řešení ■ podmínky jsou užívány pasivně jako test ■ přiřazuji hodnoty proměnných a zkouším co se stane ■ vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj ■ úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) ■ zbytečně pomalé (exponenciální): procházím i „evidentně" špatná ohodnocení Konzistenční (propagační) techniky ■ umožňují odstranění nekonzistentních hodnot z domény proměnných ■ neúplná metoda (v doméně zůstanou ještě nekonzistentní hodnoty) ■ relativně rychlé (polynomiální) Používá se kombinace obou metod ■ postupné přiřazování hodnot proměnný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 Algoritmy pro CSP Prohledávání do hloubky Základní algoritmus prohledávání do hloubky Základní prohledávací algoritmus pro problémy splňování podmínek Prohledávání stavového prostoru do hloubky (depth first search) Dvě fáze prohledávání s navracení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 ■ zpětná fáze: pokud neexistuje konzistentní hodnota pro aktuální proměnnou, algoritmus se vrací k předchozí přiřazené hodnotě Proměnné dělíme na ■ minulé - proměnné, které už byly vybrány (a mají přiřazenu hodnotu) ■ aktuální - proměnná, která je právě vybrána a je jí přiřazována hodnota ■ budoucí - proměnné, které budou vybrány v budoucnosti Hana Rudová, Logické programování I, 30. dubna 2013 9 Algoritmy pro CSP Backtracking (BT) Backtracking ověřuje v každém kroku konzistenci podmínek vedoucích z minulých proměnných do aktuální proměnné Backtracking tedy zajišťuje konzistenci podmínek ■ na všech minulých proměnných ■ na podmínkách mezi minulými proměnnými a aktuální proměnnou proceduře BT(G,a) Q:={(Ví, V a) e hrany(G) , i < a] % hrany vedoucí z minulých proměnných do aktuální Consistent := true while Q nem' prázdná a Consistent do vyber a smaž libovolnou hranu (Vk,Vm) z Q Consistent := not reviseiV^ Vm) % pokud vyřadíme prvek, bude doména prázdná return Consistent end BT Hana Rudová, Logické programování I, 30. dubna 2013 11 Algoritmy pro CSP ■ Pro jednoduchost proměnné očíslujeme a ohodnocujeme je v daném pořadí ■ Na začátku voláno jako 1 abel i ng (C, 1) procedure labeling(G,a) if a > |uzlyCC)| then return uzly(C) for V x 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 4= fail then return R return fail end labeling Po přiřazení všech proměnných vrátíme jejich ohodnocení ■ Procedury consistent uvedeme pouze pro binární podmínky Hana Rudová, Logické programování I, 30. dubna 2013 10 Algoritmy pro CSP Příklad: backtracking ■ červené čtverečky: chybný pokus o instanciaci, řešení neexistuje ■ nevyplněná kolečka: nalezeno řešení ■ č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) FCje 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 % přidání hran z budoucích do aktuální proměnné proceduře FC(G,a) Q-={(Ví,Va) ehrany(G), í> a\ Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (VJt,Vm) z Q if revi se((V(;, Vm)) then Consistent := (|Djt|>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 2013 Algoritmy pro CSP Pohled dopředu (LA - looking ahead) LAje rozšíření FC, navíc ověřuje konzistenci hran mezi budoucími proměnnými % začináme s hranami do a procedure LA(G,a) Q := {(VuVa) e h rany (C), í > a] Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (Vk,Vm) z Q if revi se((VJt, Vm)) then Q := Q u {(VuVk)\(VuVk) e hrany(G), í + k, í + m, í > a] Consistent := (\Dk\ > 0) return Consistent end LA ■ Hrany z minulých proměnných do aktuální proměnné opět netestujeme ■ Tato LA procedura je založena naAC-3, lze použít i jiné AC algoritmy 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 Algoritmy pro CSP Příklad: kontrola dopředu Omezení: Vu V2, V3 in 1... 3, c:V1#=3x V3 Stavový prostor: v2 v. c => fail Hana Rudová, Logické programování I, 30. dubna 201 3 1 4 Algoritmy pro CSP Příklad: pohled dopředu (pomocí AC-3) Omezení: V1,V2,V3 in 1...4, cl:V1#>V2, c2:V2#=3xV3 Stavový prostor (spouští se iniciální konzistence se před startem prohledávání) ^ d => V1 in 2..4 V2in 1..3 C2 => V2=3 V3= 1 d => V1= 4 Ví 41 V2 3, Vo 1j v3 o Hana Rudová, Logické programování I, 30. dubna 201 3 1 6 Algoritmy pro CSP Přehled algoritmů Cvičení proměnné BT Backtracking (BT) kontroluje v kroku a podmínky c(Vi,Vfl),...,c(Vfl-i,Vfl) z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky \^ c(V«+i,V«),...,c(V„,Vfl) z budoucích proměnných do aktuální proměnné Pohled dopředu (LA) kontroluje v kroku a podmínky ^ /I Vi(a < l < n), Vfe(a 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 Algoritmy pro CSP