Problém obchodného cestujúceho, alebo "Travelling Salesman Problem" (TSP), je optimalizačný problém v informatike a operáciách výskumu, ktorý sa snaží nájsť najkratšiu možnú trasu, ktorou obchodný cestujúci môže navštíviť viacero miest a vrátiť sa na svoje pôvodné miesto.
Konkrétne, problém sa dá formulovať nasledovne:
Máme zoznam miest a vzdialeností medzi každými dvoma mestami. Cieľom je nájsť najkratšiu možnú cestu, ktorá začína a končí v rovnakom meste a obsahuje každé mesto presne raz.
Tento problém je známy svojou zložitosťou a patrí do triedy problémov NP-ťažkých, to znamená, že neexistuje známy efektívny algoritmus, ktorý by ho dokázal riešiť pre veľké súbory dát. Existuje mnoho heuristických a aproximovaných algoritmov, ktoré sa snažia nájsť dobre riešenie, ale aj tak to môže byť veľmi náročné.
Problém obchodného cestujúceho má mnoho praktických aplikácií, napríklad v logistike, plánovaní trás dopravy, robotike alebo výrobe obvodov.
Ku keške:
Jožko Mrkvička brigáduje v Pizzerii ako rozvozca/kuriér. Medzi jeho záľuby patria autá, informatika, zvieratá, potápanie,... a kešky (skôr jeho manželke). Vašou úlohou bude navrhnúť najrýchlejšiu možnú trasu rozvozu Pizze pre Jožka.
Pravidlá:
- Jožko rozvádza pizzu v aute. Začína a končí v Alžbetinom dvore (červená bodka).
- Jožko musí každé miesto na mape (biela bodka) navštíviť aspoň raz, aby tam mohol vyložiť zákazníkovi pizzu.
- V istom bode musí vystupiť z auta, preplávať (bodkovaná čiara) ku keške, ponoriť sa, zalogovať kešku a vrátiť sa späť k autu.
- Jožka zaujíma najrýchlejšia možná trasa zo všetkých možných trás, aby mohol byť čím skôr doma. Jedna z možných trás je napríklad:
0 - 5 - 6 - 2 - 13 - 1 - 14 - 12 - 7 - 12 - 8 - 1 - 13 - 10 - 9 - 10 - Petržalka - 3 - 4 - 11 - 10 - 13 - 1 - 0. Táto trasa by trvala 371 minút. Každá zastávka/mesto/dedina má buď svoje číslo alebo svoj názov.
- Jožko musí vyložiť všetky pizze a zároveň odloviť kešku v konečnom čase, ak nejakú pizzu nevyloží, vynadá mu zamestnávateľ. Ak vynechá kešku, vynadá mu manželka.
Keďže úloha spadá do kategórie NP-ťažká, ťažko povedať ktorá trasa je najlepšia. Existujú však rôzne heuristiky ktoré často ponúkajú takmer-ideálnu trasu v konečnom čase. Vašou úlohou je vybrať najrýchlejšiu trasu a vybrať sa na prislúchajúce súradnice, kde na vás bude čakať keška (ak si vyberiete správne). Pri výbere trasy dbajte na vyššie uvedené pravidlá.
1. Alžbetin dvor - Miloslavov - Most pri Bratislave - Podunajské Biskupice - Ružinov - Petržalka - Jarovce - Rusovce - 10 - Rovinka - 1 - Šamorín - Hamuliakovo - Kalinkovo - 7 - Dunajská Lužná - Alžbetin dvor = N48 05.633 E017 18.584
2. Alžbetin dvor - Dunajská Lužná - Šamorín - Hamuliakovo - Geokeška - Hamuliakovo - 14 - Dunajská Lužná - Rovinka - Jarovce - Rusovce - Jarovce - 11 - Staré Mesto - Ružinov - Podunajské Biskupice - Most pri Bratislave - Miloslavov - Alžbetin dvor = N48 05.467 E017 18.557
3. Alžbetin dvor - Dunajská Lužná - Kalinkovo - Geokeška - Kalinkovo - Hamuliakovo - Kalinkovo - Dunajská Lužná - Rovinka - Jarovce - Rusovce - Jarovce - Petržalka - Staré Mesto - Ružinov - 2 - 6 - Miloslavov - Alžbetin dvor = N48 05.511 E017 18.334
4. Miloslavov - Most pri Bratislave - Podunajské Biskupice - 4 - Staré Mesto - Petržalka - Jarovce - Rusovce - Geokeška - Rusovce - Jarovce - Rovinka - Dunajská Lužná - Kalinkovo - 12 - Šamorín - Dunajská lužná - Alžbetin dvor = N48 05.283 E017 18.086
5. Alžbetin dvor - 5 - Most pri Bratislave - 2 - Ružinov - Staré Mesto - Petržalka - Jarovce - Rusovce - Geokeška - Rusovce - Jarovce - Petržalka - Ružinov - Podunajské Biskupice - Rovinka - Dunajská Lužná - Šamorín - Hamuliakovo - Kalinkovo - Šamorín - Dunajská Lužná - Alžbetin dvor = N48 05.113 E017 18.516
6. Alžbetin dvor - Dunajská Lužná - Kalinkovo - Hamuliakovo - 8 - Dunajská Lužná - Rovinka - Jarovce - Rusovce - Jarovce - 11 - Staré Mesto - Ružinov - Podunajské Biskupice - Most pri Bratislave - Miloslavov - Alžbetin dvor = N48 05.770 E017 19.066
7. Alžbetin dvor - Dunajská Lužná - Kalinkovo - Geokeška - Kalinkovo - Dunajská Lužná - Alžbetin dvor = N48 05.991 E017 18.807
8. Alžbetin dvor - Miloslavov - Most pri Bratislave - Podunajské Biskupice - Ružinov - Staré Mesto - Petržalka - Jarovce - Rusovce - Jarovce - Rovinka - Dunajská Lužná - Kalinkovo - 7 - Kalinkovo - Hamuliakovo - Šamorín - Dunajská Lužná - Alžbetin dvor = N48 05.915 E017 18.785
9. 0 - Dunajská Lužná - 8 - Dunajská Lužná - Kalinkovo - Hamuliakovo - Geokeška - Hamuliakovo - Kalinkovo - Dunajská Lužná - Rovinka - Jarovce - Rusovce - Jarovce - 11 - Staré Mesto - Ružinov, Podunajské Biskupice - Most pri Bratislave - Miloslavov - 0 = N48 05.876 E017 18.673
10. Alžbetin dvor - Miloslavov - Most pri Bratislave - Podunajské Biskupice - Ružinov - Staré Mesto - Petržalka - Jarovce - 9 - 7 - 9 - 10 - Rovinka - Dunajská Lužná - Kalinkovo - Hamuliakovo - Šamorín - Dunajská Lužná - Alžbetin dvor = N48 04.887 E017 19.035
11. Alžbetin dvor - 1 - Kalinkovo - Hamuliakovo - Geokeška - Hamuliakovo - Šamorín - Dunajská Lužná - Alžbetin dvor - Miloslavov - Most pri Bratislave - Podunajské Biskupice - Rovinka - Jarovce - Rusovce - 10 - Petržalka - Staré Mesto - Ružinov - Podunajské Biskupice - Most pri Bratislave - Miloslavov - Alžbetin dvor = N48 04.711 E017 19.013
