navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:uloha5-2013 [2013/11/04 18:34] roziana [Řešení pomocí generování koster] |
courses:a4m33pal:uloha5-2013 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 7: | Řádek 7: | ||
| Přečtěte si co je to [[http://en.wikipedia.org/wiki/Kirchhoff's_theorem|Kirchoffuv teorem]] Ze zadání si vytvořím dvě matice - matici stupně vrcholů a matici sousednosti. Od matice stupně vrcholů odečtu matici sousednosti a dostanu [[http://en.wikipedia.org/wiki/Laplacian_matrix|Laplacianskou matici]] Kirchhoffuv teorem říká, že když od této matice odeberu jeden řádek a sloupec (vytvořím její kofaktor), dostanu matici jejíž determinant se rovná počtu stromů daného grafu. Při volbě algoritmu na výpočet determinantu rovnou vynechte ty rekurzivní a zkuste implementovat LU dekompozici, či obyčejnou Gaussovku. | Přečtěte si co je to [[http://en.wikipedia.org/wiki/Kirchhoff's_theorem|Kirchoffuv teorem]] Ze zadání si vytvořím dvě matice - matici stupně vrcholů a matici sousednosti. Od matice stupně vrcholů odečtu matici sousednosti a dostanu [[http://en.wikipedia.org/wiki/Laplacian_matrix|Laplacianskou matici]] Kirchhoffuv teorem říká, že když od této matice odeberu jeden řádek a sloupec (vytvořím její kofaktor), dostanu matici jejíž determinant se rovná počtu stromů daného grafu. Při volbě algoritmu na výpočet determinantu rovnou vynechte ty rekurzivní a zkuste implementovat LU dekompozici, či obyčejnou Gaussovku. | ||
| + | By Milan: Narážím na zarážející problém - když odeberu z LaplacianM první sloupec a první řádek, dostanu 5/10. Odeberu-li poslední sloupec a řádek, dostanu 6/10. Nevíte, kde může být problém? Nesetkal jste se s tím někdo? Dělám to přes Gaussovku. | ||
| + | By Rosion: Ja odeberu posledni radek a posledni sloupec a v poradku a pouzivam LUDecomp. | ||
| + | |||
| + | By Lukesja7: Odebiram prvni radek a prvni sloupec, pouzivam gausovku > 10/10 Mozna spatne zaokrouhleni? | ||
| + | |||
| + | By stuchpet: Opravdu je to nejrychlejsi a asi nejrychleji naprogramovatelne reseni. Implementace pomocí (float) matice v Jave a Doolittlova algoritmu na LU rozklad projde bezpecne na 10/10. BTW. Determinant lze pocitat uz behem LU faktorizace. | ||
| ===== Řešení pomocí generování koster ===== | ===== Řešení pomocí generování koster ===== | ||
| Úloha byla nejspíše myšlena tak, abychom stromy generovali, protože to se zrovna probírá. Já jsem to řešil první způsobem, prosím ať někdo doplní tento. | Úloha byla nejspíše myšlena tak, abychom stromy generovali, protože to se zrovna probírá. Já jsem to řešil první způsobem, prosím ať někdo doplní tento. | ||
| - | Pospup algoritmu | + | ** |
| - | + | Návrh řešení** | |
| - | - Generate graph conditates | + | |
| - | * All spanning trees have |V|-1 egdes, where V is the number of nodes | + | |
| - | * So we have to generate all (|V|-1)-element subsets of the set of edges. Each subset represents then a canditate graph | + | |
| - | - For each generated condidate, test if it is a spanning tree | + | |
| - | To be a spanning tree, the candidate graph must: | + | |
| - | * be connected | + | |
| - | * contain no cycle | + | |
| - | * and contain all nodes of the original graph | + | |
| + | - **Generate graph conditates** | ||
| + | * all spanning trees have |V|-1 egdes, where V is the number of nodes | ||
| + | * so we have to generate all (|V|-1)-element subsets of the set of edges. Each subset represents then a canditate graph | ||
| + | - **For each generated condidate, test if it is a spanning tree** | ||
| + | * if a condidate graph is connected, | ||
| + | * contains no cycle | ||
| + | * and contains all nodes of the original graph | ||
| + | * then it is a ST | ||
| + | * | ||
| + | By Petr: hint pro Javu - generoval jsem subsety hran pomoci permutaci binarniho cisla delky |Pocet hran|, ktere obsahovalo |V-1| jednicek. Reprezentace jako retezec charu postacovala jen na 9/10 kvuli casovemu limitu na predposlednim testu. Vyresil jsem to zmenou reprezentace binarky na pole indexu oznacujici primo index, kde je v binarce jednicka. Zrychleni neni zas tak velke, ale na 10/10 uz to stacilo. Nestiha to pouze public test 03. | ||
| ~~DISCUSSION~~ | ~~DISCUSSION~~ | ||
