Toto je starší verze dokumentu!


Jak na to

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).

  1. Seřadím si hrany sestupně.
  2. Vytáhnu nejdelší hranu e.
  3. Spustím prohledávání DFS na e, nejprve směrem z jednoho a pak z druhého jejího vrcholu.
  4. Na začátku DFS se podívám, jestli jsem už tuto hranu nespočítal (v tomto směru).
  5. Pokud ano, rovnou vrátím výsledek.
  6. Pokud ne, spustím DFS rekurzivně na všechny relevantní! sousední hrany (tady pomůže vhodná datová reprezentace grafu).
  7. 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.
  8. Maximální ITL mám, když vytáhnu poslední (minimální) hranu.
courses/a4m33pal/uloha2-2014.1413386699.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)
Nahoru
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0