Програмісти знайшли найдовші прямі маршрути на суші і воді

Найдовший шлях по воді без виходу на сушу становить понад 30 тисяч кілометрів, з'ясували програмісти, використавши алгоритм оптимізації для розрахунку найдовших прямих маршрутів по суші і по воді. Препринт статті опубліковано на сайті arXiv, коротко про історію пошуку маршруту повідомляє MIT Technology Review.

Наприкінці грудня 2012 року один із користувачів спільноти Reddit r/MapPorn запропонував найдовший прямий маршрут водою без виходу на сушу: він займав приблизно 20 тисяч миль (близько 32 тисяч кілометрів) і проходив від узбережжя Аравійського моря в Пакистані до півострова Камчатка. Намальована карта викликала безліч обговорень: як правильності запропонованого маршруту, так і розрахунку прямого шляху сушею.

Вирішення подібного завдання вручну - це досить трудомісткий процес, що вимагає карт дуже великого дозволу: на них, з одного боку, повинні бути зображені всі озера на суші, а з іншого - всі острови в океанах. Автоматичний перебір всіх можливих маршрутів з прямих ліній, які зазвичай можна побачити на глобусах, також займає багато часу, так як і він вимагає використання моделей Землі з дуже великою роздільною здатністю. Наприклад, карта, створена Національним управлінням океанічних і атмосферних досліджень, має дозвіл в одну кутову хвилину, що приблизно дорівнює 1,86 кілометра на рівні моря: на глобусі з такою роздільною здатністю понад 200 мільйонів великих кіл, на кожному з яких - близько 20 тисяч окремих точок. Обробка всіх цих точок хоч і дозволить достовірно розрахувати прямі маршрути по воді і суші, але займе дуже багато часу навіть з використанням порівняно потужного комп'ютера.

Роуен Чабуксвар (Rohan Chabukswar) з ірландського дослідницького центру United Technologies і Кушал Мухержі (Kushal Mukherjee) з індійського підрозділу IBM припустили, що побудова подібних маршрутів - це класичне завдання оптимізації: навіть при використанні звичайного перебору завдання буде полягати в тому, щоб відсівати невідповідні варіанти (у випадку з пошуком маршруту по воді - це ті шляхи, які проходять через сушу) і порівнювати один з одним відповідні по довжині. Оскільки простий перебір - це неоптимальний варіант розрахунку подібних маршрутів, вчені запропонували використовувати метод гілок і меж. По суті такий метод - це такий же алгоритм перебору: в його основі лежить розбиття всієї безлічі можливих варіантів на підмножини менших розмірів, яке в результаті утворює дерево пошуку. На такому дереві діє правило відсіву. Верхня межа (найбільше значення) підмножини порівнюється з верхньою межею підмножини, що передує йому: якщо вона менша, то ця підмножина відкидається за відсутністю відповідних варіантів, якщо ж більше - то вона стає «рекордом» (найбільшим значенням), і межі наступних безліч порівнюються вже з нею.

Використання подібного алгоритму оптимізації дозволило дослідникам автоматично розрахувати найдовші прямі маршрути сушею і водою за 10 і 45 хвилин відповідно: так, по воді цей шлях дійсно лежить з Пакистану в Камчатку і займає 32089 кілометрів, а по суші - від узбережжя Східно-Китайського моря до Португалії (приблизно 11241 кілометр).

Таким чином, вчені підтвердили, що маршрут, запропонований користувачем Reddit в 2012 році - найдовший. Наприкінці своєї статті автори також зазначають, що їхня робота - це тільки вирішення математичного завдання, а не рекомендація щодо вибору маршруту для подорожі.

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