Šį už­da­vi­nį šim­tai moks­li­nin­kų te­be­spren­džia dau­giau nei 50 me­tų, spren­di­mo au­to­riui ža­da­mos mi­li­jo­ni­nės pre­mi­jos, ta­čiau spren­di­mo ne tik kad nė­ra, bet ir ne­aiš­ku, ar jis išvis eg­z­is­tuo­ja.

O uždavinio sąlyga labai paprasta: rasti keliaujančiam pirkliui trumpiausią miestus jungiantį maršrutą, kuris prasideda ir baigiasi tame pačiame mieste.

Dėl internetinės prekybos išnykus keliaujantiems pirkliams, atrodytų, uždavinys turėjo prarasti aktualumą (na, išskyrus pokemonų gaudytojus, kuriems svarbu surasti visus pokemonus savo mieste medžioklę pradedant ir užbaigiant savo namuose). Tačiau taip neįvyko. Keliaujančio pirklio uždavinys daug įdomesnis nei atrodo iš pirmo žvilgsnio.

Istorija

Keliaujančio pirklio uždavinys, manoma, buvo sugalvotas – ar bent jau paskelbtas – XIX amžiuje. Mokslininkai jį tuomet suformulavo kaip trumpiausio Hamiltono ciklo radimo pilnai jungiame grafe uždavinį, o buitiškesnis „keliaujančio pirklio uždavinio“ pavadinimas atsirado tik po šimtmečio.

Keliaujančio pirklio bėdos rimtesnio matematikų susidomėjimo sulaukė tik 1930 m. Atsiradus skaičiavimo mašinoms, šis uždavinys tapo dar svarbesnis: jam spręsti buvo kuriami įvairūs algoritmai, rengiami optimalių maršrutų sudarymo konkursai, uždavinio sprendinių pavaizdavimu susidomėjo ir skaitmeninio meno kūrėjai.

Žymiausią ir daugiausiai matematikų dėmesio atkreipusį keliaujančio pirklio uždavinio konkursą 1962 m., reklamuodama televizijos serialą „Car 54“, paskelbė kompanija Procter & Gamble. Konkurso dalyviams reikėjo surasti trumpiausią maršrutą, kuriuo serialo herojai policininkai Toody ir Muldoon aplankytų 33 JAV miestus. Nugalėtojo laukė 10 tūkstančių dolerių, už kuriuos 7 dešimtmetyje JAV buvo galima nusipirkti namą. Prizu susigundė ir matematikai, tad galiausiai prizą teko padalinti daugybei „teisingo“ sprendinio autorių.

Tuomet atrodęs itin sudėtingas uždavinys, dabar lengvai išsprendžiamas. Pavyzdžiui, 2004 m. buvo rastas trumpiausias, ~72 tūkst. kilometrų ilgio, maršrutas, jungiantis 24978 Švedijos miestus.

Uždavinio sudėtingumas

Tai kurgi visas uždavinio sudėtingumas? Miestų skaičius žinomas ir antrąkart lankytis tame pačiame mieste draudžiama, – vadinasi, galimų maršrutų skaičius ribotas ir tereikia juos visus patikrinti! Šioje vietoje visgi sustokime ir paskaičiuokime…

Kadangi paskutinis maršruto miestas sutampa su pirmuoju, kiekvienam iš 33 miestų priskyrę po raidę, visą galimą maršrutą, kokia tvarka reikia aplankyti miestus, galime patogiai užrašyti tokia simbolių eilute:

A Ā B C Č D E Ē F G Ģ
H I Ī J K Ķ L Ļ M N Ņ
O P R S Š T U Ū V Z Ž

Kadangi lietuviškoje abėcėlėje tėra 32 raidės, teko panaudoti latvišką, kurioje 33 simboliai.

