navigation
hledat
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/15 17:24] stuchpet |
courses:a4m33pal:uloha2-2014 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 2: | Řádek 2: | ||
| == Můj postup 10/10 (Java) == | == Můj postup 10/10 (Java) == | ||
| - | Myšlenka je následující: budu počítat ITL od jakoby pozadu 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). | + | 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ě. | - Seřadím si hrany sestupně. | ||
| Řádek 12: | Řádek 12: | ||
| - 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. | - 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. | - 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). | ||
| + | |||
| + | |||
| + | |||
| + | |||
