Konzistence po cestě
Konzistence po cestě (PC path consistency)
3 Příklad: X,Y,Z e {1,2},   X ± Y,   Y + Z,   Z + X
3 Jak posílit konzistenci?     Budeme se zabývat několika podmínkami najednou.
Cesta (Vo, Vi,..., Vm) je konzistentní právě tehdy, když pro každou dvojici hodnot x e Do a y e Dm splňující binární podmínky na hraně Vo, Vm existuje ohodnocení proměnných Vi,... 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í.l
Definice PC nezaručuje, že jsou splněny všechny podmínky nad vrcholy cesty, zabývá se pouze podmínkami mezi sousedy
Hana Rudová, Omezující podmínky, 7. října 201 9
2
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 PCI
Důkaz: 1) PC => cesty délky 2 jsou PC
I
2) cesty délky 2 jsou PC => V n cesty délky n jsou PC => PC indukcí podle délky cesty
a) n = 2 platí triviálně
b) n + 1 (za předpokladu, že platí pro n)
i) vezmeme libovolných n+ 2 vrcholů Vo, V\,..., Vn+\
ii) vezmeme libov. dvě kompatibilní hodnoty xq g Do a xn+\ e Dn+i (kompatibilní = splňující všechny bin.podmínky mezi Xo a xn+\)
iii) podle a) jsou všechny cesty délky 2 PC, a tedy i Vo, Vn, Vn+\ je PC najdeme tedy xn e Dn tak, že (xo,xn) a (xn, xn+\) jsou konzistentní
iv) podle indukčního kroku najdeme zbylé hodnoty na cestě Vo, V\,..., Vni
M Definici PC lze tedy upravit tak, že vyžadujeme pouze konzistenci cest délky 21
Hana Rudová, Omezující podmínky, 7. října 2019 3 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 ji
M AC 4> PC
3 příklad: X,Y, Z e {1,2},   X^Y,   Y^Z,   Z^X 1
je AC, ale není PC, zdůvodnění: Í=0, Y=l nelze rozšířit po cestě (X,Z,Y)I
AC vyřazuje nekompatibilní prvky z domény proměnných. Co dělá PC?
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<B, B<C => A+1<C)
Hana Rudová, Omezující podmínky, 7. října 2019 4 Konzistence po cestě
Příklad: barvení grafu
Nalezněte obarvení vrcholů grafu tak, aby sousední vrcholy neměly stejnou barvu.
není PC konzistentní je PC konzistentní
lze přiřadit X\ = r,X-$ = b
Hana Rudová, Omezující podmínky, 7. října 201 9
5
Konzistence po cestě
Algoritmus revize cesty
Jak udělat každou cestu z Vi do V) přes Vm konzistentní?
M Pro dvojici proměnných Vi a Vj aktualizuji prvky relace Ríj
M Vyřadím dvojici {a, b) z R^, pokud neexistuje taková hodnota c e Vm, že (a, c) je kozistentní pro Rtm a {c, b) je kozistentní pro Rmj%
Ä procedure revi se-3(í, m, j) Deleted := false
for V (a, b) e Rtj do ■ if neexistuje c e Dm takové, že (a,c) e Rtm a {c,b) e Rmj then smaž {a,b) z R^
Deleted := true        VUV2 e {a,b}, V3 g {a,b,c}, Vi ^ V2,V2 ŕ V3, Vi ^ V3 return Deleted revise-3(l, 2,3) (^1,^3) :fca rtb acl
end revise-3l te &b bc
pozor: aa bb nejsou už v relaci Rni
M Složitost 0(k3) (k maximální velikost domény) <=
cyklus pro každou dvojici (a,b): 0(k2), vnitřní cyklus přes c e D f O(k)
Hana Rudová, Omezující podmínky, 7. října 2019 6 Konzistence po cestě
Algoritmus PC-1
Jak udělat CSP konzistentní po cestě? Provedeme revizi každé cesty délky 2 3 Revize cesty odstraní dvojice => již zrevidované cesty opět nekonzistentní Revize cesty opakujeme dokud jsou nějaké dvojice smazány Princip je podobný jako u AC-1
Před spuštěním algoritmu nutno inicializovat relace Rij pomocí existujících binárních (i unárních) podmínek '
& proceduře PC-l(G)
repeat Changed := falše f or m : = 1 to n foř i : = 1 to n
for j := 1 to n
Changed := revise-3(í,m,j) or Changed
until not(Changed) end PC-1
Hana Rudová, Omezující podmínky, 7. října 2019 7 Konzistence po cestě
Složitost algoritmu PC-1
Celková složitost 0(n5k5) odvození podobné jako pro AC-1
3 cykly pro trojice hodnot 0(n3)
revise-3 0(k3) <= 0(n2k2) počet opakování repeat cyklu
jeden cyklus smaže (v nejhorším případě) právě jednu dvojici hodnot celkem n2k2 hodnot (n2 dvojic proměnných, k2 dvojic hodnot pro každou dvojici proměnných)
Neefektivita PC-II
3 opakovaná revize všech cest, i když pro ně nedošlo k žádné změněl
s> při revizi stačí kontrolovat jen zasažené cesty podobně jako pro PC-il
3 cesty stačí brát pouze s jednou orientací ... Ríj je totéž co Rji
i  příklad: VUV2 e {a,b},V3 e \a,b,c},V1 ŕ V2,V2 ŕ V\3Vi + V3
důsledek revi se-3(l, 2, 3) a revi se-3(3, 2,1) je totožný
<= ke každé dvojici hodnot z V\,V3 (V3, Vi) hledám kompatibilní hodnotu z V2
Hana Rudová, Omezující podmínky, 7. října 2019 8 Konzistence po cestě
Algoritmus PC-2
Cesty beru pouze s jednou orientací
aktualizuji pouze jednu z R^, Rjí
3 Do fronty dávám pouze zasažené cesty podobná modifikace jako AC-3
revi se-3 (í, m, j) mění R^, Itačí tedy aktualizovat Ru přes j a Rij přes í M Před spuštěním algoritmu
M inicializovat relace Ríj pomocí existujících binárních (i unárních) podmínek
M proceduře PC-2(G)
Q := {(í,m, j) | 1 < i < j < n, 1 < m < n, m ± í, m ± j} //seznam cest pro revizi while Q non empty do
vyber a smaž trojici (í,m,j) z Q i f revi se-3 (í, m, j) then
Q := Q u {(l,í,j)(l,j,í) I 1 < l<n, l ŕ í, l ± j]
//jako u AC přidáváme jen cesty, co ještě nejsou ve frontě
end while end PC-2
Hana Rudová, Omezující podmínky, 7. října 2019 9 Konzistence po cestě
Složitost algoritmu PC-2
Složitost 0(n3k5)i
3 každé (í, m, j) může být ve frontě maximálně k2 krát =^> 0(k2)
<= když je (í,m,j) přidáno do fronty, Ríj bylo redukováno alespoň o jednu hodnotu
3 celkem n3 trojic (í,m,j) => 0(n3) ^ revise-3 0(fc3)l
Algoritmus není optimální podobně jako AC-3
M existuje algoritmus PC-4 založen na počítání podpor 3 složitost PC-4 je 0(n3/c3), což už je optimálníl
Cvičení: řešte následující problém pomocí PC-2 algoritmu
VI e {0,1, 2,3}, V2 e {0,1}, V3 e {1,2} V3 = vi + i,V2 ^ V3, VI ^ V2I
Nápověda: zkonstruuj iniciální relace
iniciálně přidej do fronty (VI, V2, V3), (VI, V3, V2), (V2, VI, V3)
Hana Rudová, Omezující podmínky, 7. října 2019 10 Konzistence po cestě
Omezení PC algoritmů
Paměťové nároky
M protože PC eliminuje dvojice hodnot z omezení, potřebuje používat extenzionální reprezentaci omezení (pro každou dvojici hodnot si pamatuji, zdaje/není v doméně)
Poměr výkon/cena
PC eliminuje více (nebo stejně) nekonzistencí jako AC
poměr výkonu ke zjednodušení problému je ale mnohem horší než u AC
Změny grafu omezení
PC přidává hrany (omezení) i tam, kde původně nebyly a mění tak konektivitu grafu
to vadí při dalším řešení problému, kdy se nemohou používat heuristiky odvozené od grafu (resp. dané původním problémem)
PC stále není dostatečnél
M V,X,Y,Z e {1,2,3},   XŕY,   Y ŕ Z,   Z ^ X,   V ŕ X,   V ŕ Y, V^Z je PC a přesto nemá řešení
Hana Rudová, Omezující podmínky, 7. října 2019 11 Konzistence po cestě
Na půli cesty od AC k PC
Jak oslabit PC, aby algoritmus:
3 neměl paměťové nároky PC neměnil graf podmínek byl silnější než AC?I
I
Omezená konzistence po cestě - Restricted Path Consistency (RPC)
M testujeme PC jen v případě, když je šance, že to povede k vyřazení hodnoty z domény proměnné
Příklad: Vi,V2e {a,b},V3e {a,b,c},Vľ^ V2,V2 ± V3,Vi ± V3 je AC ale není PC
RPC odstraní z domény V3 hodnoty a, b
Hana Rudová, Omezující podmínky, 7. října 201 9
12
Konzistence po cestě
Omezená konzistence po cestě (RPC)
PC hrany se testuje pouze tehdy, pokud vyřazení dvojice může vést k vyřazení některého z prvků z domény příslušné proměnné
M Jak to poznáme? Jedná se o jedinou vzájemnou podporu.
Proměnná Vije omezeně konzistentní po cestě (Restricted Path Consistent, RPC)
3 každá hrana vedoucí z V\ je hranově konzistentní
3 pro každé a e Dt platí:
je-li b jediná podpora a ve vrcholu j, potom v každém vrcholu k (spojeném s i a j) existuje hodnota c tak, že (a, c) a (b,c) jsou kompatibilní s příslušnými podmínkami
Algoritmus: založen na AC-4 + seznam cest pro PC (viz Barták přednáška)
Hana Rudová, Omezující podmínky, 7. října 2019 13 Konzistence po cestě
Propagace pro nebinární omezení
Nebinární omezení
3 Zobecnění principů NC, AC, a PC směrem ke k-konzistenci
3 zajímavé z pohledu složitosti řešení problémů pracuje se s libovolnými k-ticemi proměnných v praxi se vzhledem k paměťové a časové složitosti nevyužíval
Obecné typy konzistence pro nebinární podmínky
3 pracuje se přímo s n-árními podmínkami
M příklad: obecná hranová konzistence, konzistence mezil
Globální omezení: specifické typy konzistencí
3 využívá se sémantika omezení, zaměřené opět na konkrétní omezení
speciální typy konzistence pro globální omezení (př. all_different)l Pro různé podmínky lze použít různý druh konzistence
3 A<B: hranová konzistence, konzistence mezí
Hana Rudová, Omezující podmínky, 7. října 201 9 15 Propagace pro nebinární omezení
Obsah: propagace pro nebinární omezení
k-konzistence
Obecná hranová konzistence Konzistence mezí
konzistence mezí pro aritmetická omezení
I
Globální podmínky
klasické typy podmínek a příklady jejich použití 3 propagace pro all_different a pro rozvrhování s unárními zdroji
Obecný konzistenční algoritmus pro nebinární podmínky
v jeho rámci lze využívat výše zmíněné typy konzistence
Hana Rudová, Omezující podmínky, 7. října 201 9
16
Propagace pro nebinární omezení
k-konzistence
Mají AC a PC něco společného?
S AC: rozšiřujeme jednu hodnotu do druhé proměnné 3 PC: rozšiřujeme dvojici hodnot do třetí proměnné 3 ... můžeme pokračovatl
CSP je k-konzistentní právě tehdy, když můžeme libovolné konzistentní ohodnocení (k-1) různých proměnných rozšířit do libovolné k-té proměnnél
			*		*	A
		1,2,3		1,2,3		4
