Grafy Flashcards
(6 cards)
Definice Grafu
Graf je definován jako uspořádaná dvojice množiny vrcholů 𝑉 a množin hran 𝐸 (𝐺(𝑉, 𝐸)), kde vrcholy (vertices/nodes) jsou uzly grafu a hrany (edges) jsou spoje mezi vrcholy. Graf
může být jakýkoliv rovinný nebo prostorový útvar, který bude znázorňovat důležité vazby mezi důležitými prvky (vrcholy).
Hrana znázorňuje vztah mezi vrcholy. Rozlišujeme na hrany orientované a neorientované. U orientovaných lze stanovit počáteční a koncový vrchol a u neorientovaného to nelze.
Hrany lze ohodnotit, kdy hodnota může například představovat délku, zátěž atd.
Vrchol je prvek, který chceme spojit s druhým vrcholem pomocí hrany tak, aby nám vznikl graf (ne vždy tyto prvky musí být spojené). Vrchol lze ohodnotit; stupeň grafu je
označení pro počet připojených hran. Stupeň grafu je nejvyšší hodnota ze všech stupňů jeho vrcholů.
Grafy lze dělit dle hran na:
– Neorientované grafy obsahují pouze neorientované hrany. Hrana je obousměrná.
– Orientované grafy obsahují pouze orientované hrany. Hrana je pouze jednosměrná.
– Smíšené grafy obsahují oba typy hran.
Slepé prohledávání - BFS
Slepé (neinformované) vyhledávání v grafu je taková metoda hledání, která nevyužívá žádné informace o vzdálenosti od cíle (např. heuristiky). Používá pouze obecné pravidlo pro prohledávání a neposkytuje žádnou optimalizaci směrem k cílovému stavu.
Prohledávání do šířky (Breadth-First Search)-
Princip: Tento algoritmus postupně prohledává všechny uzly na aktuální úrovni, než přejde na další úroveň.
Implementace: Používá frontu (FIFO – First In, First Out).
Optimálnost: Pokud všechny hrany mají stejnou váhu, BFS najde nejkratší cestu (v počtu hran).
Výhody:
Garantuje nalezení optimální cesty (pokud mají hrany stejnou váhu).
Vhodné pro problémy, kde je řešení v malé hloubce.
Nevýhody:
Exponenciální spotřeba paměti.
Neefektivní pro hluboké nebo velké grafy.
Slepé prohledávání - DFS
Princip: Postupuje do nejhlubšího uzlu po jedné větvi, dokud nenarazí na konec, poté se vrací zpět a pokračuje jinou cestou.
Implementace: Používá zásobník (LIFO – Last In, First Out) nebo rekurzi.
Optimálnost: Není optimální, může najít neoptimální řešení.
Výhody:
Nízké paměťové nároky oproti BFS.
Efektivní pro problémy, kde je řešení hluboko v grafu.
Nevýhody:
Může se snadno zaseknout v nekonečné smyčce (pokud není kontrola cyklů).
Nenajde nejkratší cestu.
Slepé prohledávání - DLS, IDLS
DLS – Depth-Limited Search (prohledávání do omezené hloubky)
Varianta prohledávání do hloubky (DFS) s omezením maximální hloubky, do které se může algoritmus ponořit.
Zavádí limit hloubky L, aby se předešlo zacyklení nebo pádu do nekonečného prostoru.
Nevýhoda: pokud je cíl pod hloubkou L, nebude nikdy nalezen.
Použití: tam, kde známe přibližnou hloubku cílového stavu nebo chceme omezit výpočetní náročnost.
IDDFS – Iterative Deepening Depth-First Search (iterativní prohledávání do hloubky)
Kombinuje výhody BFS (Breadth-First Search) a DFS (Depth-First Search).
Spouští DLS opakovaně s limitem hloubky: nejprve L=0, pak L=1, L=2, atd.
Každá iterace znovu prohledá celý strom až do dané hloubky.
Je kompletní (najde řešení, pokud existuje) a optimální (pro uniformní cenu kroků).
Výhody:
Malá paměťová náročnost (jako DFS)
Kompletnost a optimalita (jako BFS)
Nevýhoda:
Částečně redundantní výpočty (opakované prohledávání), ale v praxi je tento overhead malý.
Dijkstrův algoritmus
Dijkstrův algoritmus je algoritmus pro nalezení nejkratší cesty z jednoho uzlu grafu do všech ostatních uzlů. Funguje v ohodnocených grafech s kladnými vahami hran. Patří mezi neinformované algoritmy, protože nepoužívá heuristiky.
využívá prioritní frontu a seznam navštívených vrcholů.
Z prvního vrcholu se přidají všechny sousední vrcholy s jejich hodnotou hrany do prioritní fonty.
Z prioritní fronty se vždy vezme nejmenší prvek.
Z nejnižšího vrcholu se prozkoumají znovu sousedé, ale tentokrát se nepoužije pouze vzdálenost mezi nimi, ale přičte se už i vzdálenost k aktuálnímu vrcholu.
Tak se bere dokud se nedorazí k cílovému vrcholu.
Výhody:
Najde optimální řešení pro grafy s kladnými vahami.
Funguje pro všechny typy souvislých grafů (neorientované, orientované).
Je efektivní pro řídké grafy díky prioritní frontě.
Nevýhody:
Neumí pracovat se zápornými hranami (Bellman-Fordův algoritmus je lepší volba).
U hustých grafů může být pomalejší než jiné algoritmy.
A*
A* je heuristický vyhledávací algoritmus, který se používá k nalezení nejkratší cesty v grafu. Je vylepšením Dijkstrova algoritmu, protože kromě vzdálenosti od počátečního uzlu zohledňuje také odhady vzdálenosti k cíli. Díky tomu je A* často rychlejší než Dijkstra, pokud se použije správná heuristika.
A* pracuje podobně jako Dijkstra, ale vybírá uzly na základě následující hodnotící funkce
Postupuje se stejně jako u Dijktrova algoritmu, akorát se sčítá vzdálenost s hodnotou heuristiky uzlu. Dle této sečtené hodnoty je vybrán další navštívený prvek z prioritní fronty.
Výhody:
Rychlejší než Dijkstra, pokud má dobrou heuristiku.
Najde optimální cestu, pokud je heuristika admissivní.
Flexibilní – lze použít různé heuristiky.
Nevýhody:
Potřebuje správnou heuristiku – špatná heuristika může způsobit neefektivní běh.
Vyšší paměťové nároky než Dijkstra, protože udržuje více stavů.
