Tai, ką surado Japonijos mokslininkai, gali sukelti tikrą revoliuciją kompiuterijoje: vienaląstė ameba rado keliaujančio pirklio problemos sprendimą greičiau, nei tą padaro geriausi mūsų turimi algoritmai (Video) ()
Viena maža ameba rado keliaujančio pirklio problemos sprendimą greičiau, nei įmanoma geriausiais mūsų turimais algoritmais. Ką žino ji, ko nežinome mes?
|
Visi šio ciklo įrašai |
|
Prisijunk prie technologijos.lt komandos!
Laisvas grafikas, uždarbis, daug įdomių veiklų. Patirtis nebūtina, reikia tik entuziazmo.
Sudomino? Užpildyk šią anketą!
Grupė tyrėjų iš Keio universiteto Tokijuje garsiosios kompiuterių mokslo problemos, keliaujančio pirklio problemos sprendimui pasitelkė amebą. Problemos esmė tokia: įsivaizduokite, esate keliaujantis prekeivis, skraidantis iš miesto į miestą ir pardavinėjantis prekes. Jums rūpi dirbti kuo efektyviau, užsidirbti kuo daugiau, tad norite rasti trumpiausią kelią, kuriuo keliaudami, pasiektumėte kiekvieną miestą.
Paprastos matematinės formulės, pagal kurią mūsų pirklys galėtų rasti efektyviausią maršrutą, nėra. Vienintelis problemos sprendimo būdas – suskaičiuoti ir palyginti visų įmanomų kelių ilgius.
\(Physarum polycephalum\) yra labai paprastas organizmas, atliekantis du dalykus: juda link maisto ir juda nuo šviesos.
Negana to, daugėjant miestų, kelių skaičiavimas sunkėja eksponentiškai. Jei miestai keturi, tereikia palyginti tris skirtingus kelius. Bet jeigu miestai šeši, reikės apskaičiuoti 360 skirtingų kelių. Jei maršrute dešimt ar daugiau miestų, galimų kelių skaičius pasiekia milijonus – ir tai ne riba.
Todėl keliaujančio prekeivio problema yra viena iš plačios klasės problemų, kuriuos kompiuterijos mokslininkai vadina „NP sudėtingumo“. Tai problemos, kurių sprendimai labai greitai darosi eksponentiškai sudėtingi, jai priklauso ir problemos, susijusios su sistemų šifravimu ir kriptovaliutos kasyba. Nieko keisto, kad daug žmonių suinteresuoti rasti kuo greitesnio šių problemų sprendimo būdus.
Keio universiteto sprendimas skiriasi nuo kitų tyrėjų sukurtų sprendimo algoritmų, nes buvo pasitelkta ameba. Konkrečiai, \(Physarum polycephalum\) gleivūnas. \(Physarum polycephalum\) yra labai paprastas organizmas, atliekantis du dalykus: juda link maisto ir juda nuo šviesos. Per milijonus evoliucijos metų Physarum šias užduotis įgudo atlikti nepaprastai efektyviai.
Keio universiteto tyrėjai šį efektyvumą panaudojo keliaujančio prekeivio problemai spręsti. Jie įdėjo amebą į specialią, kanalėlių pilną kamerą, ir kiekvieno kanalėlio gale tyrėjai padėjo maisto. Ameba instinktyviai tiesė savo čiuptuvus į kanalėlius, siekdama maisto. Tačiau vos tik tai pavyksta, šviesa užgęsta kituose kanalėliuose.
Šiuo atveju kiekvienas kanalėlis žymi hipotetinio prekeivio maršruto miestą, o taip pat miestų aplankymo eiliškumą. Kai ameba siekia į miestą žymintį kanalėlį, ji kartu paveikia tikimybę, kad šviesa užges kanalėliuose, žyminčiuose kitus maršrute esančius miestus. Kuo miestas toliau, tuo tame kanalėlyje šviesa išsijungia dažniau.
Tai gali atrodyti kaip žiedinis keliaujančio prekeivio problemos sprendimas, bet pranašumas tas, kad ameba neskaičiuoja kiekvieno individualaus kelio, kaip tai daro kompiuterio algoritmai. Vietoje to ameba tiesiog pasyviai reaguoja į sąlygas ir išsiaiškina geriausią įmanomą konfigūraciją. O tai reiškia, kad amebai daugiau miestų nereiškia ilgesnio problemos sprendimo.
Taigi, ameba gali išspręsti NP-sudėtingą (NP-hard) problemą greičiau, nei bet kuris mūsų kompiuterinis algoritmas. Kaip tai nutinka? Keio mokslininkai tiksliai atsakyti negali.
„Mechanizmas, kuriuo ameba išlaiko sprendimo artinį, tai yra, trumpo maršruto ilgį, tebelieka nežinomas,“ pranešime spaudai sako tyrimo pagrindinis autorius Masashi Aono.
Bet jeigu tyrėjai išsiaiškins amebos veikimą, jie ne vien palengvins komivojažierių dalią. Tai galėtų paspartinti įvairiausių sudėtingų skaičiavimo problemų sprendimą ir pakeisti požiūrį į saugumą.
Ši maža ameba — ir jos sudėtingų problemų sprendimo būdas — gali visam laikui pakeisti kompiuteriją.
Avery Thompson
www.popularmechanics.com