3 - Grafy a prohledávání grafu
Připomenutí teorie
Přednáška 4 v oddíle Přednášky.
Grafy
Intuitivně si graf můžeme představit jako množinu bodů (vrcholů), z nichž některé jsou pospojované čarami (hranami) – například mapa měst spojených silnicemi, lidé a jejich přátelství na sociální síti, nebo webové stránky propojené odkazy.
Formálně je graf uspořádaná dvojice \(G = (V, E)\), kde \(V\) je (konečná) množina vrcholů a \(E\) je množina hran mezi nimi. U neorientovaného grafu je hrana neuspořádaná dvojice vrcholů, \(E \subseteq \{\{u, v\} \mid u, v \in V, u \neq v\}\), zatímco u orientovaného grafu (digrafu) je hrana uspořádaná dvojice vrcholů (často nazývaná arc), \(E \subseteq \{(u, v) \mid u, v \in V\}\). Hranám lze navíc přiřadit váhu (cenu) pomocí funkce \(w: E \to \mathbb{R}\) – takový graf se pak nazývá ohodnocený (weighted).
| English | Česky |
|---|---|
Vertex (Node) |
Uzel (Vrchol) |
Edge |
Hrana |
Neighbors (Adjacent vertices) |
Sousedé (sousední vrcholy) |
Degree |
Stupeň (vrcholu) |
Loop |
Smyčka |
Weighted edge |
Ohodnocená hrana (váha/cena hrany) |
Path |
Cesta |
Cycle (undirected graph) |
Kružnice |
Cycle (directed graph) |
Cyklus |
Connected component |
Souvislá komponenta |
Isolated vertex |
Izolovaný vrchol (nesouvislý graf) |
Directed edge (Arc) |
Orientovaná hrana |
In-degree / Out-degree |
Vstupní / výstupní stupeň |
Strom a Les
Strom (Tree) je definován jako souvislý neorientovaný graf bez cyklů.
Les (Forest) je definován jako neorientovaný graf bez cyklů. Souvislé komponenty lesa jsou stromy.
Prohledávání
Prohledávání stromu lze zapsat takto:
function search(data_structure):
while data_structure is not empty
take node from data_structure
process node
add children of node to data_structure
V případě obecného grafu musíme kontrolovat abychom nenavštěvovali uzly vícekrát - přidáváme pouze sousedy, které jsme ještě nepřidali. Za tím účelem si ukládáme množinu viděných uzlů.
Na základě toho, zda je data_structure zásobník (stack) či fronta (queue) pak algoritmus provádí DFS či BFS.
Do šířky - Breadth-first search (BFS)
Využívá frontu (queue), což je first-in first-out (FIFO) datová struktura. To znamená, že při odebrání prvku z fronty vezmeme prvek, co byl přidán první, tedy ten co je ve frontě “nejdéle”. Při prohledávání grafu pomocí BFS roste počet uzlů ve frontě exponenciálně, což je paměťově velmi náročné. Výhoda BFS ovšem je, že v neohodnocených grafech nové uzly nachází s nejkratší cestou.
Do hloubky - Depth-first search (DFS)
Využívá zásobník (stack), což je last-in first-out (LIFO) datová struktura. To znamená, že při odebrání prvku ze zásobníku vezmeme prvek, co byl přidán naposledy. DFS je paměťově méně náročné než BFS, ale nové uzly nemusí nalézt s nejkratší cestou.
Iterativní prohlubování - Iterative deepening depth-first search (IDDFS)
Iterativní algoritmus využívající DFS s omezenou hloubkou, každá iterace zvyšuje maximální povolenou hloubku o 1. IDDFS dodává DFS garanci na nalezení nových vrcholů s nejkratší cestou, ale za cenu delšího běhu celého algoritmu. Asymptoticky je však časová složitost totožná s DFS.
Řešené úlohy
Fronta & Zásobník
Řešená úloha 1:
Co bude obsahovat ds po každém řádku a co vypíše následující program pokud ds je zásobník? A co v případě, že je ds fronta?
ds.push(1)
ds.push(2)
print(ds.pop())
print(ds.peek())
print(ds.peek())
ds.push(3)
print(ds.pop())
print(ds.pop())
print(ds.peek())
ds.push(4)
ds.push(5)
print(ds.pop())
print(ds.pop())Řešení
-
Zásobník: 2, 1, 1, 3, 1, null, 5, 4
-
Fronta: 1, 2, 2, 2, 3, null, 4, 5
Řešená úloha 2:
Strom na obrázku procházíme do šířky. V určitém okamžiku jsou ve frontě uzly (uzly jsou přidávány podle abecedy, konec fronty je vpravo):
-
BGA
-
GA
-
AG
-
AEG
-
GEA
-
AE
Řešení
b) a f)
Další úlohy
⭐ Úloha 5: Najděte (libovolnou) cestu z uzlu E do uzlu A a spočítejte její celkovou cenu. Jaký algoritmus nalezne cestu, obsahující nejméně hran? Jak algoritmicky naleznete cestu s nejmenším součtem cen hran?
hint: Dijkstra
Úloha 6:
Strom na obrázku procházíme do šířky. V určitém okamžku jsou ve frontě následující uzly (čelo fronty je vlevo).
-
D
-
DF
-
FB
-
BGE
-
BAC
-
ABCD
Úloha 7: Formulujte obecný algoritmus, jak z dané posloupnosti obsahů fronty (jako v úloze 3) rekonstruovat pravidelný strom.
Grafy v praxi
Následující úlohy jsou k dispozici také v Jupyter notebooku nebo na Google Colab.
A jejich řešení jsou k dispozici v Jupyter notebooku nebo na Google Colab.
💻Úloha 8: Máte sedm kamenů a šest žab. Výchozí pozice zelených a hnědých žab jsou odděleně na opačných koncích rybníčku. Jediný volný kámen je tedy uprostřed. Vaším úkolem je pak postupně přemístit žáby do výchozích pozic jejich jinobarevných kolegyň.
Počáteční stav
Konečný stav
Pohyb žáby je možný pouze skokem na volný kámen před její pozicí nebo přeskokem přes jednu žábu (libovolné barvy) na volnou pozici za ní. Skok zpět žába nemá dovoleno, takže musíte všechny skoky pečlivě naplánovat.
Použijte prohledávání stavového prostoru řešení.
💻Úloha 9: Hanojské věže
Hlavolam se skládá ze tří kolíků (věží). Na začátku je na jednom z nich nasazeno několik kotoučů různých poloměrů, seřazených od největšího (vespod) po nejmenší (nahoře). Úkolem řešitele je přemístit všechny kotouče na druhou věž (třetí přitom využije jako pomocnou pro dočasné odkládání) podle následujících pravidel:
-
V jednom tahu lze přemístit jen jeden kotouč.
-
Jeden tah sestává z vzetí vrchního kotouče z některé věže a jeho položení na vrchol jiné věže.
-
Je zakázáno položit větší kotouč na menší.
Použijte prohledávání stavového prostoru řešení.
💻Úloha 10: Tři misionáři se vydali na osvětovou misii a jako průvodce mají tři kanibaly. Potřebují překonat řeku, ovšem loďka uveze nejvýše dva lidi. Kanibalové zatím nejsou dostatečně poznamenáni misionářskou osvětou, takže pokud se kdykoli vyskytne na jednom místě více kanibalů než misionářů, budou misionáři snězeni. Jinak však kanibalové spolupracují a udělají, co jim misionáři řeknou. Jak se může celá skupina dostat na druhý břeh?
Použijte prohledávání stavového prostoru řešení.
💻Úloha 11: Máme 3 nádoby o různých objemech. Žádná nádoba na sobě nemá stupnici a nádoby mají dokonce tak roztodivné tvary, že nám znemožňují odhadování množství vody v nich. Stále ale může naměřit i jiné množství tekutiny. Můžeme přelévat obsah jedné nádoby do druhé tak dlouho, dokud nepřelijeme všechno nebo dokud se druhá nádoba nezaplní. Jaký je nejmenší počet přelití, abychom vyřešili následující úlohy? Ve všech variantách je na počátku největší nádoba plná.
-
Máme 3 nádoby o objemech 7l, 5l a 3l. Chceme naměřit 1 litr.
-
Máme 3 nádoby o objemech 7l, 4l a 3l. Přeléváním se chceme dostat do stavu, kdy je v jedné nádobě 3l a ve zbylých dvou po 2 litrech.
-
Máme 3 nádoby o objemech 8l, 5l a 3l. Přeléváním se chceme dostat do stavu, kdy je počáteční množství rozděleno na dva stejné díly.
Použijte prohledávání stavového prostoru řešení.
💻Úloha 12: Zkuste využít BFS nebo DFS na úlohu Safe Passage. Cílem je najít nerychlejší způsob jak projít kolem stráže když máme plášť neviditelnosti, pod který se vejdou jen 2 lidé najednou.