Matematikai surado trumpiausią kelią aplankyti 2 milijonus žvaigždžių

vel prasideda matematinis briedas tas uzdavinys turi but sprendziamas palaipsnines optimizacijos metodu, o ne buhalteriskai. optimizacija turi but tokio lygmens, kokiu lygmeniu sudetingeja uzdavinys. jei eksponentiskai sudetingeja - nu tai ir algoritmo optimizacija turi but eksponentinio principo. o dabar didziuojasi, kad idiotisku budu issprende ir gavo apytiksli rezultata cia ziuriu paskutine matematikos vyraujanti tendencija. susikurt problema ir ja biski apsprest. o tada girtis. didziuotis galima tik kai gavai tikslu rezultata. aplamai - irodinet net nebutina, kad tai geriausias sprendimas - jei ji tiesiog suskaiciuoji ir sunkiuoju budu, ir jis sutampa. tos zvaigzdes aplamai juda erdveje nerealiais greiciais ir sitas skaiciavimas kuri cia atliko visiskai beprasmis. turi but skaiciuojamas ne statinis, o dinaminis modelis. ir isduot tikslia padeti reikiamu metu. keliaujancio pirklio uzdavinys turi ir laiko dedadamaja - zemes pavirsiuje atstumai nekinta. taip kad cia isvis net ir akivaizdziai meluoja su tom zvaigzdem... plius kur nuorodos i uzdavinio aprasyma ir premijas - duoda jie cia atseit matai pinigu uz rezultata kuris geresnis, bet patikrint negales. visiski glusai...

As manau, kad geriau tegu zmones lauzo galvas, negu eina gauti pasalpas is darbo birzos. Nors darbas ir niekinis, bet zmones vistiek sviesesne galva turi ant peciu...

Įdomu tai, kad šis "keliaujančio prekeivio" uždavinys išspręstas 3D erdvėje. Iki šiol teko skaityti tik apie 2D tokio tipo uždavinius. Lieka tikėtis, kad ateityje bus išvystyti algoritmai kaip spręsti tokius uždavinius aukštesnėse dimensijose. Įdomu, ar mokslininkai atsižvelgė į tai, kad žvaigždės galaktikoje juda? Spėju kad ne. Būtų nepalyginamai sunkiau suskaičiuoti trumpiausią atstumą, kai atstumai tarp 2mln. žvaigždžių nuolat kinta.

jokio skirtumo 2d ar 3d. Turi atstumus tarp žvaigždių ir tiek. 2d atveju netgi sudėtingiau (teoriškai), nes keliai tarp miestų nėra tiesės. AAA išsakyta įdėja man patiko. Gal net reikėtų pasiūlyti kokiai informatikos olimpiadai?

1d atveju viskas paprasta ir aišku. Į tolimesnį miestą neįmanoma patekti neaplankius artimesnio miesto. Ir miesto negalima aplankyti du kartus, tad pradėti kelionę reikia pirmame arba paskutiniame mieste. 2d atvejis - jau nepalyginamai sudėtingesnis. Šviesiausi planetos protai dar nerado elegantiško problemos sprendimo būdo. Tiesiog naudojama "brutali jėga" - atlieki trilijonus skaičiavimų ir išsirenki mažiausią kelią. 3d ir aukštesnės dimensijos - nuojauta kužda, kad problema dar kartą nepalyginamai pasunkėja. Turbūt bus kaip ir NP tipo uždaviniuose - didinant duomenų kiekį skaičiavimų sudėtingumas didėja eksponentiškai. ---- Nebuvau susimąstęs apie keliaujančio prekeivio problemą kreivuose 2d paviršiuose, kaip pvz sfera, toras, Kleino butelys, hiperboloidas ir kt. 3d erdvė taip pat turi šiuos atitikmenis.

Dar pridursiu kaip minėjo AAA000 3D erdvė ir dar judantys taškai tai jau 4D, o tai dar eksponentiškai padidėja nei tieiosg 3D. Dar ir orbitas paskaičiuoti reikia kiekvieno taško iš milijardo. Manau 100% tikslumu brute force būdu išsprestu kvantinis kompiuteris su milijardu kubitų (tiek kiek yra žvagždžių žvaigždėlapyje), per milisedundes, su mažiau kubitų turbut neišsprestu per protingą laiką. Na dar sukūrus neuroninį tinklą su milijardais įvesčių/išvesčių ir paslėptų sluoksnių (palei žvaigždžių kiekį) ne kvantiniam superkompiuteryje irgi išsprestu per protingą laiką brute force būdu. Aišku galima algoritmą optimizuoti ir iškarto atmesti 99,999% klystkelius, bet optimizacija kartais gali praleisti ką nors netikėto ir reikšmingo.

Tokios problemos nėra. Tai grafu objektas, kur kiekvienas nodas sujungtas su visais likusiais. inicializavimas grafu net su milijonu nodu milisekundžiu reikalas. Atstumu dinamika dėl žvaigždžiu judėjimo įneštu papildomą sudėtingumą, bet irgi nėra reikšminga problema palyginus su bendru traveling salesmen fonu. Kvantinis kompiuteris su reikiamu kubitu kiekiu, tokias problemas gali gliaudyti akimirksniu. Klasikiniame kompe problemos sprendimo laikas auga eksponentiškai, augant nodu kiekiui (np-complexity).

yra tie sprendimai. butent sitam uzdaviniui. tiesiog matematikai issikelia kokia nors durna salyga, kad "reikia irodyt" kad sprendimas geriausias ir vienintelis imanomas. bet ta salyga tokio tipo uzdaviniuose neispildoma, nes yra ne vienas vienodas variantas idealaus sprendimo. pvz paimk koki nors lygiakrasti kvadrata. arba romba. su ABCD virsunem. ir tasku E - esanciu centre. ir gali keliaut kvadrato ratu ir is bet kurio krasto padaryt kelione i centra E. ir visi variantai bus trumpiausi ir identiski. bet ju bus keli. o ne vienas geriausias. lygiai taspats nutinka ir su daug tasku. taip kad kvaila sprest tokio tipo uzdavinius irodinejimo budu - kai neimanoma apipavidalint per atsilikusias matematines taisykles. cia yra pacios matematikos problema. o ne uzdavinio neissprendimo. sita uzdavini issprest imanoma net 100% tikslumu - bet tie budai tera optimizacinio varianto, kai darai praktini sistemos subalansavima. kai sistema nusistovi i ramybes busena - tai ir yra geriausias variantas. arba uzdavinio geriausias sprendinys. nes subalansavimo principui nesvarbu lygiaverciai sprendiniai. sitas subalansavimo principas paima pati pirma geriausia atsitiktini varianta. jam nesvarbu - ju daug ar tik vienintelis. jis bus rastas. o dabartines matematikos taisyklemis to tiesiog neimanima irodyt taip kad tos premijos feikines problemos yra matematikos ribotume. o viena didziausia is ju, kad matematika naudoja nuli (atskaitos taska)...