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

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

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. 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.

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.

${\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 $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 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ő $n^{2}2^{n}$-nel. Ez még exponenciális függvénye n-nek, de sokkal jobb, mint az ${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.

Hivatkozások

• A probléma a Mathworld honlapján.
• Encyclopedia of Mathematics
• TSPLIB: Algoritmusok tesztelésére szolgáló mintabemenetek.
• A Georgia Tech 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ínai postás probléma