Az utazó ügynök dilemmája

Napjainkban sok kiskategóriás autóban van már navigációs rendszer, a matematikusokat mégis kétségbe ejti az útvonaltervezés problémája. Aki megoldja, annak milliódolláros jutalmat ígérnek.Ha valaki a leggyorsabb úton akar eljutni Augsburgból Zwickauba, akkor egyszeríen begépeli a két város nevét a navigációs rendszerbe, és másodperceken belül megkapja az optimális útvonalat. Amennyiben az autós útközben az alábbi sorrendben Berlint, Chemnitzet, Düsseldorfot és Erfurtot is meg akarja látogatni, az sem jelent nehézséget az elektronika számára: egyszeríen kiszámítja egymás után a legjobb útvonalat Augsburgból Berlinbe, majd Berlinből Chemnitzbe és így tovább. A helyzet akkor válik igazán bonyolulttá, amikor egy adott számú városba nem egymás után, hanem a legrövidebb útvonalon kell eljutni. Ha egy utazó például Augsburg és Zwickau között a legrövidebb úton 26 várost akar érinteni, akkor az útvonal megtervezésével a világ leggyorsabb számítógépe is túl lenne terhelve. Ha a városok között csupán egy út létezne, akkor is 400 quadrillió (egy quadrillió = egy egyes, amely után 24 nulla áll) útvonal lenne lehetséges, amely elképzelhetetlenül nagy szám. A4-es papíron ezresével elhelyezve az útvonalterveket akkora papírtornyot építhetnénk, amely  egészen az Alfa Centauri csillagegyüttesig érne. Mind a mai napig nem ismert olyan hatékony eljárás, amellyel úgy lehet a leggyorsabb utat megtalálni, hogy ne kelljen túlságosan sok alternatívát elemezni.

A legrövidebb út másképpen
Szakmai körökben ezt a problémát az „utazó ügynök problémájaként” ismerik. A valóságban ez a kérdés kevésbé a területi képviselői körökben, sokkal inkább számítógép-processzorok készítésénél vagy szerszámgépek vezérlésénél kerül elő. Az iparnak és a feltalálónak is egyaránt megérné egy ilyen módszer, illetve sok köztes állomású optimális útvonal megtalálása, mivel az utazó ügynök problémájának megoldásáért az amerikai Clay Foundation egymillió amerikai dollárt fizet. Az alapítvány azonban nem azért írta ki a pályázatot, hogy a navigációs rendszerek és a processzorok még nagyobb teljesítményíek legyenek, számukra az utazó ügynök problémájának matematikai jelentősége a fontosabb: ha egy napon valaki feltörné ezt a diót, azzal – bizonyos, a matematikusok számára egyszerí módosításokkal – egyszerre több száz másik matematikai feladat válhatna megoldhatóvá. Martin Grötschel professzor szerint ezek a problémák majdnem mindenhol előkerülnek: a telekommunikációban, gyártási, szállítmányozási vagy közlekedési folyamatok szervezésénél, vagy processzorok tervezésénél. Az olyan feladatok, mint a növekvő sor- és oszlopszámú Sudokuk megoldása, szinte mindennaposak. Három további példa:

– Bevásárláskor az élelmiszerboltban az árukat egyenletesen kell szétosztani két táskába, hogy azok egyformán nehezek legyenek.
– Egy háziasszony 3 óra leforgása alatt akar kitakarítani, bevásárolni, háromfogásos menüt főzni, lezuhanyozni, ünnepélyesen felöltözni és kisminkelni magát. Megvalósítható-e ez, ha mindent a legkedvezőbb sorrendben végez el?
– Egy vállalkozás új mobiltelefon-hálózatot tervez 10 000 adóoszloppal, 100 különböző frekvencia alkalmazása mellett. El lehet-e úgy rendezni az antennákat, hogy az egymással szomszédosak ne sugározzanak azonos frekvencián?
Ezen problémák egyikét sem tudjuk mind a mai napig gyors eljárással megoldani, pedig ha valaki találna egy hatékony módszert a helyzetek egyikének megfejtésére, azzal megoldhatóvá válna a többi felvetés is.

Akármennyire eltérőnek hatnak is az egyes feladatok, mégis vannak hasonlóságok közöttük. Mellesleg annál összetettebbek lesznek a problémák, minél nagyobb lesz a beadott adatok mennyisége. Ha öt árut kell minél egyenletesebben elosztani két táska között, akkor minden lehetőséget ki lehet próbálni. 100 darab árunál már belekerül némi időbe, de 100 000 darabnál lehetetlenné válik. Ugyanígy, annál inkább nehezednek a háziasszony és a telekommunikációs vállalat optimalizálási feladatai is, minél több tevékenységet kell elvégeznie, illetve minél több antennát és frekvenciát kell szétosztania.Mindhárom esetben sokkal nehezebb a megoldást megtalálni, mint eldönteni, hogy egy adott módszer helyes-e. Mert ahhoz csak egy mérlegre kell rakni a táskákat, megkóstolni a háziasszony főztjét és véleményezni a külsejét, illetve ellenőrizni az adóoszlopok terveit. Ez leginkább egy kirakójátékra emlékeztet: sok türelemre van szükség, hogy minden darabját megfelelően egymáshoz illesszük. Amikor azonban elkészül a kirakó, akkor egy pillanat alatt látni, hogy minden rendben van-e. Az utazó ügynök problémájánál is könnyedén megállapítják a matematikusok, hogy az útvonal a legrövidebb-e.

