Globální podmínky
Globální podmínky
Globální podmínka: definována pro libovolný konečný počet proměnných Global Constraint Catalog
http://sofdem.gi thub.i o/gccat/
M Nicolas Beldiceanu, Mats Carlsson and Jean-Xavier Rampon
Popis omezení dostupných v literatuře a v systémech s omezujícími podmínkami
„The catalog presents a list of 423 global constraints issued from the literature in constraint programming and from popular constraint systems. The semantic of each constraint is given together with some typical usage and filtering algorithms, and with reformulations in terms of graph properties, automata, and/or logical formulae. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms."
PDF dokument, srpen 2014, cca 4 000 stran
Hana Rudová, Omezující podmínky, 21. října 2019 2
(Globální podmínky a) rozvrhování
Všechny proměnné různé
M all Different
3 Disjunktivní zdroj/rozvrhování
M dvar interval, dvar sequence «• noOverlap
3 Kumulativní zdroj/rozvrhování
M cumuFunction, pulse
Alternativní zdroje * alternative
Hana Rudová, Omezující podmínky, 21. října 2019
3
Všechny proměnné různé
Proměnné v poli Array jsou různé
dvar int Array[Interval];
globální podmínka: al 1 Different(Array) ;
binární podmínky: for (i, j in Interval  : i  != j) Array[i]  != ArrayEj] ;
Hana Rudová, Omezující podmínky, 21. října 201 9
4
Všechny proměnné různé
Proměnné v poli Array jsou různé
M dvar int Array[Interval];
M globální podmínka: al 1 Different(Array) ;
M binární podmínky: for (i, j in Interval  : i  != j) Array[i]  != ArrayEj] ;
all Different vs. binární podmínky
M all Different má úplnou propagaci
binární podmínky mají slabší (neúplnou) propagaci
Příklad: učitelé musí učit v různé hodiny
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
Hana Rudová, Omezující podmínky, 21. října 2019
Všechny proměnné různé
Proměnné v poli Array jsou různé
M dvar int Array[Interval];
M globální podmínka: al 1 Different(Array) ;
M binární podmínky: for (i, j in Interval  : i  != j) Array[i]  != ArrayEj] ;
all Different vs. binární podmínky
M all Different má úplnou propagaci
binární podmínky mají slabší (neúplnou) propagaci
Příklad: učitelé musí učit v různé hodiny
M  globální podmínka:
Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr e{3,4}, Eva e {3,4}
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
Hana Rudová, Omezující podmínky, 21. října 2019
Všechny proměnné různé
Proměnné v poli Array jsou různé
M dvar int Array[Interval];
M globální podmínka: al 1 Different(Array) ;
M binární podmínky: for (i, j in Interval  : i  != j) Array[i]  != ArrayEj] ;
3 allDifferent vs. binární podmínky
M allDifferent má úplnou propagaci
binární podmínky mají slabší (neúplnou) propagaci
Příklad: učitelé musí učit v různé hodiny
M  globální podmínka:
Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr e{3,4}, Eva e {3,4}
M  binární podmínky:
Jan e{3,...,6}, Petr e{3,4}, AnnaG {2,..., 5}, Ota g {2,3,4}, Eva g{3,4}, Marie e{l,...,6}
Hana Rudová, Omezující podmínky, 21. října 2019 4
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
Naivní propagace pro all Different
M U = {Petr, Ota, Eva}, dom(U) = {2, 3, 4}:
učitel	min	max
Jan	3	6
Petr		
Anna	2	5
Ota		4
Eva		4
Marie	1	6
Hana Rudová, Omezující podmínky, 21. října 2019
5
Naivní propagace pro all Different
U = {Petr, Ota, Eva}, dom(U) = {2, 3, 4}:
{2,3,4} nelze pro Jan, Anna, Marie
Jan g {5,6}, Anna = 5, Marie g {1,5,6}
učitel	min	max
Jan	3	6
Petr		
Anna	2	5
Ota		4
Eva		4
Marie	1	6
Hana Rudová, Omezující podmínky, 21. října 2019
5
Naivní propagace pro all Different
U = {Petr, Ota, Eva}, dom(U) = {2, 3, 4}:
{2,3,4} nelze pro Jan, Anna, Marie
Jan g {5,6}, Anna = 5, Marie e {1,5,6}
Konzistence: musí platit:
učitel	min	max
Jan	3	6
Petr		
Anna	2	5
Ota		4
Eva		4
Marie	1	6
Hana Rudová, Omezující podmínky, 21. října 2019
5
Naivní propagace pro all Different
U = {Petr, Ota, Eva}, dom(U) = {2, 3, 4}:
{2,3,4} nelze pro Jan, Anna, Marie
Jan g {5,6}, Anna = 5, Marie g {1,5,6}
Konzistence: musí platit:
V{Xi,... ,Xk} c V : card{Di u
Inferenční pravidlo
uDk}>k
učitel	min	max
Jan	3	6
Petr		
Anna	2	5
Ota		4
Eva		4
Marie	1	6
Hana Rudová, Omezující podmínky, 21. října 2019
5
Naivní propagace pro all Different
U = {Petr, Ota, Eva}, dom(U) = {2, 3, 4}:
{2,3,4} nelze pro Jan, Anna, Marie Jan g {5,6}, Anna = 5, Marie e {1,5,6}
Konzistence: musí platit:
V{Xi,... ,Xk} c V : card{Di u ■ ■ ■ u Dk} > k
Inferenční pravidlo
S V: množina všech proměnných
* U = {Xu...,Xk}, dom(U) = {D1u---uDk}
* card(U) = card(dom(U)) => Vv e dom(U),\/X e (V - U),X + v
učitel	min	max
Jan	3	6
Petr		
Anna	2	5
Ota		4
Eva		4
Marie	1	6
Hana Rudová, Omezující podmínky, 21. října 2019
5
Naivní propagace pro all Different
U = {Petr, Ota, Eva}, dom(U) = {2, 3, 4}:
{2,3,4} nelze pro Jan, Anna, Marie Jan g {5,6}, Anna = 5, Marie g {1,5,6}
Konzistence: musí platit:
V{Xi,... ,Xk} c V : card{Di u ■ ■ ■ u Dk} > k
Inferenční pravidlo
S V: množina všech proměnných
3 U = {Xu...,Xk}, dom(U) = {D1u---uDk}
M card(U) = card(dom(U)) => Vv g dom(U),\/X e (V - U),X + v 3 hodnoty v dom(U) jsou pro ostatní proměnné nedostupné
učitel	min	max
Jan	3	6
Petr		
Anna	2	5
Ota		4
Eva		4
Marie	1	6
Hana Rudová, Omezující podmínky, 21. října 2019
5
Naivní propagace pro all Different
U = {Petr, Ota, Eva}, dom(U) = {2, 3, 4}:
{2,3,4} nelze pro Jan, Anna, Marie Jan g {5,6}, Anna = 5, Marie e {1,5,6}
Konzistence: musí platit:
V{Xi,... ,Xk} c V : card{Di u ■ ■ ■ u Dk} > k
M Inferenční pravidlo
3 V: množina všech proměnných M U = {Xi,...,Xk}, dom(U) = {Di u ■ ■ ■ u Dk} M card(U) = card(dom(U)) ^Vvg dom(U),\/X e (V - U),X + v 3 hodnoty v dom(U) jsou pro ostatní proměnné nedostupné
Složitost
hledání všech podmnožin množiny n proměnných (naivní) 0(2n)
Hana Rudová, Omezující podmínky, 21. října 201 9 5
učitel	min	max
Jan	3	6
Petr		4
Anna	2	5
Ota		4
Eva		4
Marie	1	6
Párování v bipartitních grafech
Efektivní propagaci pro allDifferent lze založit na párování v bipartitních grafech (Regin 94)
3 Bipartitní graf
uzly grafu rozdělené do dvou množin 3 neexistují hrany mezi uzly jedné množiny
Párování v bipartitních grafech
M 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
Hana Rudová, Omezující podmínky, 21. října 2019
6
Párování v bipartitních grafech
Efektivní propagaci pro allDifferent lze založit na párování v bipartitních grafech (Regin 94)
3 Bipartitní graf
uzly grafu rozdělené do dvou množin 3 neexistují hrany mezi uzly jedné množiny
Párování v bipartitních grafech
M 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
M CSP jako bipartitní graf
M jedna množina vrcholů reprezentuje proměnné
druhá množina vrcholů reprezentuje hodnoty proměnných 3 hrana z proměnné X do hodnoty a říká, že proměnná X může nabývat hodnoty a
Hana Rudová, Omezující podmínky, 21. října 2019 6
all Different - párování v bipartitních grafech II
M Inicializace
vypočti maximální párování
odstraň všechny hrany, které nepatří do žádného maximálního párování
sjednocení domén proměnné proměnných
Hana Rudová, Omezující podmínky, 21. října 2019
7
all Different - párování v bipartitních grafech II
Inicializace
vypočti maximální párování
3 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í
3 odstraň všechny hrany, které nepatří do žádného maximálního párování
sjednocení domén proměnné proměnných
Hana Rudová, Omezující podmínky, 21. října 2019
7
all Different - párování v bipartitních grafech II
Inicializace
sjednocení domén proměnné proměnných
S vypočti maximální párování
M 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
3 vypočti nové maximální párování
M odstraň všechny hrany, které nepatří do žádného maximálního párování
Algoritmus založen na doménové konzistenci
3 každé maximální párování definuje doménovou podporu
složitost 0(n2k2), n... počet proměnných, k... maximální velikost domény
Hana Rudová, Omezující podmínky, 21. října 2019
7
all Different - párování v bipartitních grafech II
A     ... sjednoceni domén
M nicia hzace - - i
proměnné proměnných
vypočti maximální párování
3 odstraň všechny hrany, které nepatří do žádného maximálního párování
Propagace zmenšené domény
3 odstraň odpovídající hrany
vypočti nové maximální párování
3 odstraň všechny hrany, které nepatří do žádného maximálního párování
Algoritmus založen na doménové konzistenci
3 každé maximální párování definuje doménovou podporu 3 složitost 0(n2k2), n... počet proměnných, k... maximální velikost domény
efektivnější algoritmus využívá konzistenci mezí - složitost O(nlogn) (Puget 1 998)
Hana Rudová, Omezující podmínky, 21. října 2019 7
Intervalové proměnné
Intervalová proměnná: pro modelování časového intervalu (úlohy, aktivi
3 hodnotou intervalové proměnné je celočíselný interval [start, end) * příklad: dvar interval x in 0..1000000 size 100..200;
0 [100,200] 1000000
F.........r . 'i......]
I— —I Time
Hana Rudová, Omezující podmínky, 21. října 2019
8
Intervalové proměnné
Intervalová proměnná: pro modelování časového intervalu (úlohy, aktivity)
3 hodnotou intervalové proměnné je celočíselný interval [start, end) * příklad: dvar interval x in 0..1000000 size 100..200;
0 [100,200] 1000000
[.........i   i   '......]
I— —I Time
-►
Volitelná intervalová proměnná: pro modelování časového intervalu, který může ale nemusí být přítomen v řešení (přítomný vs. nepřítomný interval)
např. pro modelování volitelných aktivit, které v řešení nemusí být
příklad: dvar interval x optional in 0..1000000 size in 100..200;
Dom(x) c {_l} u {[start, end)\start, end e Z,start < end} ± značí, že interval není přítomen v řešení
Hana Rudová, Omezující podmínky, 21. října 2019 8
Disjunktní/unární rozvrhování
Sekvenční proměnná p
& definována na množině intervalových proměnných x
dvar interval x[i in l..n] dvar sequence p in x;
hodnota intervalové proměnné p je permutace přítomných intervalů M pozor, permutace t ještě neimplikuje žádné uspořádání v čase!
Hana Rudová, Omezující podmínky, 21. října 2019
9
Disjunktní/unární rozvrhování
Sekvenční proměnná p
definována na množině intervalových proměnných x
dvar interval x[i in l..n] dvar sequence p in x;
M hodnota intervalové proměnné p je permutace přítomných intervalů M pozor, permutace t ještě neimplikuje žádné uspořádání v čase!
Omezení noOverlap(p)
vyjadřuje, že sekvenční proměnná p reprezentuje řetězec nepřekrývajících se intervalových proměnných
pro vyjádření rozvrhování na unárním/disjunktivním zdroji, kde se intervaly/úlohy/aktivity nepřekrývají
3 poznámka: nepřítomné intervaly v řetězci zahrnuty nejsou
Hana Rudová, Omezující podmínky, 21. října 2019 9
Disjunktivní rozvrhování: princip algoritmu
Hledání hran (edge finding) - Baptisté & Le Pape, 1 996
Hledáme úlohu, která předchází nebo následuje množinu jiných úloh
-0 dvar interval A in 4..16 size 2; dvar interval B in 6..16 size 4; dvar interval C in 7..15 size 5;
Co se stane, pokud nebude aktivita A zpracována jako první?
16
4
A(
6
B(4)
i16
C(5)
15
Hana Rudová, Omezující podmínky, 21. října 2019
10
Disjunktivní rozvrhování: princip algoritmu
Hledání hran (edge finding) - Baptisté & Le Pape, 1 996
Hledáme úlohu, která předchází nebo následuje množinu jiných úloh
-0 dvar interval A in 4..16 size 2; dvar interval B in 6..16 size 4; dvar interval C in 7..15 size 5;
Co se stane, pokud nebude aktivita A zpracována jako první?
16
4
A(
6
B(4)
i16
C(5) 15
Pro
A,B,C není dost času, a tedy aktivita A musí být první
4h A(2) "I 7
6h
B(4)
16
7
C(5)
Í15
Hana Rudová, Omezující podmínky, 21. října 2019
10
Další podmínky: precedence
Mezi intervalovými proměnnými můžeme definovat precedenční podmínky:
dvar i nterval i; dvar i nterval j ;
endBeforeStart(i , j); endBeforeEnd(i, j); endAtStart(i, j) ; endAtEnd(i, j) ; startBeforeStart(i, j); startBeforeEnd(i, j); startAtStart(i, j); startAtEnd(i , j) ;
Poznámka: tyto podmínky platí, pokud jsou oba intervaly přítomné
Hana Rudová, Omezující podmínky, 21. října 2019
A dále: logické podmínky
Unární podmínka pro přítomnost intervalu x:
presenceOf(x)
znamená, že x =/= ± Příklady:
presenceOf(x) == presenceOf(y)   // x přítomen právě tehdy, když je přítomen y presenceOf(x) => presenceOf(y)   // implikace presenceOf(x) => !presenceOf(y)
Pozor na použití:
precedenční podmínky: polynomiální složitost logické binární podmínky: polynomiální složitost precedence + logické binární: NP-těžké!
Hana Rudová, Omezující podmínky, 21. října 2019
12
Výrazy s intervalovými proměnnými
Pro vytváření účelových funkcí nebo definici omezení
startOf(x) endOf(x) sizeOf(x, V)
Příklad: minimalizace času dokončení poslední úlohy (tzv. makespanu)
minimize max(i in l..n) endOf(x[i])
Hana Rudová, Omezující podmínky, 21. října 2019
13
Příklad: rozvrhování problému job-shop
Job-shop problém:
problém rozvrhování úloh, které se skládají z nepřekrývajících operací každá operace úlohy prováděna na jiném stroji
pořadí operací úlohy předem určeno
op11	-►	op12	—>-	op13
op21
op22
op23
unarm stroje
op31
op41
op32
op33
[] M1 [] M2 □ M3
op42
op43
Hana Rudová, Omezující podmínky, 21. října 2019
14
Příklad: rozvrhování problému job-shop
Job-shop problém:
problém rozvrhování úloh, které se skládají z nepřekrývajících operací každá operace úlohy prováděna na jiném stroji
pořadí operací úlohy předem určeno
op11	-►	op12	—>-	op13
op21
op22
op23
unarm stroje
op31
op32
op33
op41
op42
op43
1
2
3
4
5
6
7
8
9
10
11
[] M1 [] M2 □ M3
dvar interval op[j in Jobs] [p in Pos] size Ops [j] [p] .pt; dvar sequence mchs[m in Mens] in
all(j in Jobs, p in Pos: Ops [j] [p] .men == m) op[j][p];
minimize max(j in Jobs) endOf(op[j] [nbPos]);
subject to { tuple Oper {
forall(m in Mchs) int mch; // Machine
noOverlap(mchs [m] ) ; ■ „_._// n
n      n i / •   •     -r -i .    0 n int pt; // Processing time
forallCj in Jobs, p in 2..nbPos) j.
^    endBeforeStart(op[j] [p-1] ,op[j] [p] ) ; 0per 0'ps[j in Jobs] [m in Mchs] =
Hana Rudová, Omezující podmínky, 21. října 2019
14
př. 0ps[l] [2]=<3,6>
Kumulativní funkce
Hodnota výrazu kumulativní funkce reprezentuje vývoj kvantity v čase, která může být inkrementálně změněna (snížena nebo navýšena) intervalovými proměnnými.
Příklady:
intervaly využívají počty pracovníků M intervaly využívají skladové zásoby
Intervalové proměnné x [i] přispívají do kumul. funkce po dobu svého provádění
pulse(xř 1)
int wor[l..5] = [1,3,2,4,1];
cumul Function y = sum(i in 1..5)   pul se(x[i ] , wor [i ]) ;
1
0
x
Time
Hana Rudová, Omezující podmínky, 21. října 2019
1 5
Kumulativní funkce
Hodnota výrazu kumulativní funkce reprezentuje vývoj kvantity v čase, která může být inkrementálně změněna (snížena nebo navýšena) intervalovými proměnnými.
Příklady:
intervaly využívají počty pracovníků M intervaly využívají skladové zásoby
Intervalové proměnné x [i] přispívají do kumul. funkce po dobu svého provádění
int wor[l..5] = [1,3,2,4,1];
cumul Function y = sum(i in 1..5)   pul se(x[i ] , wor [i ]) ;
A
pulse(xř 1)
0
Omezení na výrazech kumulativní funkce
x
Time
int h =
dvar int h =
cumulFunction f=
cumulFunction f=
f<=h
f<=h
Hana Rudová, Omezující podmínky, 21. října 2019
1 5
Příklad: RCPSP
Resource-contrained project scheduling problem (RCPSP)
tuple Task { key int id; i nt        pt;
int qty[Resources]; {int} succs;
}
{Task} Tasks = ... ;
Hana Rudová, Omezující podmínky, 21. října 2019
16
Příklad: RCPSP
Resource-contrained project scheduling problem (RCPSP)
1 dvar interval a[i in Tasks] size i.pt;
2 cumulFunction usage[r in Resources] =
3 sum(i in Tasks: i.qty[r]>0) pulse(a[i],i.qty[r]);
4 minimize max(i in Tasks) endOf(a[i]);
5 subject to {
6 forali(r in Resources)
7 usage[r] <= Capacity[r];
8 forali(i in Tasks, j in i.succs)
9 endBeforeStart(a[i], a[<j>]);
10 } <j> odkazuje jako klíč na celý tuple
Hana Rudová, Omezující podmínky, 21. října 2019
16
Alternativní podmínka
Pokud je interval x přítomný, pak je právě jeden z intervalů yl, . . . ,yn přítomný a je synchronizován s x (má stejný start a konec)
& alternative(x, [yl,...,yn])
Pokud je x nepřítomné, pak jsou yi také nepřítomné
Hana Rudová, Omezující podmínky, 21. října 2019
17
Alternativní podmínka
Pokud je interval x přítomný, pak je právě jeden z intervalů yl, . . . ,yn přítomný a je synchronizován s x (má stejný start a konec)
& alternative(x, [yl,...,yn])
Pokud je x nepřítomné, pak jsou yi také nepřítomné Rozšíření: právě k intervalů z yl, . . . ,yn je synchronizováno s x
& alternative(x,  [yl,...,yn], k)   //k: celočiselný výraz
Hana Rudová, Omezující podmínky, 21. října 2019
17
Alternativní podmínka
Pokud je interval x přítomný, pak je právě jeden z intervalů yl, . . . ,yn přítomný a je synchronizován s x (má stejný start a konec)
& alternative(x, [yl,...,yn])
Pokud je x nepřítomné, pak jsou yi také nepřítomné Rozšíření: právě k intervalů z yl, . . . ,yn je synchronizováno s x
& alternative(x,  [yl,...,yn], k)   //k: celočiselný výraz
Příklad použití:
-0 každá intervalová proměnná x[t] vyžaduje nbWorkers[t] přítomných intervalů mezi assigned[t] [w] pro pracovníky w
M dvar interval x[t in Tasks] size pt[u]; int nbWorkers[t in Tasks];
dvar interval assigned[Tasks][Workers] optional; forall (t in Tasks)
alternative(x[t], all (w in Workers) assigned[t][w], nbWorkers[t]);
Hana Rudová, Omezující podmínky, 21. října 201 9 1 7
Alternativní podmínka
Pokud je interval x přítomný, pak je právě jeden z intervalů yl, . . . ,yn přítomný a je synchronizován s x (má stejný start a konec)
& alternative(x, [yl,...,yn])
Pokud je x nepřítomné, pak jsou yi také nepřítomné Rozšíření: právě k intervalů z yl, . . . ,yn je synchronizováno s x
& alternative(x,  [yl,...,yn], k)   //k: celočiselný výraz
Příklad použití:
-0 každá intervalová proměnná x[t] vyžaduje nbWorkers[t] přítomných intervalů mezi
assigned[t] [w] pro pracovníky w (kód ještě nutno rošířit o nepřekrývání pro pracovníky).
M dvar interval x[t in Tasks] size pt[u]; int nbWorkers[t in Tasks];
dvar interval assigned[Tasks][Workers] optional; forall (t in Tasks)
alternative(x[t], all (w in Workers) assigned[t][w], nbWorkers[t]);
Hana Rudová, Omezující podmínky, 21. října 201 9 1 7
Obecný konzistenční algoritmus
Konzistenční algoritmus pro nebinární podmiň
Obecný konzistenční algoritmus Varianta AC-3 s frontou proměnných rozšíření AC-2001 na nebinární podmínky
Hana Rudová, Omezující podmínky, 21. října 201 9
19
Konzistenční algoritmus pro nebinární podmínky
Obecný konzistenční algoritmus Varianta AC-3 s frontou proměnných rozšíření AC-2001 na nebinární podmínky M Opakovaně se provádí revize podmínek, dokud se mění domény
proceduře Nonbinary-AC-3-with-Variables(Q) while Q non empty do
vyber a smaž V j e Q for V C takové, že V j e scope(C) do W : = revise (V/, C)
// W je množina proměnných jejichž, doména se změnila if 3 Vi e W taková, že Di = 0 then return fail Q := Q u {W} end Nonbinary-AC-3-with-Variables
Hana Rudová, Omezující podmínky, 21. října 2019
19
Revizní procedura: různé typy konzistence
Speciální revise procedury jsou definovány v závislosti na typu omezení, tj. revise procedura může implementovat
obecnou hranovou konzistenci
konzistenci mezí
M konzistenční algoritmy pro globální podmínky jako allDifferent
Hana Rudová, Omezující podmínky, 21. října 2019
20
Revizní procedura
3 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)
M vyvolání revize pouze při dané změně proměnné
& při libovolné změně domény (u obecné hranové konzistence) ±> při změně mezí (u konzistence mezí) ±> při instanciaci proměnné
M tj. pro každou proměnnou lze použít různé události
3 revize jednolivých podmínek jsou realizovány v závislosti na aktivaci odpovídající události (událostmi řízený výpočet)
Hana Rudová, Omezující podmínky, 21. října 2019
21
Revizní procedura
3 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)
M vyvolání revize pouze při dané změně proměnné
& při libovolné změně domény (u obecné hranové konzistence) ±> při změně mezí (u konzistence mezí) ±> při instanciaci proměnné
M tj. pro každou proměnnou lze použít různé události
3 revize jednolivých podmínek jsou realizovány v závislosti na aktivaci odpovídající události (událostmi řízený výpočet)
Je potřeba navrhnout propagaci přes podmínku pro danou událost
M výsledkem propagace je zmenšení domén proměnných M pro jednu podmínku lze mít více propagačních kódů
Hana Rudová, Omezující podmínky, 21. října 201 9 21
Základní konzistenční algoritmus s událostmi
-0 procedure Nonbinary-AC-3-with-Events(Q) while Q non empty do
vyber a smaž event(Vj) e Q
for V C takové, že V) e scope(C) a C čeká na event(Vj) do W : = revi se (event (V)), C) // jsou vyvolány pouze ty revize, které čekaji na danou event(Vj) // W je množina proměnných jejichž, doména se změnila if 3 Vi G W taková, že Dt = 0 then return fail Q := Q u {W} end Nonbinary-AC-3-with-Events
Hana Rudová, Omezující podmínky, 21. října 2019
22