Další rozšíření backtrackingu Problémy skoku zpět Při skoku zpět zapomínáme už udělanou práci Příklad: Obarvěte graf třemi barvami tak, že mají sousední vrcholy různou barvu (uvedené hodnoty barev jsme už vyzkoušeli) Vrchol Barva A 1 B 2 C 1 2 D 1 2 3 E 1 2 3 Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 2 Další rozšíření backtrackingu Problémy skoku zpět Při skoku zpět zapomínáme už udělanou práci Příklad: Obarvěte graf třemi barvami tak, že mají sousední vrcholy různou barvu (uvedené hodnoty barev jsme už vyzkoušeli) Vrchol Barva A 1 B 2 C 1 2 D 1 2 3 E 1 2 3 => zpět na D Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 2 Další rozšíření backtrackingu Problémy skoku zpět Při skoku zpět zapomínáme už udělanou práci Příklad: Obarvěte graf třemi barvami tak, že mají sousední vrcholy různou barvu (uvedené hodnoty barev jsme už vyzkoušeli) Vrchol Barva A 1 1 B 2 2 1 C 1 2 1 2 D 12 3: => skok na B 1 2 E 12 3 = > zpět na D 1 2 3 Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 2 Další rozšíření backtrackingu Problémy skoku zpět Při skoku zpět zapomínáme už udělanou práci Příklad: Obarvěte graf třemi barvami tak, že mají sousední vrcholy různou barvu (uvedené hodnoty barev jsme už vyzkoušeli) Vrchol Barva A 1 1 B 2 2 1 C 1 2 1 2 D 12 3: => skok na B 1 2 E 12 3 = > zpět na D 1 2 3 Při druhém ohodnocení C děláme zbytečnou práci, stačilo nechat původní hodnotu 2, změnou B se nic neporušilo Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 2 Další rozšíření backtrackingu Dynamický backtracking: příklad 3 Stejný graf (A,B,C,D,E), stejné barvy (1,2,3), ale jiný postup Skok zpět + pamatování si důvodu konfliktu + přenos důvodu konfliktu + změna pořadí proměnných = dynamický backtracking Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 3 Další rozšíření backtrackingu Dynamický backtracking: příklad Stejný graf (A,B,C,D,E), stejné barvy (1,2,3), ale jiný postup Skok zpět + pamatování si důvodu konfliktu + přenos důvodu konfliktu + změna pořadí proměnných = dynamický backtracking Vrchol 1 2 3 A 0 B 0 vybraná barva: o C A 0 důvod konfliktu: AB D A B 0 E A B D Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 3 Další rozšíření backtrackingu Dynamický backtracking: příklad Stejný graf (A,B,C,D,E), stejné barvy (1,2,3), ale jiný postup Skok zpět + pamatování si důvodu konfliktu + přenos důvodu konfliktu + změna pořadí proměnných = dynamický backtracking Vrchol 1 2 3 Vrchol 1 2 3 A 0 A 0 B 0 B 0 vybraná barva: o C A 0 C A 0 důvod konfliktu: AB D A B 0 D A B AB E A B D E A B skok zpět (na D) + přenos důvodu chyby (AB) Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 3 Další rozšíření backtrackingu Dynamický backtracking: příklad Stejný graf (A,B,C,D,E), stejné barvy (1,2,3), ale jiný postup Skok zpět + pamatování si důvodu konfliktu + přenos důvodu konfliktu + změna pořadí proměnných = dynamický backtracking Vrchol 1 2 3 Vrchol 1 2 3 Vrchol 1 2 3 A 0 A 0 A 0 B 0 B 0 C A 0 vybraná barva: o C A 0 C A 0 B 0 A důvod konfliktu: AB D A B 0 D A B AB D A 0 E A B D E A B E A D o skok zpět (na D) skok zpět (na B) + přenos důvodu chyby (AB) + přenos důvodu chyby (A) + změna pořadí (B,C) Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 3 Další rozšíření backtrackingu Dynamický backtracking: příklad Stejný graf (A,B,C,D,E), stejné barvy (1,2,3), ale jiný postup Skok zpět + pamatování si důvodu konfliktu + přenos důvodu konfliktu + změna pořadí proměnných = dynamický backtracking Vrchol 1 2 3 Vrchol 1 2 3 Vrchol 1 2 3 A 0 A 0 A 0 B 0 B 0 C A 0 vybraná barva: o C A 0 C A 0 B 0 A důvod konfliktu: AB D A B 0 D A B AB D A 0 E A B D E A B E A D o skok zpět (na D) skok zpět (na B) + přenos důvodu chyby (AB) + přenos důvodu chyby (A) + změna pořadí (B,C) M Vrchol C, resp. celý graf, který na něm případně visel není nutno přebarvovat Hana Rudová, Omezující podmínky, 18. listopadu 2019 3 Další rozšíření backtrackingu Dynamický backtracking: algoritmus procedure DB(Variables, Constraints) Labelled := 0; Uniabelled := Variables while Unlabelled <> 0 do vyber X z Unlabelled ValuesX := DX - hodnoty nekonzistentní s Labelled použitím Constraints Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 4 Další rozšíření backtrackingu Dynamický backtracking: algoritmus procedure DB(Variables, Constraints) Labelled := 0; Uniabelled := Variables while Unlabelled <> 0 do vyber X z Unlabelled ValuesX := DX - hodnoty nekonzistentní s Labelled použitím Constraints if ValuesX= 0 then nechť E je vysvětlení konfliktu (množina konfliktních proměnných) if E = 0 then failure else nechť Y je nejbližší proměnná v E zruš přiřazení Y (z Labelled) s vysvětlením E-Y smaž všechna vysvětlení zahrnujícící Y Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 4 Další rozšíření backtrackingu Dynamický backtracking: algoritmus procedure DB(Variables, Constraints) Labelled := 0; Uniabelled := Variables while Unlabelled <> 0 do vyber X z Unlabelled ValuesX := DX - hodnoty nekonzistentní s Labelled použitím Constraints if ValuesX= 0 then nechť E je vysvětlení konfliktu (množina konfliktních proměnných) if E = 0 then failure else nechť Y je nejbližší proměnná v E zruš přiřazení Y (z Labelled) s vysvětlením E-Y smaž všechna vysvětlení zahrnujícící Y else vyber V z ValuesX Unlabelled := Unlabelled -{X} Labelled := Labelled u {X/V} return Labelled Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 4 Další rozšíření backtrackingu Dynamický backtracking: algoritmus procedure DB(Variables, Constraints) Labelled := 0; Uniabelled := Variables while Unlabelled <> 0 do vyber X z Unlabelled ValuesX := DX - hodnoty nekonzistentní s Labelled použitím Constraints if ValuesX = 0 then nechť E je vysvětlení konfliktu (množina konfliktních proměnných) if E = 0 then failure else nechť Y je nejbližší proměnná v E zruš přiřazení Y (z Labelled) s vysvětlením E-Y smaž všechna vysvětlení zahrnujícící Y else vyber V z ValuesX Unlabelled := Unlabelled -{X} Labelled := Labelled u {X/V} return Labelled Nevýhody algoritmu: přeuspořádáváním proměnných rušíme efekt heuristik výběru proměnných Hana Rudová, Omezující podmínky, 18. listopadu 2019 4 Další rozšíření backtrackingu Redundance backtrackingu Redundantní práce: opakování výpočtu, jehož výsledek už máme k dispozici Změna B neovlivňuje hodnotu C => není potřeba znova procházet podstromy C=l,... ,C=9 Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 5 Další rozšíření backtrackingu Redundance backtrackingu Redundantní práce: opakování výpočtu, jehož výsledek už máme k dispozici Změna B neovlivňuje hodnotu C => není potřeba znova procházet podstromy C=l,... ,C=9 M Backmarking pamatuje si, kde testy na konzistenci neuspěly eliminuje opakování dříve provedených konzistenčních testů Hana Rudová, Omezující podmínky, 18. listopadu 2019 5 Další rozšíření backtrackingu Základy backmarkingu Mark(Y, u každé hodnoty b z domény Y pamatuje nejvzdálenější konflikt 3 konflikt = proměnná xp taková, že ap je v konfliktu s Y = b 3 BackTo(Y): u každé proměnné Y pamatuje nejvzdálenější návrat 3 návrat = proměnná, jejíž hodnota se změnila od poslední instanciace Y Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 6 Další rozšíření backtrackingu Základy backmarkingu Mark(Y, u každé hodnoty b z domény Y pamatuje nejvzdálenější konflikt konflikt = proměnná xp taková, že ap je v konfliktu s Y = b p BackTo(Y): u každé proměnné Y pamatuje nejvzdálenější návrat M návrat = proměnná, jejíž hodnota se změnila od poslední instanciace Y Y=b Mark BackTo Mark(Y,b) BackTo(Y) BackTo(Y) Mark(Y,b) Y/b je nekonzistentní Y/b je s X/a stále s X/a (konzistentní nekonzistentní, se vším nad X) Y=b tedy nezkoušíme přiřazovat Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 6 zde je Y/b v pořáku zde je třeba X=? ^ Y/b znovu zkontrolovat Y=b Y/b je nekonzistení s X/a (aleje konzistentní se vším předtím) Další rozšíření backtrackingu Backmarking: příklad Problém N královen 1 m 2 i « 3 2 1 2 ľ 4 !> 5 4 2 1 2 3 6 3 2 4 3 1 2 3 7 8 Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 7 1 . Dámy přiřazujeme po řádcích, tj. pro každou dámu hledáme sloupec 2. Vedle šachovnice píšeme úrovně návratu (BackTo). Na začátku všude 1. 3. Do políčka zapisujeme čísla nejvzdálenějších konfliktních dam (Mark). Na začátku všude 1. Další rozšíření backtrackingu Backmarking: příklad Problém N královen 1 . Dámy přiřazujeme po řádcích, tj. pro 1 každou dámu hledáme sloupec 1 2. Vedle šachovnice píšeme úrovně návratu 1 (BackTo). Na začátku všude 1. 1 3. Do políčka zapisujeme čísla ^ nejvzdálenějších konfliktních dam (Mark). Na začátku všude 1. 5 4. Dámu v řádku 6 nelze přiřadit. 1 5. Vracíme se na 5, opravíme BackTo. 1 6. Když znova přijdeme na 6, všechny pozice jsou stále špatné (M a r k< BackTo) Backmarking lze kombinovat s backjumpingem (zdarma) 1 m 2 i « 3 2 1 2 ľ 4 !> 5 4 2 1 2 3 6 3 2 4 3 1 2 3 7 8 Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 7 Další rozšíření backtrackingu Algoritmus backmarkingu procedure Backmarki ng((X,D, C)) rozdíly od backtrackingu Mark(Xj,v) := 0, BackTo(Xj) := 0 pro Ví a V v (inicializace datových struktur) i : = 1 (inicializace čitače proměnných) D[ := Di (kopirováni domény) whi 1 e 1 < i < n přiřazeni xt := Select-Value-Backmarking if Xi is null (žádná hodnota nebyla vrácena) for V j :i < j < n (úprava BackTo pro budouci proměnné) if í < BackTo(Xj) then BackTo(Xj) := í (í je nový nejvzdálenějši návrat) BackTo(Xj) := i - 1 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 Backmarking Hana Rudová, Omezující podmínky, 18. listopadu 2019 8 Další rozšíření backtrackingu Uspořádání hodnot pro backmarking proceduře Select-Value-Backmarking smaž z D[ všechna v taková, že Mark(X{,v) Neúplná stromová prohledávání 3 Neúplné prohledávání do hloubky 1 2 3 4 567 Hana Rudová, Omezující podmínky, 18. listopadu 2019 11 Neúplná stromová prohledávání Neúplné prohledávání do hloubky Depth first search (DFS): odpovídá algoritmu backtrackingu Reálne problémy mají často tak velké prostory možných ohodnocení, že není možné je celé prohledat. Je možné prohledat jen omezený prostor => Neúplná stromová prohledávání 3 Neúplné prohledávání do hloubky 1 2 3 4 567 Hana Rudová, Omezující podmínky, 18. listopadu 2019 11 Neúplná stromová prohledávání Neúplná stromová prohledávání Neprohledáváme celý stavový prostor Nemáme záruku, že řešení neexistuje, i když ho algoritmus nenalezne M ztráta úplnosti M u některých algoritmů lze obecně zaručit úplnost, i když s vyšší složitostí než měl původní algoritmus V řadě případů najdeme řešení rychleji Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 12 Neúplná stromová prohledávání Neúplná stromová prohledávání Neprohledáváme celý stavový prostor Nemáme záruku, že řešení neexistuje, i když ho algoritmus nenalezne M ztráta úplnosti M u některých algoritmů lze obecně zaručit úplnost, i když s vyšší složitostí než měl původní algoritmus V řadě případů najdeme řešení rychleji Neúplné algoritmy často odvozeny od algoritmu úplného (DFS) M přerušení běhu algoritmu (cutoff) ±< po vyčerpání přiděleného prostředku (čas, počet návratů, ...) algoritmus přerušíme X* prostředek může být globální (pro celý strom) i lokální (pro daný podstrom nebo uzel) opakovaní běhu algoritmu (restart) ± běh předešlého neúplného prohledávání opakujeme s jiným nastavením parametrů při opakování běhu lze využívat algoritmy učení Hana Rudová, Omezující podmínky, 18. listopadu 2019 12 Neúplná stromová prohledávání Randomizovaný backtracking Časově omezený backtracking (přerušení) běh (úplného) algoritmu ukončíme po zadaném časovém intervalu (prostředek=čas) časový interval lze pro další běhy zvětšit => při dostatečném počtu kroků máme úplný algoritmus Náhodný výběr hodnot a proměnných (opakování) M pokud máme možnost volby při výběru hodnot nebo proměnných (vzhledem k dané heuristice uspořádání hodnot a proměnných) náhodně zvolíme některou z nich Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 13 Neúplná stromová prohledávání Randomizovaný backtracking Časově omezený backtracking (přerušení) běh (úplného) algoritmu ukončíme po zadaném časovém intervalu (prostředek=čas) časový interval lze pro další běhy zvětšit => při dostatečném počtu kroků máme úplný algoritmus Náhodný výběr hodnot a proměnných (opakování) M pokud máme možnost volby při výběru hodnot nebo proměnných (vzhledem k dané heuristice uspořádání hodnot a proměnných) náhodně zvolíme některou z nich 3 Randomizovaný backtracking s učením 3 chybná přiřazení předchozích běhů uchováme a využíváme M takto lze také dosáhnout úplnosti, protože chybných přiřazení je konečně mnoho Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 13 Neúplná stromová prohledávání Omezení počtu návratů 3 Bounded-backtrack search (BBS) Omezený počet návratů (přerušení) návrat do bodů volby, kde už nelze vybrat novou hodnotu nezapočítáváme > „omezený počet navštívených listů" Pro úplnost: při neúspěchu zvětšíme počet návratů o jedna (opakování) Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 14 Neúplná stromová prohledávání Omezení počtu návratů Bounded-backtrack search (BBS) Omezený počet návratů (přerušení) návrat do bodu volby, kde už nelze vybrat novou hodnotu nezapočítáváme „omezený počet navštívených listů Pro úplnost: při neúspěchu zvětšíme počet návratů o jedna (opakování) Příklad: BBS(6) Implementace Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 14 Neúplná stromová prohledávání Omezení počtu návratů 3 Bounded-backtrack search (BBS) Omezený počet návratů (přerušení) návrat do bodů volby, kde už nelze vybrat novou hodnotu nezapočítáváme „omezený počet navštívených listů" 3 Pro úplnost: při neúspěchu zvětšíme počet návratů o jedna (opakování) Implementace M počítáme počet návratů (neúspěchů) při překročení meze se prohledávání ukončí Hana Rudová, Omezující podmínky, 18. listopadu 2019 14 Neúplná stromová prohledávání Omezení hloubky Depth-bounded search (DBS) Omezíme hloubku prohledávaného stromu (přerušení) do dané hloubky stromu se zkouší všechny alternativy ve zbytku stromu se může použít jiná neúplná metoda Pro úplnost: při neúspěchu zvětšíme hloubku prohledávání o jedna (opakování) Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 Neúplná stromová prohledávání Omezení hloubky Depth-bounded search (DBS) Omezíme hloubku prohledávaného stromu (přerušení) do dané hloubky stromu se zkouší všechny alternativy ve zbytku stromu se může použít jiná neúplná metoda Pro úplnost: při neúspěchu zvětšíme hloubku prohledávání o jedna (opakování) Implementace Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 Neúplná stromová prohledávání Omezení hloubky Depth-bounded search (DBS) Omezíme hloubku prohledávaného stromu (přerušení) do dané hloubky stromu se zkouší všechny alternativy ve zbytku stromu se může použít jiná neúplná metoda Pro úplnost: při neúspěchu zvětšíme hloubku prohledávání o jedna (opakování) Implementace * udržujeme pořadové číslo přiřazované proměnné 3 je-li pořadové číslo větší než daná mez, zkouší se pouze jedna alternativa - BBS(O) Hana Rudová, Omezující podmínky, 18. listopadu 2019 15 Neúplná stromová prohledávání Prohledávání s kreditem Credit seaľch (CS) Omezený kredit (počet návratů) pro prohledávání (přerušení) kredit se rovnoměrně dělí mezi alternativní větve prohledávání jednotkový kredit zakazuje možnost volby (hodnoty), tj. pokračujeme pouze bez návratů Pro úplnost: při neúspěchu navýšíme kredit o jedna (opakování) Příklad: CS(12) Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 16 Neúplná stromová prohledávání Prohledávání s kreditem Credit search (CS) Omezený kredit (počet návratů) pro prohledávání (přerušení) kredit se rovnoměrně dělí mezi alternativní větve prohledávání 3 jednotkový kredit zakazuje možnost volby (hodnoty), tj. pokračujeme pouze bez návratů Pro úplnost: při neúspěchu navýšíme kredit o jedna (opakování) Příklad: CS(12) Implementace Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 16 Neúplná stromová prohledávání Prohledávání s kreditem Credit search (CS) Omezený kredit (počet návratů) pro prohledávání (přerušení) kredit se rovnoměrně dělí mezi alternativní větve prohledávání M jednotkový kredit zakazuje možnost volby (hodnoty), tj. pokračujeme pouze bez návratů Pro úplnost: při neúspěchu navýšíme kredit o jedna (opakování) Příklad: CS(12) Implementace M v každém uzlu se nejednotkový kredit (rovnoměrně) rozdělí mezi alternativní podstromy při jednotkovém kreditu se neberou alternativy (tj. při neúspěchu končíme) Hana Rudová, Omezující podmínky, 18. listopadu 2019 16 Neúplná stromová prohledávání Iterativní rozšiřování Iterative broadening IB 3 Omezený maximální počet voleb (hodnot) při každém výběru proměnné (přerušení) 3 v každém bodě volby větvení omezeno konstantou M při překročení max. počtu voleb pokračujeme předchozím bodem volby Úplnost: při neúspěchu zvýšíme povolený počet voleb o jedna (opakování) 3 Implementace Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 17 Neúplná stromová prohledávání Iterativní rozšiřování Iterative broadening IB 3 Omezený maximální počet voleb (hodnot) při každém výběru proměnné (přerušení) 3 v každém bodě volby větvení omezeno konstantou M při překročení max. počtu voleb pokračujeme předchozím bodem volby Úplnost: při neúspěchu zvýšíme povolený počet voleb o jedna (opakování) 3 Implementace M po výběru proměnné umožníme pouze výběr určeného počtu jejích hodnot Hana Rudová, Omezující podmínky, 18. listopadu 2019 17 Neúplná stromová prohledávání Stromová prohledávání a heuristiky Při řešení reálných problémů často existuje nápověda odvozená ze zkušeností s „ručním" řešením problému & Heuristiky - radí, jak pokračovat v prohledávání M doporučují hodnotu pro přiřazení často vedou přímo k řešení M Co dělat, když heuristika neuspěje? M DFS se stará hlavně o konec prohledávání (spodní část stromu) DFS tedy spíše opravuje poslední použité heuristiky než první DFS předpokládá, že dříve použité heuristiky ho navedly dobře Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 18 Neúplná stromová prohledávání Stromová prohledávání a heuristiky Při řešení reálných problémů často existuje nápověda odvozená ze zkušeností s „ručním" řešením problému 3 Heuristiky - radí, jak pokračovat v prohledávání M doporučují hodnotu pro přiřazení často vedou přímo k řešení M Co dělat, když heuristika neuspěje? M DFS se stará hlavně o konec prohledávání (spodní část stromu) DFS tedy spíše opravuje poslední použité heuristiky než první DFS předpokládá, že dříve použité heuristiky ho navedly dobře Pozorování: M počet porušení heuristiky na úspěšné cestě je malý M heuristiky jsou méně spolehlivé na začátku prohledávání než na jeho konci (na konci máme více informací a méně možností) Hana Rudová, Omezující podmínky, 18. listopadu 2019 18 Neúplná stromová prohledávání Zotavení se z chyb heuristiky Heuristika doporučuje hodnotu pro prirazení Diskrepance = porušení heuristiky M použita jiná hodnota, než doporučila heuristika Pozorování: málo chyb heuristiky na cestě k řešení => cesty s méně diskrepancemi jsou prozkoumány dříve 3 Pozorování: chyby heuristiky hlavně na začátku cesty => cesty s diskrepancemi na začátku jsou prozkoumány dříve Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 19 Neúplná stromová prohledávání Omezené diskrepance Limited discrepancy search (LDS) Omezený maximální počet diskrepancí na cestě (přerušení) M cesty s diskrepancemi na začátku jsou prozkoumány dříve Při neúspěchu navýšíme počet povolených diskrepancí o jedna (opakování) 3 tj. nejprve jdeme tak, jak doporučuje heuristika; potom jdeme po cestách s maximálně jednou diskrepancí; pak maximálně se dvěma diskrepancemi, atd. Příklad: LDS-PROBE(l), heuristika doporučuje vydat se levou větví Diskrepance pro nebinární domény 6 54 3 2 1 3 nedoporučené hodnoty se berou jako jedna diskrepance (zde) výběr každé další hodnoty proměnné je jedna diskrepance (tj. třetí hodnota = dvě diskrepance, čtvrtá hodnota = tři diskrepance, ...) Hana Rudová, Omezující podmínky, 18. listopadu 2019 20 Neúplná stromová prohledávání Algoritmus LDS procedure LDS(Variables,Constraints) for D=0 to IVariablesI do % D určuje max. počet povolených diskrepancí R := LDS-PROBE(Variables,{},Constraints,D) if R ^ fail then return R return fail Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 21 Neúplná stromová prohledávání Algoritmus LDS procedure LDS(Variables,Constraints) for D=0 to |Variables| do % D určuje max. počet povolených diskrepancí R := LDS-PROBE(Variables,{},Constraints,D) if R ^ fail then return R return fail procedure LDS-PROBE(Unlabelled,Labelled,Constraints,D) if Unlabelled = {} then return Labelled select X e Unlabelled Values^ := - {values inconsistent with Labelled using Constraints} if Values^ = {} then return fail else select HV e Values^ using heuristic if D>0 then for VV g ValuesHHV} do R := LDS-PROBE(Unlabelled-{X}, Labelled u {X/V}, Constraints, D-l) if R ^ fail then return R return LDS-PROBE(Unlabelled-{X}, Labelled u {X/HV}, Constraints, D) end LDS-PROBE Hana Rudová, Omezující podmínky, 18. listopadu 2019 21 Neúplná stromová prohledávání Omezené diskrepance - zlepšení LDS v každé další iteraci prochází i větve z předchozí iterace, tj. opakuje již provedený výpočet a navíc se v rámci iterace musí vracet do již prošlých částí Improved limited discrepancy search (ILDS) 3 daný počet diskrepancí na cestě (přerušení) s> cesty s diskrepancemi na konci prozkoumány dříve Při neúspěchu navýšíme počet diskrepancí o jedna (opakování) 3 Příklad: ILDS-PROBE(l), heuristika doporučuje vydat se levou větví 1 2 3 4 5 Hana Rudová, Omezující podmínky, 18. listopadu 2019 22 Neúplná stromová prohledávání Algoritmus ILDS procedure ILDS(Variables,Constraints) % analogie LDS(Variables,Constraints) procedure ILDS-PROBE(Unlabelled,Labelled,Constraints,D) Rozdíly od LDS if Unlabelled = {} then return Labelled select X e Unlabelled Values^ := - {values inconsistent with Labelled using Constraints} if Values^ = {} then return fail else select HV e Values^ using heuristic if D<|Unlabelled| then R := ILDS-PROBE(Unlabelled-{X}, Labelled u {X/HV}, Constraints, D) if R ^ fail then return R if D>0 then for VV g ValuesHHV} do R := ILDS-PROBE(Unlabelled-{X}, Labelled u {X/V}, Constraints, D-1) if R ^ fail then return R end ILDS-PROBE Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9 23 Neúplná stromová prohledávání Hloubkou omezené diskrepance 3 ILDS bere cesty s diskrepancemi na konci dříve 3 Depth-bounded discrepancy search (DDS) 3 Diskrepance povoleny pouze do dané hloubky (přerušení) v této hloubce je vždy diskrepance, tj. zabrání se procházení větví z předchozí iterace hloubka zároveň omezuje maximální počet diskrepancí cesty s diskrepancemi na začátku prozkoumány dříve Při neúspěchu navýšíme hloubku o jedna (opakování) Příklad: DDS(3), heuristika doporučuje vydat se levou větví 3 12 3 4 Hana Rudová, Omezující podmínky, 18. listopadu 2019 24 Neúplná stromová prohledávání