Radome geriausią kelią tarp žvaigždžių. Keliaujančio prekeivio problema, garsioji matematinė mįslė, kur ieškoma trumpiausio kelio tarp daugelio vietovių, kiekvieną iš jų aplankant tik kartą ir sugrįžtant į pradžią, buvo išspręstas kol kas didžiausiu – galaktikos – masteliu.
Keliaujančio prekeivio problema regis paprasta, tačiau pagarsėjusi sprendimo sudėtingumu. Konkrečių duomenų aibes galima išspręsti, tačiau bendras algoritmas, pagal kurį būtų galima išspręsti bet kurį problemos atvejį, dar nerastas. Williamas Cookas iš Vaterlo universiteto (Kanada) ir Keldas Helsgaunas iš Roskildės universiteto (Danija) išsprendė jį kol kas didžiausiu masteliu.
Jie išanalizavo „Gaia“ kosminio teleskopo duomenis, kurių pirmajame rinkinyje yra išmatuota 2 079 471 mūsų galaktikos žvaigždės vieta. Efektyviausias visų jų aplankymo maršrutas yra 94 208 157,5 šviesmečių ilgio. Jei egzistuoja trumpesnis maršrutas, remiantis jų skaičiavimu, jis negali būti trumpesnis daugiau nei 0,0000074 karto – maždaug 700 šviesmečių. Tada jie nubraižė šį kelią tarp žvaigždžių 3D žemėlapyje.
„Tai būtų greičiausias būdas aplankyti visas išmatuotas mūsų galaktikos žvaigždes, tereikėtų erdvę iškreipiančio variklio“, – sako W.Cookas. Netgi šviesos greičiu tokia kelionė truktų beveik 100 milijonų metų.
Keliaujančio prekeivio problema nėra grynai akademinis pratimas. W.Cooko ir K.Helsgauno panaudoti metodai gali būti pritaikyti ir kitokiems duomenims, pavyzdžiui, skrydžių maršrutams ir genomo išdėstymui. „Kuo didesnę užduotį gali išspręsti, tuo labiau gali priartėti prie tikrovės, prie tikro pasaulio modeliavimo“, – sako W.Cookas. „Gaia“ jau paskelbė duomenis apie daugiau nei milijardą žvaigždžių ir tyrėjai stengiasi surasti trumpiausią kelią tarp jų.
Šios užduoties skaičiavimui per porą metų panaudota maždaug 200 metų kompiuterio skaičiavimo laiko, pažymi W.Cookas. Ateityje šį optimizavimo procesą galėtų paspartinti kvantiniai kompiuteriai. „Yra dvi dalys: reikia rasti gerą sprendimą ir tada įrodyti, kad niekas negalėtų padaryti geriau. Turint pakankamai gerą mašiną, kvantinis kompiuteris iš principo galėtų pirmąją dalį atlikti labai gerai“, – paaiškina W.Cookas.
Tačiau kol kas kvantiniai kompiuteriai tokių didelių užduočių nepajėgia įveikti, tad W.Cookas siūlo piniginį atlygį bet kam, kas galėtų pagerinti jo sudarytą maršrutą tarp žvaigždžių.
