Rozdíly

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

--- courses:a4m33pal:uloha2-2014 [2014/10/08 22:41]
trosman
+++ courses:a4m33pal:uloha2-2014 [2025/01/03 18:28] (aktuální)
@@ Řádek 1: / Řádek 1: @@
 ===== Jak na to =====
+== Můj postup 10/10 (Java) ==
+Myšlenka je následující: budu počítat ITL jakoby pozpátku od nejdelší hran po ty nejkratší. Výhoda je v tom, že jakmile mám spočítanou nejdelší možnou ITL cestu pro hranu s délkou 10, tak kdykoliv přijdu do této hrany z hrany s délkou < 10, tak už rovnou použiju dříve spočítaný výsledek. Vede to defacto na dynamické programování. Je potřeba si hlídat, ze kterého vrcholu jsem do hrany přišel (tj. každá hrana má 2 max ITL - pro každý vrchol-směr).
+  - Seřadím si hrany sestupně.
+  - Vytáhnu nejdelší hranu e.
+  - Spustím prohledávání DFS na e, nejprve směrem z jednoho a pak z druhého jejího vrcholu.
+  - Na začátku DFS se podívám, jestli jsem už tuto hranu nespočítal (v tomto směru).
+  - Pokud ano, rovnou vrátím výsledek.
+  - Pokud ne, spustím DFS rekurzivně na všechny relevantní! sousední hrany (tady pomůže vhodná datová reprezentace grafu).
+  - Tímto v každé DFS iteraci zjistím, jaká je ITL vzdálenost pro aktuální hranu a vrchol, hodnotu si rovnou zapamatuju, abych to nemusel příště znovu procházet.
+  - Maximální ITL mám, když vytáhnu poslední (minimální) hranu.
+== Možné zrychlení ==
+  - Výsledek je někdy možné urychlit podmínkou kontroly nutnosti procházení seznamu seřazených hran. Uvedu na příkladu. Mějme nejvyšší číslo hrany 10. Maximální součet, který lze dosáhnout na základě vstupních omezení je 10 + 9 + .... + 1 = (10 * 11) / 2 = 55. Po obdržení ITL délky pro jednu hranu lze odečíst od tohoto maxima, tedy max - len(e) = zbytek . Je-li len(e) > zbytek a zároveň len(e) je maximum mezi dosud nalezenými výsledky, lze výpočet ukončit a vrátit hodnotu len(e).

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

Nahoru