Keisdami šios sekos raides vietomis, gausime visus įmanomus maršrutus. Kadangi maršrutas cikliškas, jo pradžios taškas nesvarbus. Taigi, viso bus 32!=32×31×30×…×2×1 galimų kombinacijų. Pusė iš jų atitiks maršrutus, einančius priešinga kryptimi. Taigi, reikės patikrinti dvigubai mažiau – 32!/2, t. y. 131565418466846765083609006080000000, t. y. 131 tūkstantį kvintilijonų (10³⁰), kombinacijų.

Kiek truktų visų šių kombinacijų perrinkimas kompiuteriu? Šiuo metu galingiausias pasaulyje superkompiuteris „Sunway TaihuLight“ gali atlikti maždaug 93 014 milijardų (10¹²) aritmetinių veiksmų per sekundę. Jeigu tartume, kad vieno maršruto ilgio suskaičiavimas tėra vienas aritmetinis veiksmas (nors akivaizdu, kad tai netiesa), superkompiuteris per 33 miestus keliaujančio pirklio uždavinį išspręstų po 44 milijardų metų. Galingiausias Lietuvos superkompiuteris užtruktų beveik 4000 kartų ilgiau.

Turint omeny, kad Visatos amžius yra 13,8 milijardo metų, tokį sprendimo būdą drąsiai galima laikyti nepriimtinu.

Dinaminio programavimo algoritmu uždavinį pavyktų išspręsti žymiai greičiau. Jeigu perrinkimo metodo sprendimo trukmės priklausomybę nuo miestų skaičiaus n apibrėžia funkcija (n-1)!/2, tai dinaminio programavimo algoritmo – 2ⁿn². Taigi, 33 miestų uždavinį galingiausias Lietuvos superkompiuteris išspręstų greičiau nei per sekundę.

Dinaminio programavimo metodas paremtas logika, kad paprastesnio uždavinio sprendinį galime panaudoti didesnio uždavinio sprendimui. Keliaujančio pirklio uždavinio atveju iš pradžių reikėtų rasti visus galimus optimalius maršrutus, sudarytus iš 4 miestų bei, prieš grįžtant į pradinį tašką, užsibaigiančius tam tikrame mieste. Prie uždavinio sąlygos pridėjus penktąjį, šeštąjį ir kitus miestus, tereiktų pasinaudoti prieš tai gautais optimalių trumpesnių maršrutų rinkiniais.

Visgi ir dinaminio programavimo metodu uždavinys sprendžiamas nepriimtinai ilgai. Bėda, kad jo vykdymo trukmė priklauso nuo daugiklio 2ⁿ, kuris lemia, kad didinant miestų skaičių vis tiek greitai turėsime situaciją, kada sprendinio teks ieškoti milijardus metų (tai atsitiks kai miestų skaičius > 100).

Visgi pilno perrinkimo ir dinaminio programavimo algoritmai yra vieninteliai žinomi deterministiniai (kuriuos atlikus, visuomet gaunamas teisingas atsakymas) keliaujančio pirklio uždavinio sprendimo algoritmai.

Padėtis be išeities?

Euristiniai sprendimo būdai

Keliaujančio pirklio uždavinį galima spręsti euristiniais metodais. Jie spartūs, tačiau remdamiesi vien jais, nežinosime, ar gautas rezultatas optimalus. T. y., sprendinys bus apytikslis.

Aptarkime genetinį ir atkaitinimo modeliavimo algoritmus keliaujančio pirklio uždaviniui spręsti.

Genetiniame algoritme raidėmis užrašytas pirklio maršrutas laikomas tarsi genų seka, kuri gali atsitiktinai mutuoti (maršrute du gretimi miestai apsikeisti vietomis, vienas miestas sekoje atsitiktinai peršokti į kitą vietą ir t. t.). Kompiuteriu generuodami daugybę tokių sekų ir atlikdami mutacijas, galime imituoti natūralią atranką panaikindami kai kurias sekas. Šiuo atveju silpniausi nariai yra ilgiausi maršrutai ir jie, žinoma, turi didesnę tikimybę žūti.

