navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:popis-alg [2009/11/04 00:13] dundee |
— (aktuální) | ||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | ====== Popis algoritmu hledání minimální kostry orientovaného grafu ====== | ||
| - | Právě se mi podařilo získat 6/10, tak snad už mám řešení a pochopení natolik dobré, abych se zde mohl podělit. | ||
| - | |||
| - | V dalším textu bude detailně popisován algoritmus sepsaný Ali Tofighem v Optimum Branchings | ||
| - | and Spanning Aborescences (odkaz je na stránce úkolu - algorithm-description.pdf). Pokusím se popsat i optimální implementaci datových struktur. Nebudu zde opakovat to, co je v anglickém originálu naprosto zřejmé. | ||
| - | |||
| - | ===== Datové struktury ===== | ||
| - | |||
| - | ==== Disjunktní množina ==== | ||
| - | V algoritmu potřebujeme union-find množiny, které budou reprezentovat slabé a silné komponenty grafu a umožní nám snadno provádět jejich slučování. Strukturu je možné navrhnout například jako pole, kde index prvku odpovídá číslu vrcholu/komponenty a hodnota prvku odpovídá reprezentantu množiny. Funkce find pak vrací reprezentanta množiny, union slučuje dvě množiny. Je potřeba, aby find snižoval výšku stromu množiny. Snad jasné. | ||
| - | |||
| - | ==== Binomická halda ==== | ||
| - | Každý vrchol grafu si musí pamatovat množinu hran, které do něj vstupují. Z těchto hran bude vybírána vždy ta nejmenší. Dále bude potřeba umět dvě takovéto množiny efektivně sloučit (log n) a v konstantním! čase zvýšit váhu všech hran. Tohoto nejlépe docílíme právě upravenou binomickou haldou. | ||
| - | |||
| - | Nejtěžší je pravděpodobně zvyšování váhy všech vah. To lze provést tak, že přírůstek vah uložíme v prvním kroku jen do pomocné struktury haldy a dále tuto hodnotu šíříme haldou až v případě potřeby (odebírání vrcholu, slučování dvou hald). Každý uzel haldy si bude pamatovat kromě své váhy/klíče i přírůstek. Přitom je vhodné, aby platilo, že celková váha nějakého uzlu je součet vah jeho rodičů (včetně té pomocné struktury haldy), jeho přírůstku a jeho vlastní váhy. | ||
| - | |||
| - | Propagace do nižších pater haldy probíhá vždy, když by se narušily správné celkové hodnoty vah uzlů. Jedním příkladem je odebírání minima z haldy. Pokud uzel minima obsahuje přírůstek, jeho pouhým odebráním bychom o něj přišli. Musíme tedy tento přírůstek propagovat do jeho potomků (o jedno patro níž). Další příklad je sloučení dvou hald. V takovém případě nemůžeme ponechat přírůstek v pomocné proměnné...atd. Doporučuju dobře otestovat, je to celkem fuška. | ||
| - | |||
| - | ==== Les ==== | ||
| - | Hrany s minimálními váhami, které budeme postupně vybírat si musíme někam ukládat, a to nejlépe tak, abychom nějakým snadným způsobem získali z této struktury výslednou minimální kostru. K tomuto účelu je potřeba připravit kořenový les, kde jednotlivými uzly lesa jsou hrany zadaného grafu. Je potřeba připravit se na to, že uzly které už v lese budou, bude občas potřeba přesunout v lese jinam - přesněji přidat je jako potomky jinému uzlu. A rozhodně není možné procházet les a hledat jestli v něm uzel (hrana grafu) náhodou už není :) Je potřeba konstantní čas. | ||
| - | |||
| - | Další lahůdkou je, že na konci algoritmu se bude les prořezávat. Budou se odstraňovat cesty (tedy uzly na cestě) vedoucí od nějakého listu lesa až do kořene, přičemž potomci odstraněných uzlů stoupají vzhůru (stávají se z nich kořeny lesa). | ||
| - | |||
| - | ===== Algoritmus ===== | ||
| - | |||
| - | <code> | ||
| - | foreach (V as node) { | ||
| - | W.makeset(node); //na zacatku jsou vsechny uzly samostatnymi slabymi komponentami | ||
| - | S.makeset(node); //na zacatku jsou vsechny uzly samostatnymi silnymi komponentami | ||
| - | min[node] = node; | ||
| - | } | ||
| - | roots := V; | ||
| - | |||
| - | while ((r = roots.pop()) != NULL) { | ||
| - | |||
| - | /* vrati nejmensi hranu, pokud hrana smeruje z jedne silne komponenty do stejne silne komponenty, zahodime ji a najdeme dalsi minimalni. Hrany tedy po nalezeni z haldy hned mazeme. Kdyz je halda prazdna a zaroven uz mame ulozeny v "root" koren, znamena to, ze ma graf dva koreny a je tedy neresitelny. Kdyz je halda prazdna a nemame jeste koren, ulozime ho (root = r;) */ | ||
| - | edge = incoming[r].min(); | ||
| - | } | ||
| - | </code> | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | ~~DISCUSSION~~ | ||
| - | |||
