Az utazó ügynök problémája

Az utazó ügynök problémája egy kombinatorikus optimalizálási probléma. Kiváló példa a bonyolultság-elmélet által NP-nehéznek nevezett problémaosztályra. Az utazó ügynök problémájához kapcsolódó matematikai feladatokkal először Sir William Rowan Hamilton és Thomas Penyngton Kirkman foglalkoztak az 1800-as években. Hamilton és Kirkman ezen korai munkájáról szóló értekezés megtalálható a Graph Theory 1736-1936.^[1] című munkában. Az utazóügynök-probléma általános változatát először az 1930-as években vizsgálták Bécsben, illetve a Harvardon, kiváltképp Karl Menger. A problémával később Hassler Whitney és Merrill M. Flood is komolyan foglalkozott a Princetoni Egyetemen. Az utazóügynök-probléma fejlődéséről, valamint Menger és Whitney kapcsolatáról részletes információk találhatók Alexander Schrijver publikációjában.^[2]

Optimális útvonal Németország 15 legnagyobb városának bejárásához.
A 43 589 145 600 lehetséges útvonalból ez a legrövidebb

A probléma

Ha az ügynök az A pontból indul, és minden pontpár között ismeri a távolságot, akkor melyik a legrövidebb út, melyen végighaladva érinti az összes pontot, és A-ba tér vissza?

Adva van n város, illetve az útiköltség bármely két város között, keressük a legolcsóbb utat egy adott városból indulva, amely minden várost pontosan egyszer érint, majd a kiindulási városba ér vissza.

${\displaystyle {\frac {(n-1)!}{2}}}$ út közül kell választanunk, ez ugyanis a Hamilton-körök száma az n pontú teljes gráfban.

Megjegyzés: Ez a képlet csak ${\displaystyle n>2}$ esetén működik.

Kapcsolódó problémák

1. Ekvivalens gráfelméleti megfogalmazása a problémának: Adott teljes élsúlyozott gráf esetén keressük a legkisebb összsúllyal rendelkező Hamilton-kört. Megmutatható, hogy a kiindulási városba való visszatérés megkövetelése nem nehezít a probléma számítási nehézségén, tehát minimális súlyú Hamilton-út keresése egy adott pontból is NP-teljes.
2. A probléma egy másik változata, amikor nem a legkisebb súlyú Hamilton-kört keressük, hanem azt, amelyikben a „legnehezebb” él súlya a lehető legkisebb. A logisztikai problémákon túl nagy gyakorlati jelentőséggel bír például a nyomtatott áramkörök gyártása során fúrórobotok ideális mozgásának megtervezésében.
3. Az utazóügynök-probléma általánosított változatában „országok” szerepelnek egy vagy több „várossal”, az ügynök minden országból pontosan egy várost köteles meglátogatni, majd visszatérni kiindulási helyére. Behzad és Modarres^[3] megmutatta, hogy az általánosított utazóügynök-probléma visszavezethető egy standard utazóügynök-problémára azonos mennyiségű várossal, más súlyozással.

Számítási nehézség

A legkézenfekvőbb megoldás az összes permutáció végignézése, és a legkisebb súlyú kiválasztása lenne, de tekintve, hogy ez n! darab permutációt jelent (ahol n a városok száma), nagyobb n-ekre ez a megoldás kivitelezhetetlen. Dinamikus programozási technikák segítségével a probléma megoldásának lépésszáma felülről becsülhető ${\displaystyle n^{2}2^{n}}$-nel.^[4] Ez még exponenciális függvénye n-nek, de sokkal jobb, mint az ${\displaystyle {n!}}$ lépést használó brute force („nyers erő”) módszer.

A probléma bizonyítottan NP-nehéz, annak eldöntése pedig, hogy adott x-re létezik-e x-nél olcsóbb megoldása a konkrét esetnek NP-teljes. A probléma különböző megszorító feltételek mellett is NP-nehéz marad: kiköthetjük, hogy a városok egy euklideszi síkon helyezkedjenek el a szokásos távolságfogalommal. Akkor sem egyszerűsödik a helyzet, ha elhagyjuk azt a feltételt, hogy az ügynök minden várost csak egyszer látogathat meg, hiszen könnyen látható, hogy euklideszi síkon amúgy is ez az optimális megoldás (a háromszög-egyenlőtlenség miatt).

Algoritmusok

Mivel tehát hatékony megoldás nem ismert a probléma megoldására sok város mellett, a következő célú algoritmusok a gyakoriak:

• A legjobb megoldást megkereső algoritmus, mely csak kisebb mennyiségű pontszám mellett hatékony.
• „Szuboptimális” vagy heurisztikus algoritmusok, melyek nagy valószínűséggel az optimális megoldáshoz jól közelítő megoldást adnak.
• A probléma speciális eseteivel foglalkozó, azt valamilyen megszorítás mellett hatékonyan megoldó algoritmusok.

Teljes megoldású algoritmus

Az idő múlásával az egyre finomodó technikáknak, és a számítástechnika fejlődésének köszönhetően egyre nagyobb mennyiségű városra sikerült megoldani a problémát (forrás: Georgia Tech):

• 1954: 49 amerikai város - G. B. Dantzig, D. R. Fulkerson és S. Johnson.
• 1977: 120 város Németország környékéről - M. Grötschel.
• 1987: 2392 pont - M. W. Padberg és G. Rinaldi.
• 2004: Svédország 24 978 városa - D. Applegate, R. Bixby, V. Chvátal, W. Cook és K. Helsgaun.
• 2006: egy 85 900 pontú probléma megoldása a CONCORDE algoritmus segítségével - D. Applegate, R. Bixby, V. Chvátal, W. Cook, D. Espinoza, M. Goycoolea és K. Helsgaun.^[5]

Jegyzetek

1. N.L. Biggs, E.K. LLoyd, and R.J. Wilson, Graph Theory 1736-1936, Clarendon Press, Oxford, 1976.
2. Schrijver, Alexander "On the history of combinatorial optimization (till 1960)," Handbook of Discrete Optimization (K. Aardal, G.L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam, 2005, pp. 1-68. PS, PDF
3. (2002) „New Efficient Transformation of the Generalized Traveling Salesman Problem into Traveling Salesman Problem”. Proceedings of the 15th International Conference of Systems Engineering (Las Vegas).
4. (1962) „A Dynamic Programming Approach to Sequencing Problems”. Journal of the Society for Industrial and Applied Mathematics 10 (1), 196-210. o. DOI:10.1137/0110015.
5. CONCORDE solves Traveling Salesman Problem. [2008. április 18-i dátummal az eredetiből archiválva]. (Hozzáférés: 2008. március 30.)

Hivatkozások

• A probléma a Mathworld honlapján.
• Encyclopedia of Mathematics
• TSPLIB: Algoritmusok tesztelésére szolgáló mintabemenetek.
• A Georgia Tech Archiválva 2006. február 7-i dátummal a Wayback Machine-ben gyűjteménye a témáról.
• Alice és Bob - 6. rész: Alice és Bob a kiszámíthatóság határán
• Alice és Bob - 7. rész: Alice és Bob egymillió dolláros kérdése
• Alice és Bob - 8. rész: Alice és Bob biztonsága

Kapcsolódó szócikkek

• Kínaipostás-probléma