Optimizavimo uždaviniuose dažnai susiduriama su situacija, kai nepaisant nieko, tarpinio gauto maršruto sprendinys tik blogėja (maršrutas ilgėja). Todėl gali klaidingai atrodyti, kad tas maršrutas ir yra optimalus. Kitaip tariant, sprendinys atsiduria lokaliame minimume, nors pagrindinis sprendimo tikslas – rasti globalaus minimumo (pačio trumpiausio maršruto) parametrus.

Genetinio algoritmo privalumas – atsidūrus lokaliame minimume, visuomet egzistuoja tikimybė dėl atsitiktinių mutacijų „peršokti“ į kitą maršrutą, artimesnį globaliam minimumui.

Panašiai kaip genetinis algoritmas buvo sukurtas pagal biologinius evoliucijos principus, taip ir kitas algoritmas – atkaitinimo modeliavimas – remiasi fizikos analogija, metalų grūdinimu.

Norint pagerinti metalo plastiškumą, jis įkaitinamas ir paskui pamažu atvėsinamas. Aukštoje temperatūroje metalo atomai lengviau juda kristalinėje gardelėje bei išsklaido gardelės deformacijas. Metalui vėstant, toks judėjimas vis labiau suvaržomas, galiausiai nusistovi pusiausvyra – optimali kristalo gardelės struktūra.

Optimizavimo uždaviniuose tokia padėtis atitinka siekiamąjį globalųjį minimumą, o „temperatūra“ – uždavino parametrų kintamumą. Taigi, atkaitinimo modeliavimo algoritmo pradžioje, panašiai kaip genetiniame algoritme, maršrutui leidžiama neribotai atsitiktinai kisti. Vėliau įvairių mutacijų tikimybės perskaičiuojamos pagal aplinkos „temperatūrą“ – kuo temperatūra mažesnė, tuo bet kuri maršrutą pailginanti mutacija mažiau priimtina. Galiausiai, pasiekus nulinę temperatūrą, bet koks maršruto nesutrumpinantis sprendinio pakitimas atmetamas, o geriausias sprendinys įsimenamas.

Atkaitinimo modeliavimo algoritmas keliaujančio pirklio uždaviniui dažnai leidžia neužstrigti lokaliame minimume. Kita vertus, kaip ir metalurgijoje, itin išauga temperatūros mažinimo scenarijaus svarba.

Jei temperatūra keičiama lėtai, sprendimas užtrunka, o jei greitai – didėja tikimybė gauti lokalaus minimumo sprendinį. Dažniausiai atkaitinimo modeliavimo algoritmuose pasirenkama tokia temperatūros kitimo funkcija, kurios kitimo greitis pradžioje didesnis nei pabaigoje. Tai gali būti, pavyzdžiui, eksponentiškai mažėjanti funkcija.

Nors euristiniai algoritmai pagal apibrėžimą duoda tik apytikslį sprendinį, visgi, kai kada keliaujančio pirklio uždavinį galima išspręsti visiškai tiksliai. Matematiškai galima suskaičiuoti, koks bus paties trumpiausio maršruto ilgis, tačiau pats maršrutas lieka nežinomas. Taigi, sprendžiant keliaujančio pirklio uždavinį bet kokiu metodu ir gavus būtent tokio ilgio maršrutą, iškart turėtumėme įrodymą, kad gautasis maršrutas – pats trumpiausias.

Svarbiausias informatikos uždavinys

Ir visgi, kodėl keliaujančio pirklio uždavinys yra vienas intensyviausiai nagrinėtų skaičiuojamosios matematikos uždavinių? Negi tai toks įdomus žaidimas mokslininkams, kad juo būtų užsiimama jau daugiau nei 50 metų? Tiesa ta, kad keliaujančio pirklio uždavinys – esminė paties svarbiausio šių laikų informatikos mokslo uždavinio dalis.

