Az utazó ügynök problémája
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.[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]
A probléma[szerkesztés]
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.
ú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 esetén működik.
Kapcsolódó problémák[szerkesztés]
- 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.
- 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.
- 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[szerkesztés]
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ő -nel.[4] Ez még exponenciális függvénye n-nek, de sokkal jobb, mint az 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[szerkesztés]
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[szerkesztés]
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[szerkesztés]
- ↑ N.L. Biggs, E.K. LLoyd, and R.J. Wilson, Graph Theory 1736-1936, Clarendon Press, Oxford, 1976.
- ↑ 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
- ↑ (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).
- ↑ (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.
- ↑ 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[szerkesztés]
- 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