Prohledávání do hloubky (DFS) - rekurzivně
l function df s(G, v) mark v as visited preVisit(v) for (v, w) g E(G) do edgeVisit (\/, w) if w not visited then |^ df s(G, w)
postVisit(v)
Prohledávání do sirky (BFS)
l function bf s(G, v) Q <— empty queue mark v as visited enqueue(Q, v) while Q not empty do v <— dequeue(Q) vertexVisit(v) for (v, w) g E(G) do edgeVisit (\/, w) if w not visited then mark w as visited enqueue (Q, w)
Prohledávání do sirky (BFS)
l function bf s(G, v) Q <— empty queue mark v as visited enqueue(Q, v) while Q not empty do v <— dequeue(Q) vertexVisit(v) for (v, w) g E(G) do edgeVisit (\/, w) if w not visited then mark w as visited enqueue (Q, w)
► Co se stane když vyměníme frontu za zásobník?
Tzv. „obecné schéma" prohledávání grafu
l function search(G,\/) B 4- empty bag put (6, v)
while B not empty do v <— get (6) if v not visited then mark v as visited vertexVisit(v) for (v, w) g do edgeVisit (\/, w) put (6, w)
► Je toto tvrzení pravdivé? „Pokud je bag fronta, je toto schéma BFS, pokud je bag-zásobník, je toto schéma DFS."
rohledávánř do hloubky (DFS) - iterativně
Chceme skutečné iterativní DFS
► musí mít všechny vlastnosti DFS, tj. zejména postorder
► potřebujeme simulovat rekurzi pomocí zásobníku
► co všechno je na zásobníku rekurze?
Prohledávání do hloubky (DFS) - iterativně
Chceme skutečné iterativní DFS
► musí mít všechny vlastnosti DFS, tj. zejména postorder
► potřebujeme simulovat rekurzi pomocí zásobníku
► co všechno je na zásobníku rekurze?
Varianta 1: indexy následníků (iterátory)
► s každým prvkem v zásobníku si pamatujeme index
► ten určuje, které následníky ještě musíme zpracovat
► použitelnost závisí na reprezentaci grafu
► index může být obecnější iterátor
► použitelné pro explicitní grafy (matice sousednosti, seznam následníků)
► i pro některé implicitní grafy
Prohledávání do hloubky (DFS) - iterativně
Chceme skutečné iterativní DFS
► musí mít všechny vlastnosti DFS, tj. zejména postorder
► potřebujeme simulovat rekurzi pomocí zásobníku
► co všechno je na zásobníku rekurze?
Varianta 1: indexy následníků (iterátory)
► s každým prvkem v zásobníku si pamatujeme index
► ten určuje, které následníky ještě musíme zpracovat
► použitelnost závisí na reprezentaci grafu
► index může být obecnější iterátor
► použitelné pro explicitní grafy (matice sousednosti, seznam následníků)
► i pro některé implicitní grafy
Varianta 2: bez iterátorů
► u některých implicitních grafů nejsme schopni rozumně iterovat přes následníky
► vygenerujeme všechny následníky a uložíme je na zásobník
► dva typy prvků na zásobníku (vrcholy a hrany)
Prohledávání do hloubky (DFS) - iterativně
1 function df s(G, v)
2 S <— empty stack
3 mark v as visited
4 preVisit (\/)
5 push(S, (\/, 1))
6 while S not empty do
7 (v, k) <r- pop(S)
8 if k < number of v s successors in G then
9 push(S, (v, k + 1))
10 w <— kth successor of v in G
11 edgeVisit (w)
12 if w not visited then
13 mark w as visited
14 preVisit (w)
15 push(S, (w, 1))
16
17
else
|^ postVisit(v)
Prohledávání do hloubky (DFS) - iterativně (bez iterátorů)
i function df s(G, v)
2
3
4
5
6
7
8
9 10
S <— empty stack expand(G, S, v) while S not empty do top <— pop(S)
if top is an edge (\/, w) then edgeVisit (\/, w)
if w not visited then expand(G, S, w) else
|^ postVisit(top)
ll function expand(G, S, v) mark v as visited preVisit(v) push(S,v) for (v, w) g do L push(S, (v, i/i/))
12
13
14
15
16
Hledání nejkratších cest - Dijkstrův algoritmus
l function dijkstra(G, s)
P <— empty priority queue
d[s] <r- 0
for v e V{G) do
if v    s then d[v] <— oc insert (P, (v, c/[v]));
while P not empty do v <— extractMin(P) mark v as closed for (v, w) g f(G) do
if w not closed and c([v] + 5(v, w) < d[w] then d[w] <- d[v] + 5(v, w) decreaseKey(P, 1/1/, c/[i/i/])
Hledání nejkratších cest - Dijkstrúv algoritmus
l function dijkstra(G, s)
P <— empty priority queue
d[s] <r- 0
insert (P, (s,0)) while P not empty do v <— extractMin(P) mark v as closed for (v, w) g E (G) do
if w not closed and d [v] + 5(v, w) < d[w] then d[w] <- d [v] + S(v, w) if w is in P then
decreaseKey(P, 1/1/, d[w]) else
insert(P, (1/1/, cŕ[w]))
► Vkladáme do prioritní fronty vrcholy až za běhu.
Hledání nejkratších cest - Dijkstrúv algoritmus (modifikovaný)
l function dijkstra(G, s)
P <— empty priority queue
d[s] <r- 0
insert (P, (s,0)) while P not empty do v <— extractMin(P) for (v, w) g E (G) do
if d [v] + S(v, w) < d[w] then d[w] <- d [v] + S(v, w) if w is in P then
decreaseKey(P, 1/1/, d[w]) else
insert(P, (1/1/, cŕ[w]))
► Je tento algoritmus korektní? Jakou má časovou složitost?
Hledání nejkratších cest - A*
Motivace
► často chceme hledat pouze cestu ze startu do cíle
► preferujeme cesty, které vypadají, že vedou směrem k cíli
Heuristika
► pro každý vrchol máme hodnotu h(v), která je odhadem vzdálenosti k cíli
► přípustná: h(v) nesmí být větší než skutečná vzdálenost k cíli
► konzistentní: pro každé v, w platí: h(v) < 8(v, w) + h(w)
K zamyšlení:
► Je každá konzistentní heuristika přípustná?
► Je každá přípustná heuristika konzistentní?
Algoritmus A*
► varianta Dijkstrova algoritmu: místo d[v] je klíčem d[v] + h(v)
Hledání nejkratších cest - A*
l function aStar(G,s, ř)
P <— empty priority queue
d[s] <r- 0
insert (P, (s,0 + /?(s))) while P not empty do v <— extractMin(P) if v = t then stop for (v, w) g f(G) do
if d[v] + 5(v, w) < d[w] then d[w] <- d[v] + 5(v, w) if w is in P then
decreaseKey(P, 1/1/, cf[w] + else
insert (P, (1/1/, cf[w] +
► Kterou podmínku musíme na heuristiku klást, aby algoritmus korektní? Jakou má složitost?
Hledání nejkratších cest
Zajímavé odkazy
http://theory.Stanford.edu/^amitp/GameProgramming/
http://www.redblobgames.com/pathfinding/a-star/
introduction.html
http://zerowidth.com/2013/05/05/
jump-point-search-explained.html
(poslední odkaz vysvětluje algoritmus Jump Point Search, heuristiku pro vylepšení algoritmu A*)