Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

## Základní grafové algoritmy

V tomto oddíle zavedeme pro odhady časových složitostí algoritmů značení a

Algoritmus (Dijkstrův algoritmus pro hledání nejkratší cesty)

Máme graf jehož hrany jsou ohodnoceny kladnými čísly, tzn. že je dáno zobrazení (Ohodnocení hrany si představujeme jako její délku. Délka cesty je rovna součtu délek jejích hran a vzdálenost vrcholů je rovna nejmenší z délek všech cest spojujících Obyčejná grafová vzdálenost je speciální případ, totiž je-li pro každou hranu ) Hledáme nejkratší cestu z vrcholu do všech ostatních vrcholů.

1. (Inicializace)
   Odhad vzdálenosti u počátečního vrcholu nastavíme na 0, odhady u všech ostatních vrcholů na (známe cestu délky 0 z do délky ostatních cest neznáme). Do množiny vrcholů, u nichž ještě není odhad definitivní, dáme všechny vrcholy kromě .
2. (Volba množiny )
   Do množiny právě zpracovávaných vrcholů uložíme všechny vrcholy z které mají ze všech vrcholů z minimální odhad vzdálenosti; tyto vrcholy z vyřadíme.
3. (Aktualizace odhadů)
   Pro každou hranu kde porovnáme hodnoty a Pokud (přes vrchol vede do kratší cesta, než jsme zatím znali), nastavíme na tuto hodnotu. Po vyčerpání všech takových hran pokračujeme dalším krokem.
4. (Test ukončení)
   Jestliže odhady vzdáleností všech vrcholů v množině jsou algoritmus končí, jinak pokračuje krokem 2.

Po skončení algoritmu je buď (je-li souvislý) nebo obsahuje pouze vrcholy nedosažitelné cestou z vrcholu

??? Algoritmus jsem opravil, i když je to vcelku zbytečné ... kdyžtak to někdo zkontrolujte.

Věta (Složitost Dijkstrova algoritmu)

Lze ho implementovat v čase -- např. pomocí Fibonacciho hald.

Poznámka

Pokud hledáme nejkratší cestu pouze do jednoho zadaného vrcholu můžeme ukončit Dijkstrův algoritmus hned poté, co tento vrchol opustí množinu (jeho vzdálenost se stane definitivní). Výpočet také můžeme urychlit následující heuristikou: máme funkci splňující a pro každou hranu platí (v problémech dopravního spojení to může být např. vzdálenost vzdušnou čarou od cíle). Potom při volbě množiny vybíráme prvky s minimálním součtem dosavadního odhadu a heuristické funkce -- Je-li kvalitní, dá se čekat, že algoritmus najde definitivní vzdálenost do rychleji.

Algoritmus (Prohledávání do šířky)

Máme graf a počáteční vrchol Na začátku položíme v dalších krocích položíme Složitost algoritmu je

Algoritmus (Prohledávání do hloubky)

??? Poměrně jasné, často vede k exponenciální složitosti. Nutno rozlišovat metodu zpracování prvků -- preorder, inorder nebo postorder.

Algoritmus (Hladový (Kruskalův) algoritmus na hledání minimální kostry)

Mějme souvislý graf s ohodnocením hran Hrany máme uspořádány vzestupně podle váhy,

1. Položme
2. Z množiny spočítáme množinu následovně:

Algoritmus se zastaví, pokud má hran. Poslední množina jsou hrany minimální kostry grafu

Věta (Složitost Kruskalova algoritmu)

Při implementaci potřebujeme v podstatě vyřešit úlohu udržování ekvivalence (UNION-FIND): máme množinu vrcholů, na počátku je rozdělena do jednoprvkových tříd ekvivalence. Navrhněte datové struktury a algoritmus, který efektivně vykonává dvě operace:

1. Sjednocení tříd (UNION): učinit dva vrcholy ekvivalentními t.j. nahradit třídy je obsahující jejich sjednocením.
2. Testování ekvivalence (FIND): Pro dané dva vrcholy rozhodnout, zda jsou momentálně ekvivalentní.

V průběhu algoritmu hledání minimální kostry vykonáme operací UNION -- jednu při každém přidání hrany, a operací FIND -- při každém testování, zda přidávaná hrana nevytvoří kružnici. (pozn.: Vrcholy této hrany musí ležet v různých komponentách.)

Řešení: vrcholy mají přiřazenu značku určující třídu ekvivalence, do které patří; a pro každou třídu ekvivalence existuje seznam jejích vrcholů. Testování ekvivalence je pak porovnání dvou značek o složitosti a při sjednocení tříd musím přeznačit a přemístit vrcholy jedné ze tříd, což zabere času. Pokud přeznačujeme vždy menší třídu, vyjde odhad potřebného času

Algoritmus (Jarníkův (Primův) algoritmus na hledání minimální kostry grafu)

Je dán souvislý graf Budeme postupně vytvářet množiny vrcholů a hran, přičemž a kde je libovolně zvolený vrchol. V -tém kroku algoritmu vybereme z množiny hran tu s minimálním ohodnocením (bude to ) a položíme a Pokud žádná taková hrana neexistuje, algoritmus končí, to nastane v -ním kroku a je množina hran minimální kostry grafu. (Kostru tedy začínám budovat od jediného vrcholu a v každém kroku k ní přidám nejkratší z hran mezi vrcholy kostry a zbytkem vrcholů.) Jarníkův algoritmus lze implementovat v čase

Algoritmus (Topologické třídění)

Problém: V orientovaném grafu sestrojte prosté zobrazení tak, aby (Tedy máme očíslovat vrcholy prvními přirozenými čísly tak, aby hrany vedly jen z vrcholu s nižším číslem do vrcholu s vyšším číslem.)
Algoritmus: Nejprve nastavíme čítač na 1. Nalezneme vrchol, do kterého nevede žádná hrana; tento vrchol očíslujeme čítačem a odtrhneme ho od grafu (sestrojíme indukovaný podrgraf) a zvýšíme čítač. Tento krok opakujeme, dokud množina vrcholů grafu není prázdná. Pokud nemůžeme v nějakém kroku nalézt bod, do kterého nevede žádná hrana, nelze graf topologicky setřídit.
Využití: Odpovídají-li vrcholy grafu jednotlivým krokům nějakého postupu a hrany časovým závislostem, které je třeba zachovat, odpovídá topologické setřídění tohoto grafu (jednomu z) pořadí, ve kterém je nutné kroky vykonávat.