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
Nejčtenější články
Č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.
Tento server dodržuje právní předpisy
ISSN 1213-6018
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.
Tento server dodržuje právní předpisy
o ochraně osobních údajů.
ISSN 1213-6018
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.
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.
3 komentářů:
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ý.
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í.
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.
Okomentovat