W. J. Cook: Po stopách obchodního cestujícího
W. J. Cook: Po stopách obchodního cestujícího. Matematika na hranicích možností. Dokořán a Argo, 2012, 258 str., váz.
Problém obchodního cestujícího je dosud nevyřešený matematický problém. Spočívá v tom, že máte seznam měst, které potřebujete navštívit, každé jednou, a na konci cesty se opět vrátit domů, do výchozího města. Cesta má být nejkratší. Co je na tomto problému obtížného? Zdánlivě se nabízí jednoduché řešení, propočítat všechny možnosti. Tato metoda hrubé síly má však malý háček, už při počtu měst blížícím se počtu bývalých okresních měst v Česku je těchto možných tras větší než je počet atomů ve vesmíru. Tento počet atomů odhadl v minulém století Artur Edington, propagátor a podporovate Alberta Einsteina na deset na osmdesátou, tedy jedničku, následovanou 80 nulami. Tento zdánlivě jednoduchý a bezvýznamný problém má docela velký význam nejen pro obchodní cestující, firmy zásobující např. Prodejny, ale také při výrobě integrovaných obvodů, desek plošných spojů, ale také při plánování pohybu Hubbleova teleskopu atd.
Autor knihy náleží do úzkého okruhu nejvýznamnějších matematiků, zabývajících se tímto problémem. Kniha má 12 kapitol, předmluvu, poznámky, seznam literatury a rejstřík. Problém obchodního cestujícího se dotýká výpočtové složitosti. Na matematiky, kteří by našli řešení problému, čeká tučná odměna. Clayův matematický institut vypsal odměnu 1 milión dolarů pro kohokoliv, kdo přijde jako první s efektivním řešením, nebo kdo dokáže, že žádné takové efektivní řešení neexistuje. Problém neustále motivuje nové a nové objevy v oboru aplikované matematiky. O tzv. problémech milénia, tedy o sedmi matematických problémech, na jejichž vyřešení je vypsána odměna po jednom milionu dolarů, vydalo nakladatelství Dokořán knihy Problémy pro třetí tisíciletí.
Lidé se s problémem obchodního cestujícího setkali už mnohem dříve, než se stal předmětem studia matematiků. Profesionální matematici se nesnázemi obchodních cestujících, kazatelů a právníků, kteří potřebovali při svých cestách stanovit nejkratší cestu, příliš nezabývali. Přesto dva matematici vytvořili základy pro budoucí zkoumání problému z matematického hlediska. Byli to Leonhard Euler, který vyřešil hádanku, která trápila obyvatele Královce (dnes Kaliningrad). Obyvatelé města se rádi procházeli městem a při tom přecházeli řeku Pregel přes sedm mostůp, které tehdy existovaly. Hádanka spočívala v tom, najít způsob, jak přejít sedm mostů právě jednou během jediné procházky městem. Euler jednou pro vždy problém vyřešil a vytvořil při tom novou matematickou metodu, teorii grafů. Druhý matematik, Howard Rowan Hamilton měl zálibu v hledání cest v grafech. Sto let po Eulerovi studoval problém cesty, která má projít všech 20 vrcholů pravidelného dvanáctistěnu. Hamilton a Euler hledali cesty, při kterých mohli zanedbat vzdálenosti.
Dnešní typický obchodní cestující má auto vybavené satelitní navigací. Mapový software, který běží na jednotce GPS, často obsahuje modul pro vyřeršení malých úloh obchodního cestujícího kolem deseti měst, což stací pro cesty v rámci jednoho dne.
Podstatná část knihy je věnována historii výzkumu problému a zdokonalovaní a zjemňování metod.
Devátá kapitola „Výpočtová složitost“ se věnuje tím, zda existuje nebo neexistuje polynomiální algoritmus pro omezenou úlohu v celočíselním programování, která je jako taková samozřejmě konečná. Tak alespoň zní motto kapitoly, jehož autorem je Jack Edmonds. Všechna matematická tvrzení musí být formulována, nebo musí být alespoň v principu možné je přesně fotrmulovat, abychom mohli mluvit o jejich řešení. Otázka zní: jak zformalizovat pojem algoritmus: Problém se dostal do popředí na počátku 20. století, kdyžř David Hilbert formuloval problém rozhodnutelnosti. Teorie, která vedla k odpovědi na podobné otázky, je jedním z výsledků matematiky 20. stol. K jejímu vybodování přispěli Kurt Goedel, Alonzo Church a Alan Turing. Turing zavedl Turingův stroj. Jeho definice umožnila matematicky zkoumat algoritmy. S příchodem počítačů začala získávat na důležitosti otázka efektivnosti. Jedna věc je vědět, že Turingův stroj problém vyřeší, a jiná, míst jistotu, že se řešení dozvíme ještě za našeho života. První diskuse týkající se efektivnosti algoritmů se soustředily na problém obchodního cestujícího. Právě citovaný Jack Edmonds se stal zakladatelem teorie výpočtové složitosti.
V kapitole 11 „Estetika“ cituje autor knihy jako motto výrok českého matematika z Univerzity Karlovy Jaroslava Nešetřila: „Matematika byla vždy zdrojem složitých (a pro laiky mystických) struktur“. Kapitola se tak zabývá krásou v matematickém smyslu. Problém obchodního cestujícího inspiroval vznik celé řady poutavých výtvarných děl, které zachytily jeho matematickou podstatu. Kromě Jaroslava Nešetřila, který napsal a vydal v angličtině esej o matematice a umění, autor knihy opakovaně píše zřejmě o dalším českém matematikovi, který asi žije v USA, Vaškovi Chvátalovi, nebývá ovšem obvyklé, aby se v podobných zahraničních knihách nejen o matematice objevovala jména českých vědců, proto jsem se o tom zmínil. Kniha končí kapitolou „O krůček dál“, která má jen dvě stránky. Shrnuje, že problém není uzavřen, a že krása skrytá v problému obchodního cestujícího bude dál lákat matematiky a informatiky.
Karel Vašíček
Šílený střelec a selhání policie
Včera jsme zažili zřejmě nejhorší jednotlivý trestný čin v našich dějinách. Detailů jsme se zatím mnoho nedozvěděli ani od policie ani z médií. Nabízí se několik otázek.
Karel Vašíček
Kdo cestou k moci vraždil a vraždit bude dál.
Slova písničkáře Vladimíra Merty byla aktuální před lety po pádu tzv. komunistického režimu. Dnes bychom slovo vraždit mohli nahradit slovem lhal. Nicméně ve výzkumech veřejného mínění nemalá část populace uvádí, že současní polit
Karel Vašíček
E-mail predsedovi CSSD MIchalu Smardovi
Dekuji za newsletter "priteli" Smardo, Jak jste dopadli ve volbach? Jako sedlaci u Chlumce Ptam se, koho muze zaujmout chudak jako jste Vy, nebo "pritel" Hamacek
Karel Vašíček
Výročí narození matematika Alana Turinga, utajovaného hrdiny 2. světové války,
Výročí narození matematika Alana Turinga, utajovaného hrdiny 2. světové války, pár slov o Antonínu Svobodovi čsl. průkopníku počítačových technologií světového významu A. Turing – otec moderních počítačových technologií.
Karel Vašíček
Jsme v polovině pandemie koronaviru?
Už dva roky světovou populací drtí pandemie, kterou nikdo z naší generace ani z našich rodičů nezažil. Když už „hořela“ značná část Itálie, někteří novináři a politikové psali, že koronavir je vymyšlený a vše, co se kolem nás děje
Další články autora |
Tři roky vězení. Soud Ferimu potvrdil trest za znásilnění, odvolání zamítl
Městský soud v Praze potvrdil tříletý trest bývalému poslanci Dominiku Ferimu. Za znásilnění a...
Moderní lichváři připravují o bydlení dlužníky i jejich příbuzné. Trik je snadný
Premium Potřebujete rychle peníze, pár set tisíc korun a ta nabídka zní lákavě: do 24 hodin máte peníze na...
Takhle se mě dotýkal jen gynekolog. Fanynky PSG si stěžují na obtěžování
Mnoho žen si po úterním fotbalovém utkání mezi PSG a Barcelonou postěžovalo na obtěžování ze strany...
Školu neznaly, myly se v potoce. Živořící děti v Hluboké vysvobodili až strážníci
Otřesný případ odhalili strážníci z Hluboké nad Vltavou na Českobudějovicku. Při jedné z kontrol...
Prezident Petr Pavel se zranil v obličeji při střelbě ve zbrojovce
Prezident Petr Pavel se při střelbě na střelnici v uherskobrodské České zbrojovce, kam zavítal...
Arizonští poslanci zrušili 160 let starý zákon, který zakazoval potraty
Zákonodárci ve Sněmovně reprezentantů v americkém státě Arizona ve čtvrtek schválili zrušení zákona...
Poslední mrazivá noc. Od pátku se bude oteplovat, v neděli se vrátí letní teploty
Ve čtvrtek budou ještě teploty podprůměrné a na horách může sněžit. V pátek ráno dokonce hrozí na...
Rusko vyrábí víc zbraní, než potřebuje na Ukrajině, varoval německý ministr
Rusko podle odhadů německého ministra obrany Borise Pistoriuse už vyrábí více zbraní a munice než...
Nejednáme. Na obzoru je stávka soudních pracovníků, požadují vyšší platy
Premium Odvádějí vysoce odbornou práci, musejí skládat speciální zkoušky, někdy sami vypracovávají drobná...
- Počet článků 178
- Celková karma 0
- Průměrná čtenost 924x