Problém
českého kačera
Úvod
Vzpomínáte si ještě na
dvanáct mých keší v rekultivované
krajině mezi Barborou,
Hrobem a
Křižanovem? Pokud jste je chtěli odlovit během jednoho odpoledne, tak
jste
určitě řešili, jak přesunem mezi nimi ztratit co nejméně času. Podobný
problém znají například obchodní
cestující (dnes bychom řekli obchodní zástupci firem). Mají za úkol
objet N měst, vrátit se zase do výchozího města a najet při
tom co
nejméně kilometrů. Dříve jezdili vlakem, nyní auty. Čas jsou peníze a
taky proč zbytečně utrácet za jízdné nebo za benzín. Nakonec se této
záležitosti chopili matematici a tak vznikl problém obchodního cestujícího
(zkráceně TSP – Travelling Salesman Problem).
Za jeho zakladatele se pokládá K. Menger (30. léta
20. století), který navázal na práci R. W. Hamiltona z r. 1858.
Profese
obchodního cestujícího inspirovala řadu spisovatelů, dramatiků a
filmařů. Vzpomeňme na divadelní hru Arthura Millera Smrt obchodního
cestujícího nebo na sbírku povídek Smrt krásných srnců od Oty
Pavla. Také Limonádový Joe byl obchodním zástupcem firmy Kolalok
&
syn.
Od začátku bylo jasné, že řešení TSP hrubou silou
(Brute force – BF) je únosné jen pro malý počet měst. V mé úloze (viz
dále) s pouhými N = 12 místy by to znamenalo propočítat
39 916
800
různých cest (tzn. sečíst skoro půl miliardy čísel udávajících
vzdáleností). Pro 20 míst už je třeba prověřit 2,43 * 1018
tras a třeba při rozvozu zboží na 25 adres bude 1,55 * 1025
různých možností, v jakém pořadí těch 25 zákazníků obsloužit (a zase se
s autem vrátit do skladu). Většina možností sice bude
už na první pohled nesmyslná, ale i tak zbude rozumných tras víc než
dost.
„Přátelé,
tudy ne, tudy cesta nevede,“ řekl Jára Cimrman – a
měl pravdu.
Jistě už tušíte, že zase máme co dělat s NP-úplnou úlohou,
kterou pro
trochu větší N zatím nejsme schopni vypočítat v
rozumném čase ani na dnešních superpočítačích. Těch 25 adres objede
průměrně inteligentní řidič za necelou pracovní směnu,
ale nám by výpočet trval do soudného dne. (Nepřeháním!
Maximální
rychlost nejvýkonnějšího počítače je t.č. cca 8,2 * 1015
operací za
sekundu, takže výpočet pro N = 25 by trval nejméně 1500 let...).
Zkrátka
P ≠ NP. A
tak vědci bádali a bádají, jak by si tu spoustu výpočtů ulehčili nebo
to aspoň nějak odšvindlovali. Hlavně rezignovali na to, že by byli
schopni najít jediné, to úplně nejlepší (optimální)
řešení. Místo toho postupně vymýšleli další a další více či
méně chytré metody.
Krátce po ukončení 2.
světové války např. vznikla simplexová
metoda,
která rychle vybere když už ne nejlepší,
tak aspoň nějaké
dobré (suboptimální)
řešení. Úspora času je přitom
ohromná, takže
se TSP a podobné metody implementované do počítačů začaly
využívat i v reálném životě. Aplikací se nabízí víc než
dost. Například podobný problém
čínského listonoše
nalézá uplatnění třeba při
údržbě a úklidu ulic a silnic, zvláště v zimě (sypání a pluhování).
Je-li použit vhodný
algoritmus, tak obvykle bývá chyba malá a za
časovou úsporu to stojí. (Na svém
počítači jsem spočítal výše uvedený příklad rozvozu zboží na N = 25
adres metodou
nejbližšího souseda
za zlomek sekundy...) V
literatuře je pro řešení TSP popsaná spousta dalších algoritmů různé
náročnosti a tomu odpovídající přesnosti. Vedle jednodušších (metoda nejbližšího souseda
nebo horolezecký
algoritmus)
přes různé kejkle s
prohazováním hran (spojnic) a přidáváním
vrcholů
(měst) až po simulaci změn v krystalických mřížkách rozžhavených
kovů při jejich chladnutí, opičení se po přírodě (genetický algoritmus,
využívající dědičnost, tj. rozmnožování, křížení, přírodní
výběr, mutace apod.) nebo simulující chování mravenců(!)
při cestě z mraveniště za potravou a zpět.
Tolik teorie, více naleznete na internetu. Ale vraťme se raději zpátky
ke
geocachingu.
Jak
najít keš
Na prvním obrázku vidíte
plánek území se zakreslenými kešemi –
tradičkami a finálkami, které chcete najít. Začněte u keše F,
postupně obejděte všech
dalších 11 keší a
pak se zas vraťte ke keši F. Zvolte si trasu mezi kešemi
tak,
jak sami
uznáte za
vhodné, abyste v terénu zbytečně nechodili sem a tam. Svůj návrh jste
si v
dalším kroku mohli otestovat v počítači.
Soubor v Excelu
jste si
mohli stáhnout z mých
stránek.
Jenže to už nepůjde. Seznam.cz totiž zrušil k 30.
11. bezplatné umístění souborů (včetně
tabulky Traveltest.xls pro výpočet) v úložišti Sweb.cz, takže už nejsou
dostupné. Navíc ani Geocaching.com už nebere soubory z jiných než
schválených webů. Vyřešil jsem to tedy jinak.
Obrázek 1. Rozmístění
keší. Začněte u keše F.
Osa x je vodorovná, osa y je
svislá. Číslice u os znamenají metry.
Souřadnice keší uvádím v tabulce 3.
* * *
Tabulka 2. Vzdálenosti mezi
kešemi jsou zaokrouhlené na celé metry. Pokud chcete větší
tabulku
společně s předchozím obrázkem, tak klikněte
sem. )
K event. ručnímu výpočtu používejte pouze
tyto zaokrouhlené vzdálenosti.
* * *
Tabulka 3:
Kartézské souřadnice (X a Y) jednotlivých keší.
Z
těchto souřadnic byly vypočteny všechny vzdálenosti v tabulce
č. 2.
Tabulka 4: Nejlepší řešení.
Teď ho už mohu prozradit...
Tato
úloha je silně zidealizovaná. Nepočítá s terénními překážkami a
předpokládá přímé spojené každé keše s každou. Můžete tedy jít
přímo „za šipkou“ a ani se nemusíte vracet po stejné cestě.
Ale až
se budete prodírat trním, brodit bahnem nebo odněkud spadnete, tak mi
nenadávejte!
Nová
úloha
Jak
jsem uvedl výše, tak tabulku Traveltest.xls už nelze použít. Proto jsem
vymyslel alternativní luštění pomocí Fleissnerovy otočné
mřížky. Mřížka 5×5 vás zavede rovnou na finálku.
Je zvykem doplnit
poslední „slovo“ celé zprávy do pěti znaků pomocí „X“.
Do tabulky 5×5 musíte šifrovaný text vkládat natřikrát.
Mřížku otáčejte doprava.
Poznámky
-
Problém obchodního cestujícího patří vedle problému čínského listonoše
mezi
dopravní
úlohy.
Spolu s dalšími typy úloh (např. problémem
dvou loupežníků, problémem batohu, řeznými plány, teorií
hromadné obsluhy (teorií front), CPM, PERT atd.)
tvoří širokou skupinu metod operačního
výzkumu (operační analýzy).
-
Internetové
zdroje: hledejte hesla: problém obchodního cestujícího, TSP,
Hamiltonova kružnice, operační
výzkum, lineární programování, simplexová metoda, problém čínského
listonoše, NP úlohy, teorie grafů a pod. Najdete tam taky řadu
bakalářských a
magisterských diplomových prací, kde se dočtete podrobnosti.
-
V této oblasti je řada posedů a občas tam
natrefíte i na myslivce. Takže pozor za šera a tmy, zvláště na podzim!
Je tam i dost velký pěší i cyklistický mudloprovoz. Na přístupových
cestách bývá bláto i v sušším období.
Konec
GC8EZTK
– verze 2.6 z 12. 1. 2024
(CC BY-SA 3.0
CZ) ladislavappl, 2019
Vytvořeno v
Kompozeru