neděle, dubna 18, 2010

Problém obchodního cestujícího, aneb když počítače nestíhají

Není pochyb o tom, že počítače hrají v dnešním světě čím dál větší roli. Rozšiřuje se množství přístrojů s přívlastkem "chytrý". Takovéto rozšíření počítačů ve všedním světě by mohlo vést k myšlence, že prakticky nemůže existovat úloha, kterou by dostatečně výkonný počítač nemohl vyřešit, ale to je omyl.

Ve třicátých letech minulého století byl formulován tzv. Problém obchodního cestujícího, který je založen na následující úvaze. Představme si že jsme obchodní cestující, který má z nějakého města postupně navštívit další tři města a potom se zase vrátit zpět.

Nechť je našim startovním bodem město Brno a během své služební cesty musíme navštívit Znojmo, Břeclav a Olomouc a poté se zase vrátit zpět. Přitom je třeba co nejvíce šetřit čas a benzin. Celkovou vzdálenost, kterou urazíme, musí být co nejkratší. Podíváme se do mapy a zjistíme nejkratší vzdálenost mezi každými dvěma městy, výsledky pak zapíšeme do tabulky:

Brno Znojmo Břeclav Olomouc
Brno 0 55,2 53,5 65,09
Znojmo 60,2 0 61,97 120,3
Břeclav 53,5 61,97 0 98,11
Olomouc 65,09 120,3 98,11 0

(Pozn.: Vzdálenost Brno-Znojmo není stejná jako Znojmo-Brno z důvodu objížďky na trati.)

Otázkou je jak uspořádat zbylá tři města tak, abychom ujeli co nejkratší vzdálenost. Na první pohled by tato úloha neměla být vůbec těžká. Stačí vzít jednotlivá uspořádání tras, z tabulky vyčíst vzdálenosti, sečíst je, a se získaných celkových vzdáleností vzít tu nejmenší.

Tedy v našem případě máme tyto kombinace tras:

Trasa Celková délka [km]
 Brno-Znojmo-Břeclav-Olomouc-Brno   55,2+61,97+98,11+65,09 = 280,37
 Brno-Znojmo-Olomouc-Břeclav-Brno  55,2+120,3+98,11+53,5 = 327,11
 Brno-Břeclav-Olomouc-Znojmo-Brno  53,5+98,11+120,3+60,2 = 332,11
 Brno-Břeclav-Znojmo-Olomouc-Brno  53,5+61,97+120,3+65,09 = 300,86
 Brno-Olomouc-Znojmo-Břeclav-Brno  65,09+120,3+61,97+53,5 = 300,86
 Brno-Olomouc-Břeclav-Znojmo-Brno  65,09+98,11+61,97+60,2 = 285,37

Je evidentní, že v našem případě je optimální trasa Brno-Znojmo-Břeclav-Olomouc-Brno, jejíž délka je 280,37 km. Poznamenejme, že použité vzdálenosti jsou pouze přibližné a pro jejich získání byl použit vyhledávač WolframAlpha.

Pro malé množství tras je tato úloha triviální, ale v případě obchodního cestujícího, který musí navštívit velké množství měst, je tato úloha opravdu dost náročná.

Řekněme, že naše trasa obsahuje kromě počátečního města ještě dalších 10 měst. Mohli bychom pokračovat mnoha způsoby, od ručního počítání (to ale nelze doporučit, neboť celkový počet tras je 3 628 800) nebo provedeme výpočet na PC, třeba v nějakém tabulkovém procesoru.

Jak jsme došli k číslu 3 628 800? Jedná se o takzvaný faktoriál čísla 10 a píšeme 10!. Faktoriál čísla n je roven součinu všech kladných celých čísel menších nebo rovných n.

Faktoriál se vyskytuje v mnoha oblastech matematiky, zejména pak v kombinatorice, kde vyjadřuje počet permutací množiny n prvků, tzn. vyjadřuje počet způsobů, jak seřadit n různých objektů. V našem případě

10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3 628 800

(na začátku máme 10 možností, kde začít, pak 9, ...).

Teď si představme, že si sami pro každou z těchto tras spočítáme celkovou vzdálenost a že nám každý takový výpočet zabere přesně jednu minutu. Potom bychom strávili nepřetržitým počítáním 6,9 roku! Skoro 7 let kvůli deseti městům.

Přidáme-li jedenácté město, pak se celkový počet různých tras přiblíží čtyřiceti milionům:

11! = 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 39 916 800

počítání by nám trvalo skoro 76 let!

Vidíme tedy, že faktoriály rostou velice rychle, a nemůžeme se proto divit, že když přidáme k našemu seznamu měst jen pár položek navíc, tak se radikálně zvýší časová náročnost výpočtu a i nejvýkonnější počítače takovýto úkol, založený na faktoriálním růstu veličiny, nemusí zvládnout.

Problém obchodního cestujícího ilustruje zajímavý fakt, že i velmi jednoduše formulované problémy mohou být neřešitelné (nebo jsou řešitelné, ale výpočet by trval příliš dlouho).