Az np-problémák és megoldásuk
Az olyan feladatokat, amelyeknél egyszerí kideríteni, hogy egy adott megoldás helytálló-e, a matematikusok np-problémáknak nevezik. Ezek között vannak nehezebbek, mint a fentebb említett problémák, és viszonylag egyszeríek, mint például két szám összegzése. Az utóbbiak röviden p-problémák. Hogy mi az egyszerí, vagy nehéz, azt a matematikusok világosan kimutatták. Amennyiben egy feladat n tényezőből tevődik össze, akkor az egyszerí feladatokat annyi számítási lépéssel lehet elvégezni, amit az n hatványaival lehet megadni, úgymint n2 vagy n3 lépéssel. A nehezebbeknél ez azonban nem lehetséges, mert ott a számítási igény exponenciálisan növekszik. &Iacutegy ebben az értelemben a legtöbb iskolai matematikafeladat, mint az összeadás, hatványozás, gyökvonás és egyenletmegoldás könnyínek tekintendő. Két ötjegyí szám összegzését öt számjegy összeadására és esetenként a tízesek áthozatalára lehet felbontani.

Amennyiben két százjegyí számot kell összegezni, akkor elegendő száz számítási mívelet is. Szorzásnál már egy kicsit összetettebbé válik a helyzet. Amennyiben két ötjegyí számot szorzunk egymással, akkor 25 szorzás és számjegyek összeadása szükséges. Százjegyí számoknál ez már 10 000 szorzás és összeadás lesz. A számítási lépések száma négyzetesen növekszik az összeszorzandó számok számjegyeinek számával. Ez ugyan gyors az egyszerí összeadáshoz viszonyítva, de szinte semmi az utazó ügynök problémájához képest. Ha ebben az esetben minden lehetőséget végigpróbálunk, az öt városnál 30 eshetőség, tíz városnál 3 628 800 és 100-nál már több mint az univerzumban található atomok száma (a pontos összeg egy 157 számjegyí szám). A számítási igény robbanásszeríen növekszik az ilyen megközelítési mód szerint, amikor mindent végigpróbálunk. Nincs az a szuperszámítógép, amely lépést tudna ezzel tartani.

Azonban létezhet egy furfangos eljárás, amellyel lerövidíthető ez a keresgélés. Matematikusaink ugyan egyes esetekben már meg tudják oldani az utazó ügynök problémáját, de olyan módszer, amely akármely városok tetszőleges összeállítására együttesen praktikusan alkalmazható, mind a mai napig nem ismert. Ha megtalálnák a megfelelő módszert, nemcsak az utazó ügynök problémája kerülne át a p-típusú problémák körébe, hanem azzal együtt több száz optimalizálási feladat is, mint a bevásárlótáska, a háziasszony és a mobilszolgáltatók problémája. Egy ilyen szenzáció az egymillió dollár minden egyes centjét megérné. Az iparnak hatalmas nyereség lenne, mivel fontos, a gyakorlatban felmerülő feladatokat rövid idő alatt optimálisan megoldhatnának vele.A bankok viszont egyik napról a másikra nagy bajba kerülnének, mivel a bankkártyaszámok internetes titkosítását például csak azért nem lehet feltörni, mert senki sem tud egy elegendően nagy – körülbelül 200 számjegyí – számot annak osztóira bontani. Azt, hogy 7 x 5 = 35, minden kisiskolás tudja, 758 717-nél azonban már nehezedik a helyzet. Egy számítógéppel meghatározhatóak ennek a számnak az osztói és így másodpercek alatt kiderül, hogy 758 717 = 761 x 997. Száznál több számjegyí számoknál viszont ezek keresése kilátástalan vállalkozás. Egy szám osztóira bontása a nehezebbnek gondolt np-osztályú feladatok közé tartozik.

Lehet azonban, hogy egy zseniális elme talál eljárást a nagy számok osztóira való bontására. Ezzel mintegy varázsütésre azt is bizonyítaná, hogy p=np, tehát sok, ma nehéznek tínő feladat valójában könnyí. Ilyen herkulesi tettel nem számol azonban a tudományos közösség egy tagja sem, hiszen azóta nem értek el jelentős előrelépést, amióta először megfogalmazódott a „p=np” kérdés. A legtöbb szakember meg van győződve arról, hogy p nem egyenlő np-vel. Egy ilyen kijelentés alátámasztására azonban bizonyítani kellene, hogy nem létezik hatékony megoldás az np-problémákra. Annak bizonyítása, hogy valami nem létezik nemcsak az ufók és a telepátia esetében nehézkes, hanem a matematikában is. Bátran kijelenthetjük, hogy az internetes pénzforgalom feltehetőleg egy ideig biztonságos marad. Szegény utazó ügynökünknek viszont valószíníleg még sok kerülőt számításba kell vennie.

  • Az utazó ügynök problémájának megoldásáért az amerikai Clay Foundation egymillió amerikai dollárt fizet.Egy háziasszony 3 óra leforgása alatt akar kitakarítani, bevásárolni, háromfogásos menüt főzni, lezuhanyozni, ünnepélyesen felöltözni és kisminkelni magát. Megvalósítható-e ez, ha mindent a legkedvezőbb sorrendben végez el?Annak bizonyítása, hogy valami nem létezik nemcsak az ufók és a telepátia esetében nehézkes, hanem a matematikában is.