Prohledávání do hloubky: Porovnání verzí

Smazaný obsah Přidaný obsah
Chobot (diskuse | příspěvky)
m robot přidal: ko:깊이 우선 탐색
→‎Vlastnosti algoritmu: opravena chyba -- stromové hrany netvoří strom *nejkratších* cest.
Řádek 11:
Algoritmus je úplný (vždy najde řešení, tzn. určitý cílový vrchol, pokud existuje), ale není optimální (pokud graf není [[strom (graf)|strom]], nemusí najít nejkratší možnou cestu k cíli). Algoritmus dokáže prohledat pouze souvislé komponenty grafu, není tedy vždy zajištěno ani to, že algoritmus projde všechny uzly.
Předpokládáme, že graf má uzly ohodnocené číselnými hodnotami, které budeme dále používat zejména pro výběr jakým směrem, přes jaký uzel z následníků daného uzlu se má algoritmus vydat. V tomto algoritmu totiž panuje pravidlo výběru postupně právě těch následníků daného uzlu v pořadí hodnot, kterými jsou uzly hodnoceny. Od nižšího ohodnocení k vyšším.
V grafu se vyskytují celkem čtyři typy hran. Jsou to hrany stromové, příčné, zpětné a dopředné. Algoritmus prochází hranami a postupuje tím stylem, že se snaží projít nejprve co nejhlouběji do nitra (z tohoto principu se také tomuto algoritmu říká prohledávání do hloubky) aneb nejdál, co to jen jde. Tyto hrany, po kterých algoritmus prochází takto "co nejdál" grafem, se nazývají hrany stromové. Z těchto hran je poté vytvořen strom nejkratších cest z kořene (počátečního uzlu) do všech orientovaně dosažitelnývh vrcholů. Když algoritmus zkouší nalézt další FRESH uzly po dalších hranách, tak se stane, že místo aby tento uzel měl stav FRESH, tak bude OPEN. Tuto hranu poté pojmenujeme jako zpětnou. Tuto zpětnou vazbu vlastně ani nevyužijeme, jelikož díky ní pouze zjistíme, že dále pokračovat již není možné a musíme se algoritmem vracet zpět a zkoušet cestu přes jinou hranu vedoucí k dalšímu následníkovi. Jestliže narazíme z uzlu OPEN na uzel CLOSE, jedná se o příčnou či o dopřednou hranu. Mezi těmito dvěma typy hran rozlišujeme podle časové značky otevření uzlu. Jestliže se dostaneme z uzlu OPEN s časovou značkou otevření například 10 do uzlu CLOSE přes dopřednou hranu, bude platit, že tento CLOSE uzel bude mít časovou značku otevření vyšší než 10. Dopředná hrana spojí uzel s nižší časovou značkou otevření s uzlem s vyšší značkou otevření. Jestliže se stane tato situace přesně opačně, že totiž hrana spojí uzel s vyšší časovou značkou otevření s uzlem s nižší značkou otevření, bude se jednat o hranu příčnou. Stejně jako hranu zpětnou, tak ani poslední dvě zmiňované hrany ve výsledném stromu nejkratších vzdáleností nevyužijeme a slouží nám pouze jen pro to, abychom zjistili, že se máme vydat jinou cestou.
 
== Obecná implementace v pseudokódu ==