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:26] stuchpet |
courses:a4m33pal:uloha2-2014 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řá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). | ||
| + | |||
| + | |||
| + | |||
| + | |||
