Problém obchodního cestujícího

pátek 29. dubna 2016 ·

Problém obchodního cestujícího je podle Wikipedie obtížný diskrétní optimalizační problém, matematicky vyjadřující a zobecňující úlohu nalezení nejkratší možné cesty procházející všemi zadanými body na mapě.




Doprovodný článek na Popcyclical.com

OptiMap - online služba řešící problém obchodního cestujícího v prostředí Mapy Google (maximálně 100 bodů trasy):




Zdroj: kottke.org, Wikipedie

3 komentářů:

Pavel Doležel řekl(a)...
29. dubna 2016 14:41  

V tom nadpisu to není napsáno úplně přesně. Problém obchodního cestujícího je problém nalezení takové cesty, která každé z prodejních míst navštíví právě jednou a skončí v místě, v němž začala a která bude zároveň nejkratší ze všech možných.

Nejsem si jist, zda lze skutečně obecně v reálném čase nalézt nejkratší cestu pro 100 obchodních míst. Aktuálně znám algoritmy local search typu a evoluční algoritmy. Všechny ale problém řeší pouze heuristicky. Pak je možné to řešit hrubou silou, což sice vede k optimu, ale nikoliv v nějakém rozumném čase. Problém je NP úplný.

m vanek řekl(a)...
30. dubna 2016 9:56  

Jedná se o matematický problém z teorie grafů. Problém má řadu variant. Obecné řešení neexistuje. Pokud by na ně někdo přišel, bude hodně slavný. Proto bývá tento problém v soutěžích a všichni doufají, že se objeví nějaký geniální přístup, který ukáže cestu k řešení.

Pavel Doležel řekl(a)...
30. dubna 2016 10:09  

Proč by obecné řešení neexistovalo? Existuje a nemusí nutně být jen jedno. Problém je ho nalézt. Jediný algoritmus, který obecně vede k nalezení nejkratší cesty je ale triviální a prostě zkouší všechny možné cesty a pak vybere tu nejkratší. Protože jich je moc, nezvládne to dostatečně rychle.

Slavný bude ten, kdo nalezne řešení, které by běželo tzv. v polynomiálním čase. To by totiž zároveň znamenalo vyřešení slavného problému P=NP. K tomu ale velmi pravděpodobně nedojde. Spíše čekám důkaz, že P<>NP.



Články dle data

Učitelské listy

Nabídka práce

Česká škola - portál pro ZŠ a SŠ

Česká škola poskytuje svým čtenářům diskusní prostor k vyjádření názorů na školskou problematiku. Tyto příspěvky se nemusí shodovat se stanoviskem redakce České školy a jsou uveřejňovány jako podnět k dalším diskusím.

Obsah článků nemusí vyjadřovat stanovisko redakce nebo vydavatele Albatros Media, a.s.


Všechna práva vyhrazena.

Tento server dodržuje právní předpisy
o ochraně osobních údajů.

ISSN 1213-6018




Licence Creative Commons

Obsah podléhá licenci Creative Commons Uveďte autora-Neužívejte dílo komerčně-Nezasahujte do díla 3.0 Česká republika, pokud není uvedeno jinak nebo nejde-li o tiskové zprávy.



WebArchiv - archiv českého webu



Tyto webové stránky používají k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Informace o tom, jak tyto webové stránky používáte, jsou sdíleny se společností Google. Používáním těchto webových stránek souhlasíte s použitím souborů cookie.