ARTP - 01 - Problém obchodného cestujúceho

Zhrnutie prednášky

Prednáška zavádza problém obchodného cestujúceho (TSP): v neorientovanom grafe s nezápornými váhami hrán treba nájsť najkratší cyklus, ktorý navštívi každý vrchol práve raz. Problém je NP-ťažký, takže pri P ≠ NP preň neexistuje polynomiálny algoritmus; brute force cez permutácie má zložitosť n!, dynamické programovanie približne O(n²·2^n), čo je pre väčšie vstupy prakticky nepoužiteľné. Ako úvod k aproximácii prednášajúci predstavuje heuristiku pre euklidovský prípad: nájde sa najkratšia kostra, prehľadá sa do hĺbky, vznikne cyklus s opakovanými vrcholmi a ten sa skráti preskočením už navštívených vrcholov. Upozorňuje, že vo všeobecnom grafe toto skracovanie nefunguje, lebo priame hrany nemusia existovať alebo môžu byť veľmi dlhé.

• - TSP: nájsť najkratší cyklus navštevujúci každý vrchol práve raz v neorientovanom grafe s nezápornými váhami.
• - Problém je NP-ťažký; ak P ≠ NP, neexistuje polynomiálny algoritmus.
• - Brute force (permutácie, backtracking) má zložitosť n!, dynamické programovanie približne O(n²·2^n).
• - Exaktné exponenciálne algoritmy sú pre praktické vstupy príliš pomalé, preto sa hľadajú aproximácie.
• - Aproximačná myšlienka: najkratšia kostra, prehľadávanie do hĺbky a skrátenie cyklu vynechaním opakovaných vrcholov.
• - Skracovanie cez 'priame hrany' funguje v euklidovskom priestore, vo všeobecnom grafe nie.

Zhrnutie pripravené s pomocou AI z prepisu videa.