tag:blogger.com,1999:blog-9210966517210062357.post41099714155921849..comments2023-06-06T18:13:57.732+02:00Comments on Česká škola: Problém obchodního cestujícíhoAdminAMhttp://www.blogger.com/profile/10505144085274313295noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-9210966517210062357.post-24261857925198896742016-04-30T10:09:24.669+02:002016-04-30T10:09:24.669+02:00Proč by obecné řešení neexistovalo? Existuje a nem...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.<br /><br />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.Pavel Doleželhttps://www.blogger.com/profile/06619131298655488174noreply@blogger.comtag:blogger.com,1999:blog-9210966517210062357.post-18819902276673043182016-04-30T09:56:38.182+02:002016-04-30T09:56:38.182+02:00Jedná se o matematický problém z teorie grafů. Pro...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í.Anonymoushttps://www.blogger.com/profile/13385588715290569278noreply@blogger.comtag:blogger.com,1999:blog-9210966517210062357.post-67521967301860530782016-04-29T14:41:51.066+02:002016-04-29T14:41:51.066+02:00V tom nadpisu to není napsáno úplně přesně. Problé...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.<br /><br />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ý.Pavel Doleželhttps://www.blogger.com/profile/06619131298655488174noreply@blogger.com