William J. Cook

Po stopách obchodního cestujícího

Matematika na hranicích možností

                     Překlad Veronika Douchová a Radek Honzík, vázaná s přebalem, 165 x 235, 256 stran, 120 ilustrací, vydání 1, poprvé vyšlo 09.10.2012.

Původní název: In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation

                                        Představte si, že máte seznam měst, která potřebujete navštívit, každé jednou, a na konci cesty se chcete dostat zpátky domů. Jak najít nejkratší cestu? Tak zní zadání problému obchodního cestujícího. Je to velmi jednoduché a řešení jistě také - prostě všechny cesty vyzkoušíme a vybereme tu nejkratší. Jenže je tu háček: už při 85 městech je těchto cest víc, než kolik je ve viditelném vesmíru atomů. To asi nezvládneme.

Hledání nejkratší spojnice mezi mnoha body se využívá v celé řadě oborů, od výroby mikročipů po plánování pohybu Hubbleova teleskopu, a používáním pokročilých metod hledání se ročně ušetří desítky miliard dolarů, pro matematiky je však asi mnohem důležitější fakt, že vyřešením tohoto problému by zároveň překonali jeden ze sedmi největších matematických problémů pro třetí tisíciletí - P versus NP. Pro řešitele každého z těchto problémů vypsal v roce 2000 Clayův matematický institut odměnu milion dolarů a i to je důvodem (pro nezištné matematiky samozřejmě jen podružným), proč se jeho řešením zabývají již několik desítek let stovky nejlepších mozků planety.

Téma knihy je podáno na vysoké odborné úrovni - její autor totiž patří do úzkého kroužku nejvýznamnějších postav tohoto výzkumu - historii hledání optimální cesty je však zároveň podáno s neobvyklým nadhledem a šarmem. Proto vtipné líčení místy až bizarních metod řešení, aplikací i osudů řešitelů potěší i matematického laika.

                   O autorovi: William J. Cook (* 1957) je profesorem matematiky na Georgia Institute of Technology v Atlantě. Jeho celoživotním zájmem je kombinatorická optimalizace a celočíselné programování, na poli výzkumu problému obchodního cestujícího patří k celosvětové špičce. Je autorem řady odborných knih, článků a studií, kniha Po stopách obchodního cestujícího je jeho prvním populárně naučným dílem.

                 OBSAH

Předmluva 11

1. Velká otázka 14

Cesta po Spojených státech 15

Neřešitelný problém? 19

Jeden problém po druhém 24

Jak číst tuto knihu 30

2. Počátky problému 33

Než nastoupili matematici 33

Euler a Hamilton 41

Z Vídně do Harvardu a Princetonu 51

A dál až do RAND Corporation 54

Statistický pohled na věc 55

3. Na scénu přichází obchodní cestující 60

Po cestách i necestách 60

Mapování genomu 65

Směrování teleskopů, rentgenových paprsků a laserů 67

Ovládání průmyslových strojů 70

Třídění dat 72

Testování mikroprocesorů 75

Plánování úloh 76

A to není všechno… 77

4. Jak najít tu správnou cestu 78

Problém 48 států 78

Od cesty ke stromům a zpět 80

Na několik pokusů… 93

Vypůjčky z fyziky a biologie 103

DIMACS a koordinace vyzkumu 111

Rekordmani 112

5. Linearni programovani 114

Viceučelovy model 114

Simplexovy algoritmus 120

Dva za cenu jednoho: LP dualita 126

Linearni relaxace obchodniho cestujiciho 128

Eliminace podcest 133

Perfektni relaxace 139

Celočiselne programovani 143

Operačni vyzkum 146

6. Řezani mnohostěnů 148

Metoda řeznych rovin 148

Katalog nerovnic pro TSP 153

Separačni problem 158

Edmondsův kousek nebe 165

Řezne roviny a celočiselne programovani 166

7. Větve a meze 168

Rozděleni na menši celky 168

Prohledavaci stromy 171

Větve a meze pro celočiselne programovani 173

8. Počitani ve velkem 175

Světove rekordy 175

Velky a ještě větši 186

9. Vypočtova složitost 191

Teoreticky vypočtovy model 192

Zapas Jacka Edmondse 195

Cookova věta a Karpův seznam 197

A co obchodni cestujici? 201

Potřebujeme vůbec počitače? 209

10. Lidsky pohled na věc 217

Lide versus počitače 217

Jake strategie ma člověk k dispozici? 218

TSP v neurovědě 221

Zviřata řeši TSP 223

11. Estetika 225

Julian Lethbridge 225

Jordanovy křivky 227

Jen jedna čara stači 231

Uměni a matematika 233

12. O krůček dal 237

Poznamky 239

Bibliografie 249

Rejstřik 251

PŘEDMLUVA

Tulak z pisničky Geoffa Macka byl pry všude, tedy jmenovitě v nasledujicich

městech: Reno, Chicago, Fargo, Buffalo, Toronto, Winslow, Sarasota, Wichita,

Tulsa, Ottawa, Oklahoma, Tampa, Panama, Mattawa, LaPaloma, Bangor,

Baltimore, Salvador, Amarillo, Tocapillo, Barranquilla a Padilla.

Jednou v noci v unoru roku 1988 jsme se s kamaradem Vaškem Chvatalem

rozhodli pokračovat ve šlepějich matematickych obrů a pokusit se vyřešit

