AlegsaOnline.com

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

TSP (utazóügynök-probléma) – áttekintés: definíció, történet és hatékony megoldások; algoritmusok, heuristikák és gyakorlati alkalmazások egyszerűen és szakmailag.

Szerző: Leandro Alegsa

02-04-2026

A Traveling Salesman Problem (gyakran TSP) egy klasszikus algoritmikus probléma a számítástechnika és az operációkutatás területén. Az optimalizálásra összpontosít: adott pontok (vagy városok) és a köztük lévő távolságok ismeretében meg kell találni azt az utat (körutat), amely minden pontot pontosan egyszer érint és minimális össztávolsággal rendelkezik. Legegyszerűbben egy csomópontok halmazának helyét leíró gráfként fejezhető ki: a gráf teljes, élei súlyozottak, és a cél egy minimális súlyú Hamilton-kör megtalálása.

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 ﬁgyelemszá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.

Egy üzletkötő szeretné meglátogatni az összes várost,A, B, C és D. Mi a legjobb módja ennek (legolcsóbb repülőjegyek és minimális utazási idő)?

Egy Németország 15 legnagyobb városát felkereső üzletkötő optimális útvonala. Az ábrázolt útvonal a legrövidebb a 43 589 145 600 lehetséges útvonal közül.

A probléma megfogalmazása

Az utazó ügynök problémája egy olyan ügynököt ír le, akinek N város között kell utaznia. Az, hogy ezt milyen sorrendben teszi, nem érdekli, amíg útja során minden várost egyszer meglátogat, és ott ér célba, ahol először járt. Minden város repülőgépen, közúton vagy vasúton kapcsolódik más közeli városokhoz, vagyis csomópontokhoz. A városok közötti kapcsolatok mindegyikéhez egy vagy több súly (vagy költség) tartozik. A költség azt írja le, hogy mennyire "nehéz" áthaladni ezen az élen a gráfon, és megadható például egy repülőjegy vagy vonatjegy árával, esetleg az él hosszával vagy az áthaladáshoz szükséges idővel. Az értékesítő mind az utazási költségeket, mind a megtett távolságot a lehető legalacsonyabban szeretné tartani.

Az utazó ügynök probléma tipikusan a "nehéz" optimalizálási problémák egy nagy osztályába tartozik, amelyek évek óta izgatják a matematikusokat és az informatikusokat. A legfontosabb, hogy a természettudományokban és a mérnöki tudományokban is vannak alkalmazásai. Például egy áramköri lap gyártása során fontos meghatározni a legjobb sorrendet, amelyben egy lézer több ezer lyukat fúr. E probléma hatékony megoldása csökkenti a gyártó gyártási költségeit.

Nehézségi szint

Általában az utazó ügynök problémája nehezen megoldható. Ha van mód arra, hogy ezt a problémát kisebb komponensproblémákra bontsuk, akkor a komponensek legalább olyan bonyolultak lesznek, mint az eredeti probléma. Ezt nevezik az informatikusok NP-nehez problémának.

Sokan tanulmányozták ezt a problémát. A legegyszerűbb (és legdrágább) megoldás, ha egyszerűen minden lehetőséget kipróbálunk. Ezzel az a probléma, hogy N város esetében (N-1) faktoriális lehetőség van. Ez azt jelenti, hogy mindössze 10 város esetében több mint 180 ezer kombinációt lehet kipróbálni (mivel a kezdő város meghatározott, a maradék kilencre is lehetnek permutációk). Mi csak a felét számoljuk, mivel minden útvonalnak van egy ugyanolyan hosszúságú vagy költségű útvonala visszafelé is. 9! / 2 = 181 440

A probléma pontos megoldása ág és korlát algoritmusok segítségével megoldható. Ez jelenleg 85 900 város esetében lehetséges.
A heurisztikus megközelítések a következő csomópont kiválasztásához egy sor irányadó szabályt használnak. Mivel azonban a heurisztikák közelítéseket eredményeznek, nem mindig adnak optimális megoldást, bár a jó minőségű, elfogadható heurisztikák a probléma teljes nyers erővel történő megoldásához szükséges idő töredéke alatt találhatnak hasznos megoldást. Egy csomópontra vonatkozó heurisztika példája lehet annak összegzése, hogy hány nem látogatott csomópont van "közel" egy összekapcsolt csomóponthoz. Ez arra ösztönözhetné az értékesítőt, hogy meglátogasson egy csoport közeli csomópontot, amelyek együtt vannak klaszterezve, mielőtt továbblépne a gráf egy másik természetes klaszterére. Lásd Monte Carlo algoritmusok és Las Vegas algoritmusok.

Kérdések és válaszok

K: Mi az az utazó ügynök probléma?

V: A Traveling Salesman Problem (TSP) egy klasszikus algoritmikus probléma az informatika és az operációkutatás területén. Az optimalizálásra összpontosít, a jobb megoldások gyakran olcsóbb, rövidebb vagy gyorsabb megoldásokat jelentenek.

K: Hogyan fejezik ki a TSP-t?

V: A TSP legegyszerűbben egy gráfként fejezhető ki, amely egy csomóponthalmaz helyét írja le.

K: Ki határozta meg először a TSP-t?

V: Az utazó ügynök problémát az 1800-as években W. R. Hamilton ír matematikus és Thomas Kirkman brit matematikus definiálta.

K: Ki tanulmányozta tovább az 1930-as években?

V: Az 1930-as években Karl Menger bécsi és harvardi matematikusok tanulmányozták tovább.

K: Mit vezetett be nem sokkal később Hassler Whitney?

V: Hassler Whitney a Princeton Egyetemen nem sokkal a meghatározása után bevezette az "utazó ügynök problémája" elnevezést.

K: Mit jelent ebben az összefüggésben a "jobb megoldás" kifejezés?

V: Ebben az összefüggésben a jobb megoldás gyakran olyan megoldást jelent, amely olcsóbb, rövidebb vagy gyorsabb.

K: Milyen algoritmust tartott Menger kézenfekvőnek a TSP tanulmányozása során?

V: Menger a TSP tanulmányozásakor nyilvánvalónak tekintette a nyers erő algoritmust, és megfigyelte, hogy a legközelebbi szomszéd heurisztika használata nem mindig ad optimális eredményt.