AG1cv11 PDF

11. cvičení AG1 Minimální kostry Nejkratší cesty Chyby hlaste na [email protected] Toto není oficiální studijní materiál  Jarníkův algoritmus 7 21 1 8 9 33 35 s...

11. cvičení AG1 Minimální kostry Nejkratší cesty Chyby hlaste na [email protected] Toto není oficiální studijní materiál  Jarníkův algoritmus 7 21 1 8 9 33 35 s 1 3 5 11 2 2 1 10 42 32 0 2 4 6  7 7 21 21 1 8 1 8 9 33 35 9 33 35 s 1 3 5 s 1 3 5 11 2 2 1 11 2 2 1 10 42 32 10 42 32 0 2 4 6 0 2 4 6 7 21 7 1 8 21 1 8 9 33 35 s 1 3 5 9 33 35 s 1 3 5 11 2 2 1 11 2 2 1 10 42 32 0 2 4 6 10 42 32 0 2 4 6  7 7 21 21 1 8 1 8 9 33 35 9 33 35 s 1 3 5 s 1 3 5 11 2 2 1 11 2 2 1 10 42 32 10 42 32 0 2 4 6 0 2 4 6 7 21 7 1 8 21 1 8 9 33 35 s 1 3 5 9 33 35 s 1 3 5 11 2 2 1 11 2 2 1 10 42 32 0 2 4 6 10 42 32 0 2 4 6 Kruskalův algoritmus 7 21 1 8 9 33 35 s 1 3 5 11 2 2 1 10 42 32 0 2 4 6  7 7 21 21 1 8 1 8 9 33 35 9 33 35 s 1 3 5 s 1 3 5 11 2 2 1 11 2 2 1 10 42 32 10 42 32 0 2 4 6 0 2 4 6 7 21 7 1 8 21 1 8 9 33 35 s 1 3 5 9 33 35 s 1 3 5 11 2 2 1 11 2 2 1 10 42 32 0 2 4 6 10 42 32 0 2 4 6  Změna váhy hrany Jak se změní minimální kostra, pokud změníme váhu jedné hrany?  Řešení Pokud zvýšíme váhu hrany, která není v kostře, tak nijak. Pokud snížíme váhu hranu, která je v kostře, tak nijak. Pokud snížíme váhu hrany, která není v kostře, tak ji přidáme do kostry a pomocí DFS najdeme kružnici. Z této kružnice odstraníme nejdražší hranu. Pokud zvýšíme váhu hrany v kostře, tak ji odstraníme z kostry. Pomocí BFS určíme, které vrcholy v kostře patří do které komponenty. Projdeme všechny hrany v kostře a přidáme nejlevnější, která spojuje obě komponenty.  Záporné hrany 1) Lze Jarníkův a Kruskalův algoritmus použít na hledání kostry se zápornými hranami? 2) Lze se záporných hran zbavit tak, že k nim přičteme nějaké velké číslo K?  Řešení 1) Ano lze to, protože porovnáváme relativní pořadí vah mezi sebou a na konkrétních hodnotách nám nezáleží. 2) Přičtením K ke každé hraně nezměníme relativní pořadí vah a tento postup tedy také funguje. Od váhy je pak třeba odečíst číslo (|V|-1) * K pro získání váhy původní kostry. UnionFind s „keříky“ u Kruskala 7 21 1 8 9 33 35 s 1 3 5 11 2 2 1 10 42 32 0 2 4 6  s 0 1 2 3 4 5 6 7 Řešení s 0 3 5 s 0 1 3 5 7 1 4 6 7 2 4 6 2 s s 3 s 3 5 5 7 1 0 3 7 1 0 4 7 1 0 4 6 2 4 5 2 6 2 6 Dijkstrův algoritmus 0 s s 1 -2 0 s s s 5 -3  Řešení 0 0 ∞ 0 0 0 0 0 0 s s s s s s 1 1 1 -2 0 -2 0 -2 0 ∞ ∞ ∞ -2 ∞ ∞ -2 3 ∞ s s s s s s s s s 5 5 5 -3 -3 -3 0 0 0 0 0 0 s s s s 1 1 -2 0 -2 0 -2 0 1 -2 0 -3 s s s s s s 5 5 -3 -3 Simple Bellmann-Ford 0 s s 1 -2 0 s s s 5 -3  Náhodné pořadí hran: 1, -3, 5, 0, -2, 0 Řešení 0 0 ∞ 0 0 ∞ 0 0 ∞ 0 0 ∞ 0 0 ∞ s s s s s s s s s s 1 1 1 1 -2 0 -2 0 -2 0 -2 0 -2 0 -2 ∞ 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ s s s s s s s s s s s s s s s 5 -3 5 -3 5 -3 5 -3 5 -3 0 0 0 s s 1 -2 0 -2 ∞ ∞ 0 0 0 0 0 0 0 0 0 0 0 0 s s s s s s s s s s s 5 -3 1 1 1 1 0 0 0 -2 0 -2 0 -2 0 -2 0 s s -2 ∞ 1 -2 ∞ 1 -2 3 1 -2 0 1 1 s s s s s s s s s s s s -2 0 5 -3 5 -3 5 -3 5 -3 -2 0 1 s s s 5 -3 0 0 0 s s 0 0 0 0 0 0 0 0 0 1 s s s s s s -2 0 1 1 1 Iterace 4 a 5 už nic -2 0 1 -2 0 -2 0 0 nezmění s s s -2 0 -3 -2 0 -3 -2 0 -3 5 -3 s s s s s s s s s 5 -3 5 -3 5 -3  Nejkratších cest je exponenciálně mnoho Nalezněte graf o n vrcholech, ve kterém pro nějaké dva vrcholy platí, že mezi nimi existuje 2Ω(𝑛) nejkratších cest.  Řešení s c 𝑛−1 Cest bude 2 3 = 2Ω(𝑛)  Nejkratší cesty v DAGu Jak naleznete nejkratší cestu mezi dvěma vrcholu v acyklickém orientovaném grafu?  Řešení Vrcholy topologicky uspořádáme. Postupně projdeme všechny vrcholy tak, jak jdou podle uspořádání. Pokud z něj vede hrana do vrcholu, který má v sobě momentálně větší hodnotu, tak ho relaxujeme. Složitost je O(n+m), protože každý vrchol zpracováváme a hranu navštívíme jen jednou. Korektnost: Algoritmus vrátí nejkratší cestu, protože jednou zpracovaný vrchol nemůže svou cestu již změnit. Pokud by existovala kratší cesta, než kterou algoritmus vrátí, tak bychom se museli do nějakého vrcholu vracet => existence cyklu.  Záporné hrany Je možné se zbavit záporných hran tak, že ke každé přičteme nějakou velkou konstantu K, jako tomu bylo u koster?  Řešení NE!! – Penalizujeme tím levné cesty přes více hran. Příkladem může být následující graf 100 s c 1 1 1 1 1 K = 1000 1100 s c 1001 1001 1001 1001 1001  Poslední příklad :( Mějme mapu města, kde nějakou dobu projíždíme silnice a nějakou dobu čekáme na křižovatkách. Silnice jsou ohodnocené hrany a křižovatky ohodnocené vrcholy. Chceme najít nejkratší cestu z jednoho vrcholu do jiného. Jak za pomocí Dijkstrova algoritmu vyřešit tento problém?  Řešení Podrozdělení vrcholů - Každý vrchol rozdělím na dva, kde z vrcholu 1 povede hrana do vrcholu 2 s váhou daného vrcholu. Všechny hrany vedoucí do vrcholu v původním grafu povedou do vrcholu 1 a všechny vycházející hrany povedou z vrcholu. Přidal jsem n vrcholů a n hran – Složitost se asymptoticky nezmění. 5 5 8 8 3 2 3 6 2 6 v1 v2 10 1 10 1  Naučte se na zkoušku! Domácí úkol Kdybyste měli s něčím problém nebo byste chtěli něco znovu vysvětlit, tak napište. Až 20b Marast, 30b velký test a 10b nepovinná ústní 3 pokusy Vyplňte anketu 0b  Děkuji za pozornost Pěkné svátky, ať se daří a „Nechť máte pod svým vánočním stromem velkou haldu dárků.“