В 2012 году пользователь Reddit Патрик Андерсон опубликовал карту, на которой была показана самая длинная прямая, по которой можно проследовать по океану, не встречаясь с сушей. Он не предоставил никаких доказательств тому, что его данные верны, и пара исследователей решили разработать алгоритм, который нашел бы самую длинную прямую не только на воде, но и на суше.

Рохан Чабуксвар из Исследовательского центра United Technologies Ireland и Кушал Мукерджи из IBM Research India создали алгоритм, который должен был подтвердить, что маршрут от Пакистана до Сибири действительно является самой длинной прямой, по которой может проследовать мореплаватель. На двухмерной карте маршрут не выглядит как прямая, но не забывайте, что Земля – это сфера.

Рассчитать этот маршрут оказалось не самой простой задачей. Исследователи приобрели карту с достаточно высоким разрешением NOAA. Им предстояло проверить 5 038 848 000 000 возможных точек. Это 5 триллионов 38 миллиардов 848 миллионов точек. У Чабуксвара и Мукерджи не было достаточной вычислительной мощности для расчетов, и по этой причине ученые использовали ветвящиеся алгоритмы для решения задач оптимизации. Такой подход сокращает время решения задачи, разбивая ее на более мелкие детали и подмножества.

С помощью этой удивительной техники ученые произвели расчеты на обычном персональном компьютере за 10 минут. Удивительно, но результат оказался таким же, что был опубликован пользователем Reddit в 2012 году. Протяженность этого маршрута составляет 32 089,7 километра.

Таким же образом Чабуксвар и Мукерджи решили найти самую длинную прямую, по которой можно проследовать на суше, не сталкиваясь с крупными водоемами. Протяженность прямой составила 11 241 километр. Эта прямая проходит от Китая через Монголию, Казахстан, Россию, Польшу, Чехию, Германию, Австрию, Лихтенштейн, Швейцарию, Францию, Испанию и заканчивается в Португалии.

Стоит отметить, что маршрут от Китая до Португалии может быть не самым оптимальным, так как подсчеты не учитывают горы и реки. То же самое можно сказать и о маршруте через океан.

Источник