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

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. Ebben az összefüggésben a jobb megoldás gyakran olyan megoldást jelent, amely olcsóbb, rövidebb vagy gyorsabb. A TSP egy matematikai probléma. Legegyszerűbben egy csomópontok halmazának helyét leíró gráfként fejezhető ki.

Az utazó ügynök problémáját az 1800-as években W. R. Hamilton ír matematikus és Thomas Kirkman brit matematikus határozta meg. 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.

William Rowan Hamilton

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.

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ő)?

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.