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	m
B	2	■2ll
C	1 2	ll 2 1
D	1 2 3 l=> skok na B	1 ll
E	12 3 1» zpět na D 1	1 2 3 1
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
I
Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9
2
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
I
Vrchol	1	2	3	Vrchol	1	2 3	Vrchol	1	2	31	
A	0				0			0		1	
B		0		1		0	t	A	ol		vybraná barva: o
C	A	0		t	A	0	1	0	Al		důvod konfliktu: AB
D	A	B	0	D	A	B AB	D	A	0	1	
E	A	B	D	t	A	B	t	A	D	ol	
skok zpět (na D) I       skok zpět (na B)l + přenos důvodu chyby (AB) í- přenos důvodu chyby (A) + změna pořadí (B,C)I
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; Unlabelled := 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í Yl 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=9l
3 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
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
* návrat = proměnná, jejíž hodnota se změnila od poslední instanciace YÍ
Mark<BackTo Mark > BackTo
X
I
Y=b
Mark(Y,b)
BackTo(Y)
BackTo(Y) Mark(Y,b)
zde je Y/b v pořaku
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 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 . 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 J
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)<BackTo(X{)
while D[ is not empty
vyber a smaž libovolný ve D[ consistent := true k : = BackTo(Xí) while k < í a consistent
if not Consistent(afc,X{ = v) Mark(X{,v) := k consistent := false el se k := k + 1 if consistent
Mark(X{,v) := i return v return null
Y=b
Mark(Y,b)
I
BackTo(Y)
Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9
9
Další rozšíření backtrackingu
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
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í rychlejil I
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í) I
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 nichl
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í)
M návrat do bodů volby, kde už nelze vybrat novou hodnotu nezapočítáváme „omezený počet navštívených listů"
M 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ů)
M 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í)
I
Implementacel
* 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)
M Implementace
M v každém uzlu se nejednotkový kredit (rovnoměrně) rozdělí mezi alternativní podstromy M 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í)
Implementacel
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
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í
3 Co dělat, když heuristika neuspěje? I
M DFS se stará hlavně o konec prohledávání (spodní část stromu) DFS tedy spíše opravuje poslední použité heuristiky než první 3 DFS předpokládá, že dříve použité heuristiky ho navedly dobřel
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 ' ~ ~ " 1
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 |Variables| do % D určuje max. počet povolených diskrepancí
R := LDS-PROBE(Variables,{},Constraints,D)
if R ^ fail then return R return faill
procedure LDS-PROBE(Unlabelled,Labelled,Constraints,D) if Unlabelled = {} then return Labelled
select X e Unlabelled I 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 s e are h (ILDS)
3 daný počet diskrepancí na cestě (přerušení)
3 cesty s diskrepancemi na konci prozkoumány dříve
Při neúspěchu navýšíme počet diskrepancí o jedna (opakování)
Příklad: ILDS-PROBE(l), heuristika doporučuje vydat se levou větví
1 2 3
I
Hana Rudová, Omezující podmínky, 1 8. listopadu 201 9
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
& ILDS bere cesty s diskrepancemi na konci dříve
Depth-bounded discrepancy search (DDS)
& 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í