Программисты нашли самые длинные прямые маршруты на суше и воде

Самый длинный путь по воде без выхода на сушу составляет более 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 году — самый длинный. В конце своей статьи авторы также отмечают, что их работа — это только решение математической задачки, а не рекомендация по выбору маршрута для путешествия. 

Стоит отметить, что чаще картографы строят более полезные оптимальные маршруты. Например, зимой европейские ученые построили карту досягаемости городов: с помощью нее можно рассчитать время, которое понадобится на дорогу из любой точки до ближайшего города.

Елизавета Ивтушок