Астрономія
Технології
Астрономія
Технології

Математики вирахували найвигідніший маршрут до 2 мільйонів зірок

math.uwaterloo.ca

math.uwaterloo.ca

Вчені розв’язали так звану задачу комівояжера для 2 мільйонів зірок у нашій галактиці за допомогою даних телескопа Gaia. Найвигідніший маршрут до них складає 94208157,5 світлових років. Побачити візуалізацію маршруту можна тут.

Що таке задача комівояжера?

Задача комівояжера — це відома проблема у математиці, яка полягає у пошуку найкоротшого маршруту з багатьма пунктами призначення, побудованого так, щоб відвідати кожну точку лише один раз. Завдання залишається трудомістким, потребує використання великих обчислювальних потужностей і досі не має ефективного загального рішення. Воно поєднує теорію графів з комбінаторикою та оптимізацією.

Як вчені розв’язали цю задачу для зірок?

Математики проаналізували дані космічного телескопа Gaia, який виміряв розташування 2079471 зірок у нашій галактиці під час свого першого випуску даних. З жовтня 2017 року по жовтень 2019 року вони будували різні тривимірні маршрути до цих зірок. Основою для дослідження стало програмне забезпечення LKH — генератор майже оптимальних рішень для задачі комівояжера та пов'язаних з нею проблем маршрутизації. Вчені застосували для нього методи, спеціалізовані для великого набору даних, що поєднують локальний пошук та генетичні алгоритми, а також стратегії декомпозиції для паралельного обчислення. Пошуки тривали до кінця 2019 року, але вчені не знайшли подальших покращень рішення з жовтня 2019 року.

Найефективніший маршрут до кожної з цих зірок становить близько 94208157,5 світлових років, або 28884352,4 парсеків. Якщо й існує більш оптимальний маршрут, він буде меншим у 0,0000074 рази, тобто приблизно на 700 світлових років. Щоб здійснити цю подорож, світлу знадобилося б близько 100 мільйонів років. На основі свого рішення вчені створили тривимірну модель.

Запропонований метод може застосовуватися для інших типів даних, таких як планування польотів та мапування геному. Дослідники сподіваються, що у майбутньому квантові комп’ютери можуть прискорити процес оптимізації подібних рішень.

графів
Об’єктів та зв’язків між ними