Prohledávání a pohled dopředu Přehled prohledávacích algoritmů pro CSP 3 Rozšiřování částečného konzistentního přiřazení stromové prohledávání St backtracking i* pohled dopředu (propagace omezení) -i* pohled zpět (inteligentní vracení) J* neúplná stromová prohledávání Hana Rudová, Omezující podmínky, 4. listopadu 2019 2 Prohledávání a pohled dopředu Přehled prohledávacích algoritmů pro CSP 3 Rozšiřování částečného konzistentního přiřazení stromové prohledávání 3 backtracking i* pohled dopředu (propagace omezení) -i* pohled zpět (inteligentní vracení) 3 neúplná stromová prohledávání 3 Procházení úplných nekonzistentních přiřazení 3 generuj a testuj 3 lokální prohledávání Hana Rudová, Omezující podmínky, 4. listopadu 2019 2 Prohledávání a pohled dopředu Přehled prohledávacích algoritmů pro CSP 3 Rozšiřování částečného konzistentního přiřazení stromové prohledávání 3 backtracking i* pohled dopředu (propagace omezení) -i* pohled zpět (inteligentní vracení) 3 neúplná stromová prohledávání 3 Procházení úplných nekonzistentních přiřazení 3 generuj a testuj 3 lokální prohledávání Kombinování úplných nekonzistentních přiřazení population-based search Hana Rudová, Omezující podmínky, 4. listopadu 2019 2 Prohledávání a pohled dopředu Prohledávací algoritmy pro CSP Prohledávací algoritmy prochází (traversálně) graf stavového prostoru uzly grafu (stavy): konzistentní částečné instanciace iniciální stav: prázdné přiřazení hrany grafu: operátory, které rozšíří částečné řešení [x\/ai,...,Xj/aj] o přiřazení jedné proměnné, které není v konfliktu s dřívějšími přiřazeními, tj vznikne [xi/ai,... ,Xj/aj,Xj+i/aj+i] cílové stavy: úplná řešení Hana Rudová, Omezující podmínky, 4. listopadu 2019 červené čtverečky: chybný pokus o instanciaci, řešení neexistuje nevyplněná kolečka: nalezeno řešení (cílové stavy) černá kolečka: vnitřní uzel, máme pouze částečné přiřazení Prohledávání a pohled dopředu Prohledávací algoritmy pro CSP: vlastnosti Bod volby: z uzlu grafu vede více hran máme na výběr, kterou hodnotu přiřadíme proměnné CSP má řešení bez navracení vzhledem k uspořádání d, jestliže všechny listy v jeho grafu stavového prostoru reprezentují řešení. 3 v grafu nejsou žádné slepé větve Hana Rudová, Omezující podmínky, 4. listopadu 2019 4 Prohledávání a pohled dopředu Backtracking (BT) Prohledávání stavového prostoru do hloubky Dvě fáze backtrackingu 3 dopředná fáze: proměnné jsou postupně vybírány, rozšiřuje se částečné řešení přiřazením konzistentní hodnoty (pokud existuje) pro další proměnnou 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á, Omezující podmínky, 4. listopadu 2019 5 Prohledávání a pohled dopředu Backtracking (BT) Prohledávání stavového prostoru do hloubky Dvě fáze backtrackingu 3 dopředná fáze: proměnné jsou postupně vybírány, rozšiřuje se částečné řešení přiřazením konzistentní hodnoty (pokud existuje) pro další proměnnou 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) M aktuální - proměnná, která je právě vybrána a je jí přiřazována hodnota M budoucí - proměnné, které budou vybrány v budoucnosti Hana Rudová, Omezující podmínky, 4. listopadu 2019 5 Prohledávání a pohled dopředu Příklad: backtracking 3 Příklad: Vu V2, V3 e {1, 2, 3}, c : Vi = 3 x V3 3 Stavový prostor: Hana Rudová, Omezující podmínky, 4. listopadu 2019 6 Prohledávání a pohled dopředu Příklad: backtracking Příklad: VuV2,V3 e {1,2,3}, c\V1 = 3xV3 Příklady vizualizací viz http://www.fi .muni . cz/~hanka/vi s zpětná vazba k této bakalářská práci? «• viz kontakt na stránkách Hana Rudová, Omezující podmínky, 4. listopadu 2019 6 Prohledávání a pohled dopředu Algoritmus backtrackingu procedure Backtracking((X,D,C)) í : = 1 (inicializace čitače proměnných) D[ := Di (kopirováni domény) whi 1 e 1 < í < n přiřazeni xt : = Select-Value if Xi is null (žádná hodnota nebyla vrácena) i := i-1 (zpětná fáze) else i := í + 1 (dopředná fáze) D[ := Di if í = 0 return , ,nekonzistentni ' ' else return přiřazené hodnoty {x\,...,xn} end Backtracking 3 Algoritmus vrací pouze první řešení 3 Série domén V i: D [ c d i. Select-Value pracuje nad (promazává) D[ Hodnoty v D\ ještě netestovány vzhledem k aktuálnímu částečnému přiřazení Hana Rudová, Omezující podmínky, 4. listopadu 2019 7 Prohledávání a pohled dopředu Uspořádání hodnot pro backtracking 3 proceduře Select-Value while D[ is not empty vyber a smaž libovolný ae D[ if Consistent(aí_i,Xí = a) return a return null 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 Hana Rudová, Omezující podmínky, 4. listopadu 2019 8 Prohledávání a pohled dopředu Problémy a vylepšení backtrackingu Thľashing: opakované objevování stejných nekonzistencí a částečných úspěchů při prohledávání Hana Rudová, Omezující podmínky, 4. listopadu 2019 9 Prohledávání a pohled dopředu Problémy a vylepšení backtrackingu Thrashing: opakované objevování stejných nekonzistencí a částečných úspěchů při prohledávání M Algoritmy pohledu dopředu kontrolují podmínky dopředu 3 backtracking odhalí nesplnění podmínky teprve když přiřadí hodnoty jejím proměnným příklad: A,B,C,D,E in 1..10, A=3*E konzistenčními algoritmy lze předem upravit domény A a E Hana Rudová, Omezující podmínky, 4. listopadu 2019 9 Prohledávání a pohled dopředu Problémy a vylepšení backtrackingu Thrashing: opakované objevování stejných nekonzistencí a částečných úspěchů při prohledávání M Algoritmy pohledu dopředu kontrolují podmínky dopředu 3 backtracking odhalí nesplnění podmínky teprve když přiřadí hodnoty jejím proměnným příklad: A,B,C,D,E in 1..10, A=3*E konzistenčními algoritmy lze předem upravit domény A a E Backjumping se vrací k původci chyby příklad: A,B,C,D,E in 1..10, A>E backtracking vyzkouší všechny možnosti pro B, C, D než odhalí A^l hned po prvním neúspěšném přiřazení E se lze vrátit k přiřazování A Hana Rudová, Omezující podmínky, 4. listopadu 2019 9 Prohledávání a pohled dopředu Problémy a vylepšení backtrackingu Thrashing: opakované objevování stejných nekonzistencí a částečných úspěchů při prohledávání M Algoritmy pohledu dopředu kontrolují podmínky dopředu 3 backtracking odhalí nesplnění podmínky teprve když přiřadí hodnoty jejím proměnným příklad: A,B,C,D,E in 1..10, A=3*E konzistenčními algoritmy lze předem upravit domény A a E Backjumping se vrací k původci chyby příklad: A,B,C,D,E in 1..10, A>E backtracking vyzkouší všechny možnosti pro B, C, D než odhalí A^l hned po prvním neúspěšném přiřazení E se lze vrátit k přiřazování A M Dynamický backtracking: změna uspořádání minulých proměnných Neúplná prohledávání: hledání pouze v některých částech stavového prostoru Hana Rudová, Omezující podmínky, 4. listopadu 2019 9 Prohledávání a pohled dopředu Algoritmy pohledu dopředu {look-ahead) LA Používají propagace omezení 3 Vyvolány před přiřazováním hodnoty další proměnné Snaží se zjistit, jak rozhodnutí o výběru proměnných a hodnot ovlivní budoucí prohledávání 3 Po provedení propagace omezení lze mnohem lépe 3 rozhodnout, kterou proměnnou přiřadit ±> většinou lepší přiřadit proměnné, které nejvíce omezují zbytek stavového prostoru ± příklad: A, B,C,D,E in 1..10, D=A*B*C*E, E>5, lépe je začít s E Hana Rudová, Omezující podmínky, 4. listopadu 2019 10 Prohledávání a pohled dopředu Algoritmy pohledu dopředu {look-ahead) LA Používají propagace omezení 3 Vyvolány před přiřazováním hodnoty další proměnné Snaží se zjistit, jak rozhodnutí o výběru proměnných a hodnot ovlivní budoucí prohledávání 3 Po provedení propagace omezení lze mnohem lépe 3 rozhodnout, kterou proměnnou přiřadit ±> většinou lepší přiřadit proměnné, které nejvíce omezují zbytek stavového prostoru 3 příklad: A, B,C,D,E in 1..10, D=A*B*C*E, E>5, lépe je začít s E M rozhodnout, kterou hodnotu přiřadit proměnné 3 snaha o výběr hodnoty, která umožní nejvíce voleb v budoucích přiřazeních příklad: A,B,C in 1..10, A*B<10, B=C*2, pro A je lepší vybrat 1 Vylepšení složitosti nejhoršího případu oproti naivnímu backtrackingu zřídka. Cílem je snaha o efektivní využití algoritmů propagace omezení. Hana Rudová, Omezující podmínky, 4. listopadu 2019 10 Prohledávání a pohled dopředu Pohled dopředu pro výběr hodnoty proceduře Look-Ahead((X, D, C)) rozdíly od backtrackingu i : = 1 (inicializace čitače proměnných) D[ := Di pro 1 < i < n (kopirováni domény) whi 1 e 1 < i < n přiřazeni xt : = Select-Value-XXX i f Xi i s null (žádná hodnota nebyla vrácena) i := i-1 (zpětná fáze) nastav všechny Drk, k > i na jejich hodnotu před poslední instanciací Xi else i := í + 1 (dopředná fáze) i f í = 0 return , , nekonzi stentni ' ' else return přiřazené hodnoty {x\,... ,xn} end Look-Ahead Sel ect-Val ue-XXX se liší dle typu LA algoritmu Ukládáno n kopií každé D' M pro každou úroveň ve stavovém prostoru jedna kopie Hana Rudová, Omezující podmínky, 4. listopadu 2019 11 Prohledávání a pohled dopředu Kontrola dopředu (forward checking) FC 3 procedure Select-Value-Forward-Checking while D[ is not empty vyber a smaž libovolný a e D[ for V k, í < k < n for y b G Dk if not Consistent(ai_i,Xi = a,Xfc = Z?) smaž b z DFk if 3k,í< kV2, c2 : V2 = 3 x V3 Stavový prostor: V 1 d = V, > fail c1 => V2=1 d c2 => fail c2 V- > V2=1..2 > fail 4 d c2 1 :> V2=1..3 :> V2=3 V3=1 Hana Rudová, Omezující podmínky, 4. listopadu 2019 1 5 Prohledávání a pohled dopředu Prohledávání s iniciální konzistencí Prohledávací algoritmus často aplikován až po zajištění iniciální konzistence typicky: iniciální konzistence a pak kontrola dopředu nebo iniciální konzistence a pak pohled dopředu Příklad: pohled dopředu + iniciální konzistence Vi,V2lV3 in 1...4 cl:Vi>V2, c2:V2 = 3xV3 V- y 2 3< d => V1 in 2..4 V2in 1..3 c2 => V2=3 V3= 1 d => V1= 4 V3 1 Ó Hana Rudová, Omezující podmínky, 4. listopadu 2019 16 Prohledávání a pohled dopředu Srovnání algoritmů Backtracking (BT) kontroluje v kroku a podmínky c(Vi,Va),...,c(Va_i,Vfl) z minulých proměnných do aktuální proměnné +FC proměnné 3l. --~í =3 &) C N ôt § CD aktuálni 2" CD o. "5 o =q- c &) o N ^ CD CD Rudová, Omezující podmínky, 4. listopadu 2019 17 Prohledávání a pohled dopředu Srovnání algoritmů Backtracking (BT) kontroluje v kroku a podmínky c(Vi,VJ,...,c(Va_i,VJ 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é +FC proměnné 3l. --~í =3 &) C N ôt § CD aktuálni 2" CD o. "5 o =q- c &) o N ^ CD CD Hana Rudová, Omezující podmínky, 4. listopadu 2019 17 Prohledávání a pohled dopředu Srovnání algoritmů Backtracking (BT) kontroluje v kroku a podmínky c(Vi,VJ,...,c(Va_i,VJ 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 ^ / Vi(a < l < n), Vfc(a í na jejich hodnotu před posledni instanciaci Xt else if i < n s :=miní