Problém obchodného cestujúceho

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Problém obchodného cestujúceho (z angl. travelling salesman problem - skratka TSP) je jedna z najznámejších optimalizačných úloh. Je to aj vďaka veľkému množstvu jej praktických aplikácií (rozvoz tovaru, osadzovanie súčiastok plošného spoja a podobne).

Podstata problému[upraviť | upraviť zdroj]

Nech je daných N miest a nech je možné dostať sa z každého mesta do všetkých ostatných (buď priamo alebo cez niektoré iné mesto). Nech je každá cesta medzi dvomi navzájom prepojenými mestami ohodnotená číslom, ktoré môže vyjadrovať vzdialenosť, cenu, čas atď. Cieľom obchodného cestujúceho je vybrať sa z mesta, v ktorom sa práve nachádza, navštíviť každé mesto práve raz a vrátiť sa do počiatočného mesta. Pritom sa snaží túto cestu absolvovať tak, aby precestoval čo najmenšiu vzdialenosť, zaplatil čo najmenej peňazí a podobne.

Dejiny[upraviť | upraviť zdroj]

Problém obchodného cestujúceho sa datuje od 19. storočia. V tom období sa ním zaoberal írsky matematik Sir William Rowan Hamilton a britský matematik Thomas Kirkman. V tridsiatych rokoch 20. storočia bola na univerzite vo Viedni a Harvarde popísaná presnejšia matematická formulácia. Neskôr zohrala veľkú rolu výpočtová technika, ktorá taktiež umožnila vyriešenie úlohy až s 24 978 švédskymi mestami v roku 2004.

Problém obchodného cestujúceho v teórii grafov[upraviť | upraviť zdroj]

V terminológii teórie grafov jednotlivé mestá predstavujú vrcholy, prepojenia medzi mestami sú hrany. Ide o hranovo ohodnotený súvislý graf G=(V, H), v ktorom hľadáme hamiltonovskú kružnicu, ktorá má minimálny súčet ohodnotení hrán.

Základné definície a pojmy:

Hamiltonovská kružnica je taký podgraf, ktorý je kružnica a obsahuje všetky vrcholy pôvodného grafu.

Graf G, ktorý má aspoň jednu hamiltonovskú kružnicu, nazývame hamiltonovským grafom.

Nech pre ľubovoľné dva nesusedné vrcholy u, v grafu G=(V, H), |V| = n, n ≥ 3, platí: \delta(u)+\delta(v)\ge n, potom G je hamiltonovský graf.

Nech G=(V, H), |V| = n, n ≥ 3. Nech pre každé celé číslo j, 1 \le j \le \frac {n}{2}, počet vrcholov stupňa najviac j je menší než j, potom graf G obsahuje hamiltonovskú kružnicu.

Pre kompletný graf Kn, kde n ≥ 3, počet všetkých rôznych hamiltonovských kružníc vieme určiť podľa nasledujúceho vzťahu: \frac {1}{2} (n-1)!

Riešenie problému[upraviť | upraviť zdroj]

Problém obchodného cestujúceho je klasifikovaný ako tzv. NP-úplný. To znamená, že so vzrastajúcim počtom miest rastie čas riešenia exponenciálne. Napríklad, ak vezmeme kompletný graf, tak pri návšteve 4 miest máme tri potenciálne cesty. Návšteva 12 miest bude znamenať už takmer 20 miliónov možností. Pri 16 mestách sa číslo šplhá až na neuveriteľných viac ako 653 biliónov potenciálnych ciest. Zatiaľ však nie je známy žiaden efektívny algoritmus, ktorý by v polynomiálnom čase rozhodol o riešení.

K problému môžeme pristupovať tromi základnými spôsobmi:

  • algoritmy pre presné nájdenie riešenia (pre problémy s malým počtom vrcholov)
  • suboptimálne a heuristické algoritmy (osvedčené v dostatočnom počte prípadov, nedokázateľné, nemusia zaručovať optimálne riešenia ani hromadnosť)
  • nájdenie špeciálneho prípadu, pre ktorý vieme určiť presné riešenie

Sú známe niektoré možnosti riešenia z rôznych oblastí:

  • Umelá inteligencia:
    1. neurónové siete:
      • Hopfieldova sieť
    2. prírodne inšpirované prehľadávacie algoritmy:
      • umelé mravce
      • evolučné, genetické algoritmy
      • simulované žíhanie
  • Znalostné systémy:
    1. rozhodovacie stromy


Príklad[upraviť | upraviť zdroj]

Máme riešiť problém obchodného cestujúceho, ktorého graf je na nasledujúcom obrázku:

TSP graf1.jpg

Pre nájdenie riešenia použijeme rozhodovací strom. Obchodný cestujúci vychádza z mesta A a môže ísť buď do mesta B alebo C. Ak sa rozhodne pre B, opäť má možnosť vybrať si mesto D alebo G. Tento postup opakujeme a vytvárame z týchto výberov ciest rozhodovací strom, kde mesto A predstavuje koreňový uzol. Rozhodovací strom bude mať takúto podobu:

TSP graf2.jpg

Z rozhodovacieho stromu zistíme, že v grafe existuje 6 hamiltonovských kružníc:

  • ABDGHFECA (1)
  • ABGHEFDCA (2)
  • ABGDFHECA (3)
  • ACEHFDGBA (4)
  • ACEFHGDBA (5)
  • ACDFEHGBA (6)

Hamiltonovské kružnice (1) a (5), (2) a (6), (3) a (4) sú rovnaké, líšia sa len smerom „obehu“. Preto ďalej uvažujeme len kružnice (1), (2) a (3). Vypočítame súčty ohodnotení hrán:

  • (1) – 18
  • (2) – 24
  • (3) – 23

Snahou obchodného cestujúceho je cestovať tak, aby prešiel najmenšiu vzdialenosť. Preto riešením tejto úlohy sú hamiltonovské kružnice (1) a (5) so súčtom ohodnotení hrán 18.

Využitie[upraviť | upraviť zdroj]

Problém obchodného cestujúceho má množstvo praktických aplikácií. Využíva sa pri plánovaní dopravy, v prevádzkach, pri umiestňovaní zariadení, plánovaní výroby a riadení dodávateľského reťazca. Napríklad, môže pomôcť znížiť výrobné náklady, ak sa stanoví najefektívnejší model pre dierovanie otvorov do dosky plošných spojov alebo iných predmetov. Otvory, ktoré je potrebné vyvŕtať predstavujú počet miest a čas potrebný k posunu vŕtacej hlavy od jednej diery k nasledujúcej predstavuje cestovné náklady.

Záver[upraviť | upraviť zdroj]

Hoci je problém obchodného cestujúceho známy už pomerne dlho, ešte stále nebol nájdený efektívny algoritmus. Dokonca väčšina odborníkov sa domnieva, že ho nebude možné nikdy riešiť polynomiálnymi algoritmami kvôli jeho zložitosti.

Zdroje[upraviť | upraviť zdroj]