KCKurzy - Jak udělat zkoušku z EMM 1
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
Příklad 1: Turista vyjíždí z Catanzara a chce postupně navštívit všechna města v tabulce a vrátit se
zpátky. Naplánujte trasu tak, aby ujel co nejméně kilometrů. Vzájemné vzdálenosti mezi městy jsou v
tabulce
Řešení 1: Vogelova metoda (VAM)
Krok 1: Vypočítáme si řádkové a sloupcové diference (rozdíl dvou nejmenších vzdáleností v daném
řádku či sloupci – viz VAM metoda u dopravní úlohy)
41
Krok 2: Vybereme nejmenší sazbu v řadě s maximální diferencí – tuto trasu vybereme do okruhu
(trasa Scalea – Cosenza). Škrtáme řádek a sloupec u vybrané trasy a trasu, která předčasně uzavírá
okruh (u izolovaných tras je to pouze cesta zpátky: Cosenza - Scalea).
Krok 3: Přepočítáme opět diference již bez vyškrtnutého řádku a sloupce a volíme další trasu
(Crotone – Catanzaro). Škrtáme opět řádek a sloupec u vybrané trasy a zpětnou trasu, která
předčasně uzavírá okruh (Catanzaro - Crotone.
Krok 4: Přepočítáme opět diference a volíme další trasu (Reggio-Tropea). Škrtáme opět řádek a
sloupec u vybrané trasy a zpětnou trasu, která předčasně uzavírá okruh (Tropea - Reggio).
42
Krok 5: Přepočítáme opět diference a volíme další trasu (Cosenza - Crotone). Škrtáme opět řádek a
sloupec u vybrané trasy a zpětnou trasu, která předčasně uzavírá okruh (Crotone - Cosenza) + trasu
Catanzaro – Scalea, která by předčasně uzavřela okruh ještě před propojením všech míst.
43
Krok 6: Zbývají nám poslední dvě trasy, uzavřeme tedy okruh.
Krok 7: Navrhneme doporučenou trasu a vypočteme délku cesty (celkem délka 727 km).
44
Řešení 2: Metoda nejbližšího souseda
Krok 1 : Procházím postupně všechna města. Ke každému najdu nejbližšího souseda, k němu opět
nejbližšího souseda atd. až projedu všechna města