Jau 50 metų neįveikiamas keliaujančio pirklio uždavinys: išspręsite - milijoninės premijos garantuotos

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