Tarp miestų keliaujančio prekeivio problema sena, tačiau ir keliaujant tarp žvaigždžių, komivojažerio įgūdžiai praverstų.

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. William Cook iš Waterloo universiteto Kanadoje ir Keld Helsgaun iš Roskilde universiteto Danijoje išsprendė jį kol kas didžiausiu masteliu.

Jie išanalizavo Galia 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.

„Tai būtų greičiausias būdas aplankyti visas išmatuotas mūsų galaktikos žvaigždes, tereikėtų erdvę iškreipiančio variklio,” sako Cookas. Netgi šviesos greičiu tokia kelionė truktų beveik 100 milijonų metų.

Keliaujančio prekeivio problema nėra grynai akademinis pratimas. Cooko ir Helsgauno panaudoti metodai gali būti pritaikyti ir kitokiems duomenims, pavyzdžiui, skrydžių maršrutams ir genomoo išdėstymui. „Kuo didesnę problemą gali išspręsti, tuo labiau gali priartėti prie tikrovės, prie tikro pasaulio modeliavimo,” sako Cookas. Gaia jau paskelbė duomenis apie daugiau nei milijardą žvaigždžių, ir tyrėjai stengiasi surastui trumpiausią kelią tarp jų.

Šios problemos skaičiavimui per porą metų panaudota maždaug 200 metų kompiuterio skaičiavimo laiko, pažymi 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,” paaiškina Cookas. „Turint pakankamai gerą mašiną, kvantinis kompiuteris iš principo galėtų pirmąją dalį atlikti labai gerai.“

Tačiau kol kas kvantiniai kompiuteriai tokių didelių problemų nepajėgia, tad Cookas siūlo piniginį atlygį bet kam kas galėtų pagerinti jo sudarytą maršrutą tarp žvaigždžių.

Leah Crane
www.newscientist.com

Komentarai (8)