Skip to Content

<

Problem ceskeho kacera

A cache by ladislavappl Send Message to Owner Message this owner
Hidden : 10/17/2019
Difficulty:
2.5 out of 5
Terrain:
3 out of 5

Size: Size: small (small)

Join now to view geocache location details. It's free!

Watch

How Geocaching Works

Please note Use of geocaching.com services is subject to the terms and conditions in our disclaimer.

Geocache Description:


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 by Jára Cimrman – a měl by 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ší 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. Na pří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. 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 vráť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. 

Obrázek 1. Rozmístění keší. Začněte u keše F, postupně odlovte všech dalších 11 keší a pak se zase vraťte ke keši 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 zaokrouhlené na celé metry. Pokud chcete větší tabulku společně s předchozím obrázkem, tak klikněte sem. ) 
K výpočtům 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. 

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!

Vzdálenosti mezi kešemi, které hodláte odlovit, si poznamenávejte a nakonec je sečtěte. Nezapomeňte přičíst i poslední úsek do bodu F. Pokud budete své řešení považovat za dobré, tak si ho můžete zkontrolovat v souboru Traveltest.xls (pro Excel, pro Calc z Open Office či z Libre Office). V souboru je i návod k použití. Do žlutého pole zapisujte písmena označující jednotlivé keše podle obrázku č. 1 ve vámi navrhovaném pořadí. Program vypočítá celkovou vzdálenost v metrech, ukáže vám rovnou příslušné souřadnice, kam máte jít a k tomu přidá krátkou poznámku k umístění keše (hint). Když vám systém při pokusu vložit písmeno oznámí, že „soubor je pouze pro čtení“, tak stačí soubor uložit (třeba na Plochu) a pak ho z ní otevřít.
Souřadnice, na kterých máte začít s hledáním na této multině, závisejí na kvalitě vašeho řešení. Jděte na ty, které se zobrazí u vaší nejkratší cesty (tj. nejmenší celkové vzdálenosti); těch, které vám vyšly dřív, si už nevšímejte. To je právě ten bonus, aby ti úspěšnější mohli některé stage vynechat a zkrátit si cestu. Takže je ve vašem zájmu najít řešení s nejkratší trasou.

Pokud nemáte Excel nebo jiný výše uvedený program, tak si můžete  zkontrolovat své řešení v Geochecku. Podle tabulky 2 vypočtěte celkovou vzdálenost v metrech a dosaďte ji místo hvězdiček jako souřadnice N 50° 0*.***  E 13° 33.333; např. vzdálenost 6123 metrů dosaďte jako N 50° 06.123   E 13° 33.333. Geocheck vám ukáže souřadnice na které máte jít nebo vypíše chybovou hlášku. Geocheck ale použijte jen v případě, že nemáte Excel! Geocheck vás totiž pošle na všechny stage a nedá vám bonus (možnost vynechat některé stage), kdybyste přišli na dobré řešení. Nedosazujte do něj souřadnice, které vám při ověřování vyšly v Excelu – ty vám Geocheck nevezme!!!  

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ý mudloprovoz. 

Konec

GC8EZTK  – verze 1.3 z 10. 11. 2019

(CC BY-SA 3.0 CZ) ladislavappl, 2019

Document made with KompoZer

Additional Hints (Decrypt)

Uvag wr i birebinpv Genirygrfg. Abhmbir (wra cbxhq Genirygrfg arbgriergr) ymr cbhmvg Trbpurpx.

Decryption Key

A|B|C|D|E|F|G|H|I|J|K|L|M
-------------------------
N|O|P|Q|R|S|T|U|V|W|X|Y|Z

(letter above equals below, and vice versa)



Return to the Top of the Page

Reviewer notes

Use this space to describe your geocache location, container, and how it's hidden to your reviewer. If you've made changes, tell the reviewer what changes you made. The more they know, the easier it is for them to publish your geocache. This note will not be visible to the public when your geocache is published.