TSP (utazóügynök-probléma) — definíció, történelem és megoldások

Rövid történet

Az utazó ügynök problémáját az 1800-as években W. R. Hamilton (William Rowan Hamilton) ír matematikus és Thomas Kirkman brit matematikus tette ismertté. A Hamilton-féle Icosian Game egy szabadidős rejtvény volt, amely egy Hamilton-ciklus megtalálásán alapult. Úgy tűnik, hogy a TSP általános formáját először matematikusok tanulmányozták az 1930-as években Bécsben és a Harvardon, nevezetesen Karl Menger. Menger definiálja a problémát, megvizsgálja a nyilvánvaló nyers erővel megoldható algoritmust, és megfigyeli a legközelebbi szomszéd heurisztika nem optimális voltát:

Futárproblémának nevezzük (mivel a gyakorlatban ezt a kérdést minden postásnak, egyébként is sok utazónak kell megoldania) azt a feladatot, hogy figyelemszámú pontra, amelyek páros távolságai ismertek, meg kell találni a pontokat összekötő legrövidebb utat. Természetesen ez a feladat véges sok próbával megoldható. Olyan szabályok, amelyek a próbák számát az adott pontok permutációinak száma alá szorítanák, nem ismertek. Az a szabály, hogy a kiindulási pontból először a legközelebbi ponthoz, majd az ehhez legközelebbi ponthoz stb. kell menni, általában nem adja meg a legrövidebb utat.

Hassler Whitney a Princeton Egyetemen nem sokkal később bevezette az utazó ügynök problémáját. Azóta a TSP rengeteg elméleti eredmény és gyakorlati megoldóeszköz tárgya lett, és alapvető benchmarkként szolgál optimalizáló algoritmusok és heurisztikák teszteléséhez.

Formális definíció

Általános formában a TSP a következő: adott egy teljes, súlyozott gráf G = (V, E) és egy súlyfüggvény w: E → R+, találjuk meg azt a Hamilton-kört (azaz egy olyan zárt útvonalat, amely minden csúcsot pontosan egyszer látogat meg), amelynek az élsúlyok összege minimális. Gyakori speciális esetek:

• Symmetrikus TSP (STSP): a távolságok szimmetrikusak, w(u,v) = w(v,u).
• Aszimmetrikus TSP (ATSP): a távolságok irányfüggők, például irányított gráfként értelmezve.
• Metriás TSP: a távolságok teljesítik a háromszög-egyenlőtlenséget; ez gyakori a tényleges geometriai (pl. euklideszi) adatoknál.
• Euclidean TSP: pontok a síkon (vagy magasabb dimenzióban), távolságok euklidesziak — fontos speciális eset, amelyre hatékony közelítő eljárások léteznek.

Komplexitás és elméleti eredmények

• A TSP döntési változata (van-e olyan körút, amely súlya ≤ K?) NP-teljes. A (optimalizációs) TSP optimalizálása NP-nehéz feladat.
• Általános (nem-metriás) TSP-re nem ismert polinomidőben futó optimális algoritmus, és a probléma mérete gyorsan nő; emiatt gyakran közelítő algoritmusokat és heurisztikákat alkalmaznak.
• A Euclidean TSP-nek létezik PTAS (polynomial-time approximation scheme): Arora és Mitchell független munkái bizonyították, hogy tetszőlegesen jó közelítést lehet polinom időben elérni, ha a dimenzió rögzített.

Megoldási módszerek

Az alkalmazott módszerek két nagy csoportba sorolhatók: pontos (exact) algoritmusok, amelyek garantáltan optimális megoldást adnak, és közelítő vagy heurisztikus eljárások, amelyek gyorsak és gyakran jó (de nem mindig optimális) eredményt hoznak.

Pontos algoritmusok

• Bruteforce: összes permutáció kipróbálása — O(n!) idő; csak nagyon kis n-re használható.
• Dinamikus programozás (Held–Karp): O(n^2 2^n) idő és O(n 2^n) memória; sokkal jobb a bruteforce-nál, de még mindig exponenciális.
• Branch and bound: hatékony fa-alapú keresés, amely alsó becslésekkel metszi a keresési teret; nagy gyakorlati sikereket ért el közepes méretű példákon.
• Lineáris programozás és vágási síkok: az ILP-formuláció (subtour elimination constraints — körszétválasztó feltételek) kombinálása vágási síkokkal hatékony módszereket eredményezett; a Concorde nevű solver ilyen technikákat használ.

Közelítő algoritmusok és garanciák

• Christofides-algoritmus: metriás, szimmetrikus TSP-re 1,5-szeres közelítési garanciát ad (vagyis a megtalált körút hossza legfeljebb 1,5-szerese az optimálisnak).
• Általános aszimmetrikus esetekre és nem-metriás esetekre más közelítések és garanciák léteznek; a kutatás területén folyamatos előrelépések történnek a közelítési tényezők javításában.

Heurisztikák (praktikus, gyors módszerek)

• Legközelebbi szomszéd (Nearest Neighbor): egyszerű és gyors, de gyakran távol van az optimálistól.
• Beszúrásos módszerek (Nearest/Best insertion): pontok fokozatos hozzáadása egy részútvonalhoz.
• 2-opt, 3-opt: lokális keresés, amely élcserékkel javítja a kört; ezek nagyon hatékonyak gyakorlatban.
• Lin–Kernighan és variánsai: adaptív, erős lokális kereső, amely a legjobb ismert heurisztikák közé tartozik sok valós probléma esetén.

Gyakorlati eszközök és adatkészletek

• Concorde: nagyon hatékony pontos TSP-solver, amely kombinálja az ILP-, vágási sík- és branch-and-bound technikákat; gyakran használják rekordproblémák megoldására.
• TSPLIB: ismert benchmark-adatbázis valós és mesterséges TSP-példákkal, amely a kutatás és összehasonlítás alapját képezi.

Alkalmazások

A TSP nemcsak elméleti érdeklődés tárgya: számos gyakorlati probléma redukálható rá vagy jó analógia vele. Néhány példa:

• Logisztika és szállítmányozás (útvonaltervezés).
• Gyártás és gyártósor-optimalizáció (pl. hegesztési utak minimalizálása).
• Elektronikai áramkörök optimalizálása (drótok rendezése, nyomtatott áramköri lapok).
• Bioinformatika (például bizonyos genom-összeillesztési problémák közelítése).
• Robotika és path planning — több pont látogatása minimális energiával vagy idővel.

Összefoglalás és további olvasmány

A TSP egy egyszerűen megfogalmazható, de elméletileg és számítási szempontból nagy kihívást jelentő probléma. A kutatás kiterjed az egzakt algoritmusok fejlesztésétől a jobb közelítések és heurisztikák kidolgozásáig, valamint speciális esetek (például euklideszi TSP) hatékonyabb kezelhetőségére. Ha tovább szeretnél mélyedni a témában, érdemes megnézni klasszikus forrásokat (például könyveket az operációkutatásról és kombinatorikus optimalizálásról), a Concorde dokumentációját és a TSPLIB példáit.