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/03 23:42] 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. | ||
| - | |||
| - | ===== 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 ==== | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | ~~DISCUSSION~~ | ||
| - | |||
