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

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.