Samozřejmě v reálném životě nelze říct, že daný problém je neřešitelný, a proto matematici vynaložili velké množství energie pro nalezení jiných postupů. Zvolené přístupy lze zhruba rozdělit do dvou skupin.

První přístup je založen na tom, že se spokojíme s přibližným výsledkem. Místo absolutně nejkratší trasy budeme hledat nějakou jinou trasu, která se bude od optimální trasy lišit maximálně o zadané procento. Tento způsob se často využívá, neboť funguje ve většině bežných situací.

Druhý způsob spočívá v tom, že sice budeme trvat na přesném výsledku, ale napřed se podíváme na celkové zeměpisné rozložení měst a budeme se snažit využít specifických vlastností jejich poloh ke snížení celkového počtu tras, které je třeba zanalyzovat.

Například můžeme vyloučit na první pohled neefektivní trasy, např. ty které nás nutí cestovat z nejjižnějšího města do toho nejsevernějšího v prvních dvou krocích. Velkou nevýhodou tohoto přístupu je, že je optimalizován pouze pro konkrétní skupinu cílů, přidáním dalších měst musíme výpočet provést znovu.

Náročnost a neefektivnost této metody dokládá i výsledek amerických matematiků z roku 1998, kterým výpočet nejkratší trasy, která spojuje všech 13509 amerických měst nad 5000 obyvatel trval 3 měsíce nepřetržitých výpočtů na na počítačové síti složené ze třech superpočítačů (12 procesorů) a 32 PC Pentium II.


Je možné, že budoucí výpočetní systémy využívající kvantové jevy či DNA budou zvládat řešit problém obchodního cestujícího dostatečně rychle, ale v současnosti se musíme smířit s tím, že kromě přibližných či částečných výsledků pro některé podmnožiny měst žádné úplné prakticky využitelné řešení prostě neexistuje.


Zdroje a další informace
Wikipedia, crpc.rice.edu, Keith Devlin - Problémy pro třetí tisíciletí, Argo.


Přidat.eu záložku

7 komentářů:

Anonymní řekl(a)...

A co genetické a jiné nedeterministické algoritmy? Nebo třeba neuronové sítě (Kohonenova síť). Nejsme tak bezradní, jak by se zdálo!

Anonymní řekl(a)...

Špatá premisa hned na začátku. A zbytek? Člověče, měl jste někdy alespoň semestr předmětu zvaného Teorie grafů?

Anonymní řekl(a)...

Dobrý den! Nevím, jestli toto bude s takovým odstupem někdo číst, ale to co tu píšete mne zvedá ze židle.Případ obchodního cestujícího máme již několik let vyřešen a není to tak jak se píše.Dnes jsme schopni vzít v úvahu až 250 míst. Víc jich je možné také vzít v úvahu, ale jsme omezeni paradoxně zadáváním vstupů. V současnosti řešíme automatické zadávání programem. Tyto příklady a jim podobné(např. šachy) jsou postaveny na kombinatorice. Je paradox, že si tito pisatelé neuvědomují, že není nutné provádět kompletní plnou kombinaci. Důvodem je nereálnost či nesmyslnost nekterých možností. Je to jako například v šachách, kde příkloadně střelec taky netahá podle pravidel vodorovně, ale pouze úhlopříčně. Zde je vidět, že kombinace vodorovná pro střelce je neplatná! V tomto obobru jsme navíc museliu stanovit dva operandy, které v současnosti oficiálně neexistují. Potom jsou tyto příklady bezproblémů řešitelné. Tyto příklady řešíme jako hoby a postup vznikl jako vedlejší produkt ekonomického výzkumu. Bohužel jej nelze patentovat takže jej používá pár znalých lidí. Podpora na větší a další rozšíření není - nejsme Amerika ale funguje to !!!
S pozdravem MC.

Anonymní řekl(a)...

S.Fil:
Jo, jasne 250 mist :-D A tech par zasvecencu jsou mimozemstani, ze?

Anonymní řekl(a)...

Ví někdo, proč vědátoři počítali onen "výpočet nejkratší trasy, která spojuje všech 13509 amerických měst nad 5000 obyvatel"?? K čemu jim to bylo? Má snad někdy někdo v úmyslu vyjet jedním jediným autem z jednoho místa a objíždět všechna ostatní se striktním požadavkem absolutně nejméně najetých kilometrů? Nebo se spíš jedná zas jen o další z nepřeberné plejády vědeckého "honění si trika"?
BTW: podle reCAPTCHY jsem robot, protože jsem zcela naivně hnědé kafe nepovažoval za čaj, a poznat co je a co není salát jsem rovnou vzdal. No super :-D

peter řekl(a)...
Tento komentář byl odstraněn autorem.
michal řekl(a)...

Dost zajímavý článek. Kdo by tenkrát řekl, že se po deseti letech doprava prakticky vůbec nezmění, jen ty důvody jsou trochu odlišné. Na druhou stranu se ale vytratila ta postava obchodního cestujícího, který létá po Evropě a domlouvá kontrakty. Dneska máme prostě webky. Nedávno jsem o tom četl docela zajímavý článek, který právě hodnotil to, jak moc se změnila administrativní práce. ;-)

 

blogger templates | Make Money Online