4-konzistentní graf
Pro obecné CSP, tedy i pro nebinární podmínky
Hana Rudová, Omezující podmínky, 7. října 201 9
17
Propagace pro nebinární omezení
Silná k-konzistence
ABC
3-konzistentní graf
(1.1) lze rozšířit na (1,1,1)
(2.2) lze rozšířit na (2,2,2)
(1.3) ani (2,3) nejsou konzistentní dvojice (nerozšiřujeme je)l
není 2-konzistentníl
(3) nelze rozšířit
CSPje silně k-konzistentní právě tehdy, když je j-konzistentní pro každé j<kl
Silná k-konzistence => k-konzistence
Silná k-konzistence => j-konzistence V j < k k-konzistence ^> silná k-konzistence
I
NC = silná 1-konzistence = 1-konzistence
AC = (silná) 2-konzistence
PC = (silná) 3-konzistence & Cvičení: uveďte příklad problému, který je 4-konzistentní, ale není 3-konzistentní
Hana Rudová, Omezující podmínky, 7. října 201 9 18 Propagace pro nebinární omezení
Konzistence pro nalezení řešení
3 Máme-li graf s n vrcholy, jak silnou konzistenci potřebujeme, abychom přímo našli řešení?
CSP vyřešíme bez navracení vzhledem k uspořádání proměnných (xi,... ,xn), jestliže pro každé i < n může být každé částečné řešení (xi,..., Xi) konzistentně rozšířeno o proměnnou Xi+i. I
Nalezení řešení bez navracení pro libovolné uspořádání proměnných? I silná n-konzistence je nutná pro graf s n vrcholy
±> n-konzistence nestačí (viz předchozí příklad) silná k-konzistence pro k<n také nestačí
graf s n vrcholy domény 1 ..(n-1)
silně k-konzistentní pro každé k<n přesto nemá řešení
Hana Rudová, Omezující podmínky, 7. října 201 9 19 Propagace pro nebinární
Algoritmy pro dosažení k-konzistence
Rozšíření revize hrany a revize cesty
postupně odstraňujeme prvky z relace nad (k-1) proměnnými
Aktualizujeme relace nad každou (k-l)-ticí proměnných
3 musíme si pamatovat (k-l)-tice hodnotí
Obecný algoritmus
M rozšíření AC-1 a PC-1
opakování revizí nad (k-l)-ticemi dokud dochází ke změnám
Velká paměťová i časová složitost
M v praxi se pro vyšší k nepoužívá
Algoritmy i složitost viz Dechter: Constraint Processing
Hana Rudová, Omezující podmínky, 7. října 201 9
20
Propagace pro nebinární omezení