Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m33pal:uloha2-2013 [2013/10/06 11:59]
petvana vytvořeno
+++ courses:a4m33pal:uloha2-2013 [2025/01/03 18:28] (aktuální)
@@ Řádek 1: / Řádek 1: @@
-Jedná se o úlohu hledání Eulerovského tahu v zadaném grafu. Nejdříve je potřeba ověřit zda-li je graf opravdu Eulerovský.
+Máte někdo nápad, jaký by mohl být postup řešení?
-Potřebné info naleznete na stránce: http://www.algoritmy.net/article/33838/Cycle-finding
+~~DISCUSSION~~
+Ja to treba delal tak, ze mam algoritmus na hledani nejmensi kostry - Kruskal (hrany ulozene v ArrayListu). Vedle toho mam int[pocetVrcholu] pole, ktere obsahuje pocet stupnu jednotlivych vrcholu. Pak si z mnoziny A vyberu vsechny kombinace K-tic - pro example na strankach zadani (12,13,16,23,26,36) a ulozim do ArrayListu. Ty mi znaci, ktere z tech hran budou mit stupen 1 pri hledani kostry.
+  * Nečíslovaný seznamvysledek = maxInt
+  * while (mamNejakeKombinace K-tic) {
+  *  - vyndej jednu K-tici k
+  *  - hledej kostru, pro vrcholy z k tak, ze do vrcholu z k povede jen jedna hrana (logicky ta nejlevnejsi)
+  *      * - do kostry nepridavej hrany mezi vrcholy A
+  *  - uloz vysledek, pokud je nizsi
+  * }
+  * kdyz vysledek = MaxInt -> print -1
+  * else print vysledek
-Pro reprezentaci dat jsou asi nejlepší spojové seznamy. Pak má algoritmus opravdu lineární asymptotickou složitost.
+/10
+----
-~~DISCUSSION~~
+By bilymare:
+Jak myslíš to nepřidávej do kostry hrany mezi vrcholy z A... vždyt někdy tam hrany být mohou?
+ --- //[[[email protected]|Marek Bílý]] 2013/10/08 19:22//
+By vlcekvl2:
+Podle mě má zde autor na mysli nepřidávat hrany mezi vybranou K-ticí k vrcholů. Poté by totiž nebylo možné vytvořit souvislý graf (což kostra musí být), jelikož tyto vrcholy mohou být maximálně stupně jedna.
+By roziana:
+chci se jen zeptat, jak vytvorit k-tici kombinaci z mnoziny A?
+By milanec:
+jo, přesně, nepřidávat mezi tou K-ticí .. to jsem se přepsal :) Na výběr K-tice z množiny A si musíš vymyslet nějaký šikovný algoritmus, nebo, jako já, najít si něco na netu a přizpůsobit si to svým potřebám :P
+By bilymare:
+  - A na co máš to pole stupnů vrcholů?
+  - já to napsal celé dost objektově. a mám 6 z 10 (3 neustíhám a 1 je špatně).
+  - mám ještě dotaz nepřeteče cena přes velikost intu?
+  - implementoval si union-find stromově nebo projíždíš to pole lineárně?
+ ........           Díky      --- //[[[email protected]|Marek Bílý]] 2013/10/09 21:01//
+By milanec:
+Pole stupňů vrcholů mi pomáhá zjišťovat, jestli jsem u té K-tice nepřekročil jejich stupeň. Velikost intu mi nepřetekla a union find jsem měl polem :)

courses/a4m33pal/uloha2-2013.1381053579.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)

Nahoru