problem, jak najit nejkratši cestu mezi různymi městy – třebas mezi těmi

v pisni Geoffa Macka. Hned přišti rano jsme vyrazili do obchodu Tri-State Camera,

což je počitačovy obchůdek na dolnim Manhattanu. Když se přitomny

technik dozvěděl, že jsme matematici a chceme rychly počitač, podival se

nam do oči a zeptal se varovně: „Nechystate se nahodou vyřešit problem

obchodniho cestujiciho?“ Když si na tento okamžik dnes vzpomenu, myslim,

že jeho vystraha byla namistě. Byl to prvni z řady počitačů, ktere jsme doslova

odrovnali během nasledujicich dvaceti let věnovanych hledani řešeni.

Problem obchodniho cestujiciho zni takto: nalezněte nejkratši cestu mezi

všemi městy na danem seznamu s tim, že každe město smite navštivit pouze

jednou a musite se vratit zpět tam, kde jste začinali. Tulak z pisničky by musel

teoreticky ověřit všech 51 090 942 171 709 440 000 cest mezi 22 městy, aby

našel tu nejkratši. I nejrychlejšimu superpočitači by takova uloha na nějaky

ten den dala docela zabrat, ale při trošce trpělivosti bychom vypsali všechny

cesty a našli tak i tu nejkratši. Ale co když bychom měli hledat nejkratši cestu

mezi stovkou měst? Pak by bylo zkontrolovani všech cest zhola nemožne,

i kdybychom na to rezervovali vykon všech počitačů na celem světě.

To ještě neznamena, že problem sam je obtižny – co když lze najit nejkratši

cestu jinak, než že vypišeme všechny možnosti? Vždyť skutečně existuji

podobne problemy, kde je ještě vice kandidatů na řešeni a ktere umime

řešit relativně snadno. Problem obchodniho cestujiciho je fascinujici tim,

že se i přes snahu ohromneho počtu vynikajicich matematiků pořad nevi,

jestli lze obecně najit nejkratši cestu podstatně rychleji než vypsanim všech

11P Ř E DML U VA

možnosti. Je dokonce realna možnost, že žadna takova efektivni metoda

vůbec neexistuje. Je to hluboka matematicka otazka: existuje efektivni řešeni

problemu nebo ne? Otazka se dotyka hlubokych partii vypočtove složitosti

a mezi efektivniho počitani. Na odvažlivce, kteři by se radi pustili do řešeni

obecneho problemu obchodniho cestujiciho, čeka i sladka odměna: Clayův

matematicky institut vypsal odměnu 1 000 000 dolarů pro kohokoli, kdo

jako prvni přijde s efektivnim řešenim, nebo dokaže, že žadne takove řešeni

neexistuje.

Od uplneho řešeni můžeme byt v současně době hodně daleko. Ale to

neznamena, že jsme složili ruce do klina a nemame nic. Opak je pravdou –

existuje velky počet dilčich vysledků a hypotez, ktere jsou jak krasne, tak

i hluboke. Pokud jde o velikost uloh, ktere umime řešit, v roce 2006 jsme vyřešili

problem s 85 900 městy; vypočet zabral celkem 136 let strojoveho času

(a to uvažujeme superrychly počitač), protože bylo třeba projit neuvěřitelne

množstvi připadů. Z praktickeho hlediska si tak nevedeme špatně: u většiny

uloh, se kterymi se ve skutečnosti setkate, umime rychle najit nejkratši nebo

skoro nejkratši cestu.

Jednou z kladnych stranek obtižnosti problemu je skutečnost, že motivuje

nove objevy a nove techniky na poli aplikovane matematiky, operačniho

vyzkumu a matematickeho programovani. A dalši objevy už čekaji za rohem.

Hlavnim cilem teto knihy je proto vzbudit v čtenaři zajem o tuto problematiku

a motivovat ho k samostatnemu hledani.

Při psani knihy mi pomahalo hodně lidi, kterym bych zde rad poděkoval.

V prve řadě zminim sve kamarady a spolupracovniky – jsou to David Applegate,

Robert Bixby a Vašek Chvatal. Přes dvacet let jsme se spolu snažili

odhalit tajemstvi obchodniho cestujiciho. Hned za nimi jsou Michel Balinsky,

Mark Baruch, Robert Bland, Sylvia Boydova, William Cunningham, Michel

Goemans, Timothy Gowers, Nick Harvey, Keld Helsgaun, Alan Hoffman, David

Johnson, Richard Karp, Mitchel Keller, Anton Kleywegt, Bernhard Korte,

Harold Kuhn, Jan Karel Lenstra, George Nemhauser, Gary Parker, William

Pulleyblank, Andre Rohe, Lex Schrijver, Bruce Shepherd, Stan Wagon, David

Shmoys, Gerhard Woeginger a Phil Wolfe, kterym patři dik ze přijemne

rozhovory o matematickych i historickych souvislostech problemu.

Obrazky a historicky material poskytli: Hernan Abeledo, Leonard Adleman,

David Applegate, Masashi Aono, Jessie Brainerd, Robert Bixby, Adrian

Bondy, Robert Bosch, John Bartholdi, Nicos Christofides, James Dalgety, Todd

Eckdahl, Daniel Espinoza, Greg Fasshauer, Lisa Fleischerova, Philip Galanter,

12