Pohled zpět Přehled algoritmů pohledu zpět look-back M Algoritmy skoku zpět (backjumping) 3 při zpětném průchodu se nevracíme pouze jeden krok jako algoritmus backtrackingu snažíme se vracet co nejdále až ke zdroji chyby Algoritmy učení (constraint recorďmg, no-good learning) M no-good = chybné částečné přiřazení přidáme nová omezení, která zakazují nalezená chybná přiřazení Dynamický backtracking při skoku zpět se snažíme nezapomínat už udělanou práci 3 měníme hodnoty pouze u minulých proměnných s konfliktem (ostatní neměníme) 3 realizace: změníme uspořádání proměnných 3 Backmarking 3 pamatuje si, kde testy na konzistenci neuspěly M eliminuje opakování dříve provedených konzistenčních testů Hana Rudová, Omezující podmínky, 18. listopadu 2019 2 Pohled zpět při prohledávání Konfliktní množina pevné uspořádání proměnných (x\,..., xn) 3 Mějme částečné konzistentní prirazení ä = (a^,..., aik) libovolné podmnožiny proměnných a uvažujme dosud nepřiřazenou proměnnou x. Jestliže neexistuje hodnota b z domény x tak, aby (a, x = b) bylo konzistentní, říkáme, že a je konfliktní množina x a nebo, že a je v konfliktu s x. M vyznačené přiřazení je konfliktní množina vzhledem k X7 Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 3 Pohled zpět při prohledávání Konfliktní množina pevné uspořádání proměnných (x\,..., xn) 3 Mějme částečné konzistentní prirazení ä = (a^,..., aik) libovolné podmnožiny proměnných a uvažujme dosud nepřiřazenou proměnnou x. Jestliže neexistuje hodnota b z domény x tak, aby (a, x = b) bylo konzistentní, říkáme, že a je konfliktní množina x a nebo, že a je v konfliktu s x. M vyznačené přiřazení je konfliktní množina vzhledem k X7 M Pokud ä neobsahuje j-tici (j < k), která je v konfliktu s x, pak nazýváme ä minimální konfliktní množina. {xi/red,x3/blue}: min.konf.množina vzhledem k x7 Hana Rudová, Omezující podmínky, 18. listopadu 2019 3 Pohled zpět při prohledávání Chybné přiřazení M Mějme částečné konzistentní přiřazení di-\ = (ai,..., at_i). Jestliže je di-\ v konfliktu s xu pak ho nazýváme list slepé větve. M přiřazení v předchozím příkladu je list slepé větve Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 4 Pohled zpět při prohledávání Chybné přiřazení Mějme částečné konzistentní přiřazení cíí-\ = (ai,..., at_i). Jestliže je ai-\ v konfliktu s xu pak ho nazýváme list slepé větve. M přiřazení v předchozím příkladu je list slepé větve Částečné přiřazení a, které se nevyskytuje v žádném řešení CSP, se nazývá chybné přiřazení (no-good). konfliktní množiny jsou chybná přiřazení Cj^e,areen omezeni: ^ [xi/blue,X2/green,X5/blue] je chybné přiřazení, ale nepatří do žádné konfliktní množiny Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 4 Pohled zpět při prohledávání Chybné přiřazení Mějme částečné konzistentní přiřazení cíí-\ = (ai,..., at_i). Jestliže je ai-\ v konfliktu s xu pak ho nazýváme list slepé větve. M přiřazení v předchozím příkladu je list slepé větve Částečné přiřazení a, které se nevyskytuje v žádném řešení CSP, se nazývá chybné přiřazení (no-good). konfliktní množiny jsou chybná přiřazení Cj^e,areen omezeni: ^ [xi/blue,X2/green,X5/blue] je chybné přiřazení, ale nepatří do žádné konfliktní množiny konflitní množina = chybné přiřazení vzhledem k jediné proměnné Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 4 Pohled zpět při prohledávání Chybné přiřazení Mějme částečné konzistentní přiřazení cíí-\ = (ai,..., at_i). Jestliže je ai-\ v konfliktu s xu pak ho nazýváme list slepé větve. M přiřazení v předchozím příkladu je list slepé větve Částečné přiřazení a, které se nevyskytuje v žádném řešení CSP, se nazývá chybné přiřazení (no-good). konfliktní množiny jsou chybná přiřazení Cj^e,areen omezeni: ^ 3 [xi/blue,X2/green,X5/blue] je chybné přiřazení, ale nepatří do žádné konfliktní množiny M konflitní množina = chybné přiřazení vzhledem k jediné proměnné 3 Minimální chybná přiřazení neobsahují chybná přiřazení méně proměnných. Hana Rudová, Omezující podmínky, 18. listopadu 2019 4 Pohled zpět při prohledávání Konfliktní proměnná Mějme list slepé větve äi-\. Proměnná Xj (j < i - 1) je bezpečná, pokud je äj chybné přiřazení. také říkáme, že skok z xt na Xj je bezpečný nevynecháme žádné řešení 1 j i Hana Rudová, Omezující podmínky, 18. listopadu 2019 5 Pohled zpět při prohledávání Konfliktní proměnná Mějme list slepé větve di-\. Proměnná Xj (j < i - 1) je bezpečná, pokud je áj chybné přiřazení. také říkáme, že skok z xt na Xj je bezpečný nevynecháme žádné řešení Mějme list slepé větve di-\. Proměnná Xt je konfliktní proměnná (culprit) vzhledem k dí-i, jestliže b = mín{k < i \ äk v konfliktu s xj. au 1 b-1 ... a^inení v konfliktu s xí b......ab v konfliktu s x{ k.......ak v konfliktu s x{ J Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 5 Pohled zpět při prohledávání Konfliktní proměnná Mějme list slepé větve di-i. Proměnná Xj (j < i - 1) je bezpečná, pokud je dj chybné přiřazení. také říkáme, že skok z xt na Xj je bezpečný nevynecháme žádné řešení Mějme list slepé větve di-\. Proměnná x^ je konfliktní proměnná (culprit) vzhledem k ät-i, jestliže b = mín{k < i | äk v konfliktu s xj. Uli 1 b-1 ... a^není v konfliktu s xí b......ab v konfliktu s x{ k.......ak v konfliktu s x{ J Tvrzení: Skok ke konfliktní proměnné je bezpečný. Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 5 Pohled zpět při prohledávání Gaschnigův skok zpět Gaschnig's backjumping (GBJ) «• když nedokážeme přiřadit hodnotu proměnné xu vracíme se zpět (skáčeme zpět) ke konfliktní proměnné 3 určení konfliktní proměnné ±> pro každou hodnotu vi e xi nalezneme proměnnou s nejmenším indexem, která je s xJmx v konfliktu (přiřazení této proměnné musíme určitě změnit, aby šla hodnota vi použít) i- konfliktní proměnná je ta z nich, která má největší index (když její hodnotu změníme, můžeme zrušit konflikt s odpovídající hodnotou) v1 v2 Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 6 Pohled zpět při prohledávání Algoritmus GBJ Každá proměnná Xt uchovává v latestt index konfliktní proměnné proceduře GBJ ((X,D, C)) rozdíly od backtrackingu í : = 1 (inicializace čitače proměnných) D[ := Di (kopirováni domény) latestj := 0 (inicializace čitače na konfliktmi proměnnou whi 1 e 1 < í < n přiřazeni xt : = Select-Value-GBJ i f xt i s null (žádná hodnota nebyla vrácena) í := latestj (skok zpět) else í := í + 1 (dopředná fáze) D[ := Di latestj := 0 i f í = 0 return , , nekonzi stentni ' ' else return prirazené hodnoty {x\,...,xn} end GBJ Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 7 Pohled zpět při prohledávání GBJ: výběr hodnoty proceduře Select-Value-GBJ while D[ is not empty vyber a smaž libovolný v e D[ v1 TT v2 consistent := true k : = 1 while k latestj latestj := k if not Consistent(Vfc,X{ = v) consistent := false else k := k+1 if consistent return v return null (v doméne Xt neexistuje konzistentní' hodnota) Hana Rudová, Omezující podmínky, 18. listopadu 2019 8 Pohled zpět při prohledávání GBJ: příklad x4 M vyznačené přiřazení zároveň říká, že předchozí hodnoty už jsme vyzkoušeli (a vyřadili) M X7 = red vyřadí x\ (tj. latesty = 1), x 7 = biu e vyřadí X3 => celkem latesty = 3 M vracíme se ke konfliktní proměnné X3, ta už má ale prázdnou doménu M latesty = 2, vracíme se tedy k X2 M X3=red dala latesty na 1, X3=blue dala latesty na 2 lépe (až k x\) se ale vrátit neumíme, GBJ se v tomto okamžiku vrací k předchozí proměnné Hana Rudová, Omezující podmínky, 18. listopadu 2019 9 Pohled zpět při prohledávání Konflikty řízený skok zpět Conflict-directed backjumping CBJ Při skoku zpět na proměnnou Xj z listu slepé větve nemusíme nalézt v doméně Xj žádné hodnoty pro přiřazení. a/_i se pak nazývá vnitřní slepá větev. Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 10 Pohled zpět při prohledávání Konflikty řízený skok zpět Conflict-directed backjumping CBJ Při skoku zpět na proměnnou Xj z listu slepé větve nemusíme nalézt v doméně Xj žádné hodnoty pro přiřazení. a/_i se pak nazývá vnitřní slepá větev. CBJ skáče zpět v listu slepé větve i ve vnitřní slepé větvi M udržujeme Ji množinu skoků zpět pro každou proměnnou pomocí nesplněných omezení proměnná Xj(j < i) je bližší k xt než Xk(k < í), jestliže j > k, naopak Xk je vzdálenější ^ omezení R je vzdálenější než omezení S, jestliže je nejbližší proměnná v rozsahu R vzdálenější než nejbližší proměnná v rozsahu S (pokud totožné proměnné, rozhodují další proměnné). Pro uspořádání (x\,X2, ■ ■ ■)'■ & rozsah R\. (X3,X5,X7), rozsah S\. (X2,Xq,x&,Xg) R\ je vzdálenější než S\ od X\o Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 10 Pohled zpět při prohledávání Konflikty řízený skok zpět Conflict-directed backjumping CBJ Při skoku zpět na proměnnou Xj z listu slepé větve nemusíme nalézt v doméně Xj žádné hodnoty pro přiřazení. a/_i se pak nazývá vnitřní slepá větev. CBJ skáče zpět v listu slepé větve i ve vnitřní slepé větvi M udržujeme Ji množinu skoků zpět pro každou proměnnou pomocí nesplněných omezení proměnná Xj(j < i) je bližší k xt než Xk(k < í), jestliže j > k, naopak Xk je vzdálenější 3 omezení R je vzdálenější než omezení S, jestliže je nejbližší proměnná v rozsahu R vzdálenější než nejbližší proměnná v rozsahu S (pokud totožné proměnné, rozhodují další proměnné). Pro uspořádání (x\,X2, ■ ■ ■)'■ S rozsah R\\ (x3,Xs,Xj), rozsah S\\ (x2,XQ,Xs,Xg) R\ je vzdálenější než S\ od X\o rozsah R2: (x3,Xs,Xs,Xg), rozsah 5*2: (x2,XQ,Xs,Xg) R2 je vzdálenější než 5*2 od X\o Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 10 Pohled zpět při prohledávání Konflikty řízený skok zpět Conflict-directed backjumping CBJ Při skoku zpět na proměnnou Xj z listu slepé větve nemusíme nalézt v doméně Xj žádné hodnoty pro přiřazení. a/_i se pak nazývá vnitřní slepá větev. CBJ skáče zpět v listu slepé větve i ve vnitřní slepé větvi M udržujeme Ji množinu skoků zpět pro každou proměnnou pomocí nesplněných omezení proměnná Xj(j < i) je bližší k xt než Xk(k < í), jestliže j > k, naopak Xk je vzdálenější 3 omezení R je vzdálenější než omezení S, jestliže je nejbližší proměnná v rozsahu R vzdálenější než nejbližší proměnná v rozsahu S (pokud totožné proměnné, rozhodují další proměnné). Pro uspořádání (x\,X2, ■ ■ ■)'■ S rozsah R\\ (x3,Xs,Xj), rozsah S\\ (x2,XQ,Xs,Xg) R\ je vzdálenější než S\ od X\o rozsah R2: (x3,Xs,Xs,Xg), rozsah 5*2: (x2,XQ,Xs,Xg) R2 je vzdálenější než 5*2 od X\o M mezi nesplněnými omezeními vybereme to nejvzdálenější (ostatní omezení neumožní nejdelší možný skok zpět) 3 skočíme zpět na nejbližší proměnnou v tomto omezení (je bezpečné změnit proměnnou, která byla nejpozději přiřazená) Hana Rudová, Omezující podmínky, 18. listopadu 2019 10 Pohled zpět při prohledávání CBJ: výběr hodnoty proceduře Select-Value-CBJ while D[ is not empty vyber a smaž libovolný v e D[ consistent := true k := 1 while k<í a consistent if Consistent(Vfc,X{ = v) k : = k + 1 else R := nejvzdálenější nesplněné omezení přidej proměnné v rozsahu R vyjma Xj do Ji consistent := false if consistent return v return null (v doméně Xt neexistuje konzistentní' hodnota) Hana Rudová, Omezující podmínky, 18. listopadu 2019 11 Pohled zpět při prohledávání Algoritmus CBJ proceduře CBJ((X,D,C)) í := 1 Jí := 0 whi 1 e 1 < í < n přiřazeni xt : = Select-Value-CBJ i f Xi i s null íp := í í := index poslední proměnné v Jt Jt ■= Jí u Jip - {Xi} rozdíly od backtrackingu (inicializace čitače proměnných) (kopirováni domény) (inicializace množiny skoků zpět) (žádná hodnota nebyla vrácena) (skok zpět) (spoj množiny skoku zpět) (takto upravená Ji se použije ve vnitřni slepé větvi) else i := í + 1 (dopředná fáze) D[ := Dt Jí:=0 # if í = 0 return , ,nekonzistentni ' ' else return přiřazené hodnoty {x\, end CBJ Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 12 Pohled zpět při prohledávání CBJ: příklad X4 před vstupem do Select-Value-CBJ pro proměnnou Xy je Jy = 0 M X3 ^ Xy je nejvzdálenější omezení, které vyřadilo X7 =red, tedy// = {X3} X\ ± Xy je nejvzdálenější omezení, které vyřadilo Xy = blue, tedy Jy = {x\, X3} & skáčeme zpět na poslední proměnnou v Jy, tedy na X3 do Í3, která byla zatím prázdná, přidáme X\ M doména X3 je prázdná, v J3 je jediná proměnná X\ a na tu se vracíme Hana Rudová, Omezující podmínky, 18. listopadu 2019 13 Pohled zpět při prohledávání Algoritmy učení Množiny skoků zpět jsou chybná prirazení vypočítaná během prohledávání Tato chybná prirazení se mohou vyskytovat i později v jiných cestách stromu prohledávání a jsou znovu počítána 3 Přidáme chybná prirazení jako nová omezení při detekci slepé větve nemá cenu uchovávat celou slepou větev ät v proměnné Xí+i na toto přiřazení už později nenarazíme M uchováme chybná přiřazení na podmnožině proměnných {x\,...,xt\ Prořezávání stavového prostoru 3 čím menší chybná přiřazení se podaří uchovat, tím rychlejší bude prohledávání Zvětšování množiny omezení cena za prořezávání stavového prostoru nesmí přerůst cenu za zvětšování množiny omezení Hana Rudová, Omezující podmínky, 18. listopadu 2019 14 Pohled zpět při prohledávání Učení skoku zpět (jumpback learning) M Využijeme chybná prirazení, která jsme se naučili v CBJ Algoritmus učení skoku zpět = CBJ + přidávání nových omezení Po dosažení listu slepé větve äi-i přidáme omezení zakazující äí-i[Jí] projekce na Ji Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 Pohled zpět při prohledávání Učení skoku zpět (jumpback learning) Využijeme chybná přiřazení, která jsme se naučili v CBJ Algoritmus učení skoku zpět = CBJ + přidávání nových omezení Po dosažení listu slepé větve di-\ přidáme omezení zakazující dí-i[Jí] omezeni: j4 red ,green, teal projekce na Ji po dosažení listu slepé větve v xq je Jq = {x2,x4,Xs} <= red vyřadila xq ± Xs, blue vyřadila xq ± x2, green vyřadila xq ± x4 Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 1 5 Pohled zpět při prohledávání Učení skoku zpět (jumpback learning) Využijeme chybná přiřazení, která jsme se naučili v CBJ Algoritmus učení skoku zpět = CBJ + přidávání nových omezení Po dosažení listu slepé větve di-i přidáme omezení zakazující dt-ilJt] omezeni: j4 red ,green, teal projekce na Ji M po dosažení listu slepé větve v xq je Jq = {x2,X4,Xs} <= red vyřadila xq ± Xs, blue vyřadila xq ± X2, green vyřadila xq ± X4 * dsíJe] tedy zakazuje přiřazení [(X2,blue), {X4,green), (xs,red)] M později při procházení stromu lze např. ze znalosti X2 =blue, X4 =green odvodit x 5 ^red Hana Rudová, Omezující podmínky, 18. listopadu 2019 15 Pohled zpět při prohledávání