Pradėkime nuo to, kad algoritmas laikomas „geru“, jei jo vykdymo trukmė nuo duomenų kiekio (mūsų atveju nuo miestų skaičiaus n) priklauso kaip daugianaris (polinomas). Tokia uždavinių klasė vadinama P. Pavyzdžiui, skaičių rikiavimo uždavinys yra P (polynomial) tipo, nes tai atliekančio pačio paprasčiausio algoritmo vykdymo trukmė nuo skaičių kiekio priklausys kaip n².

Nors P tipo uždavinio apibrėžimas aiškus, pasakyti, ar duotas uždavinys yra būtent toks – sudėtinga. Visai gali būti, kad keliaujančio pirklio uždavinys irgi yra P tipo, tačiau toks algoritmas dar nerastas. Kita vertus, bet kokio sprendinio „gerumą“ galima patikrinti per P laiką. Tai yra, jei mums į rankas papultų miestų eiliškumas, mes labai greitai rastume maršruto ilgį. Ši savybė leidžia keliaujančio pirklio uždavinį priskirti NP (nondeterministic polynomial) klasei. Tai yra sudėtingai sprendžiami uždaviniai, kurių sprendinius lengva patikrinti.

Ar gali būti, kad P ir NP tipo uždaviniai iš tiesų yra to paties tipo? Gali. Negana to, matematikai Stephen Cook ir Leonid Levin 1971 m. parodė, kad jei būtų rastas „geras“ algoritmas bent vienam NP tipo uždaviniui, būtų galima rasti „gerus“ algoritmus visiems NP tipo uždaviniams. Taigi, būtų parodyta, kad P=NP.

Žmogus, išsprendęs šį uždavinį, kaip ir „Car 54“ konkurso nugalėtojas, galės pasistatyti namą JAV: Clay Matematikos Institutas yra paskyręs 1 milijono dolerių prizą sprendimo autoriui.

Galima pagalvoti, kad visa tai – tik mokslininkų reikalas, tačiau jei būtų įrodyta, kad P=NP, pasekmės būtų katastrofiškos. Pavyzdžiui, dabartinės duomenų apsaugos sistemos remiasi tuo, kad užkoduotų duomenų iššifravimas yra NP sunkumo uždavinys, kuriam išspręsti reikia begalės laiko. Taigi laikoma, kad tos sistemos saugios.

Vulgari išvada būtų tokia: jei pavyktų rasti metodą, kaip NP tipo keliaujančio pirklio uždavinį paversti P tipo uždaviniu, visos internetinės prekybos sistemos gabių hakerių būtų labai greit nulaužtos. Ir nors galima susitelkti ties šia negatyvia prognoze, teigiamas atsakymas į „N=NP?“ uždavinį būtų milžiniškas proveržis optimizavimo uždavinių sprendimui visose srityse: moksle, ekonomikoje ar inžinerijoje…

Taigi, keliaujančio pirklio uždavinys yra lengvas, sunkus ar neišsprendžiamas? Teisingas atsakymas – „niekas nežino“. Būtent dėl tokio neaiškumo šis uždavinys yra toks patrauklus. O atsakymo kaina yra daug didesnė nei pirklio kelionės išlaidos: tai yra daugiausiai dėmesio sulaukiantis uždavinys didelėje diskusijoje apie uždavinių sudėtingumą bei žmogaus pažinimo ribas.

Na, o nuožmus prekybos agentas, siūlantis stebuklingus siurblius ar visas ligas gydančio vandens filtrus ir norintis apkeliauti 33 didžiausius Lietuvos miestus, turės įveikti mažiausiai 1350 kilometrus.

Dr. Vytautas Butkus

[1] http://www.math.uwaterloo.ca/tsp/sweden/index.html

[2] https://www.top500.org/system/178764

[3] http://www.supercomputing.vu.lt/

[4] http://www.claymath.org/millennium-problems/p-vs-np-problem