Иллюстрация Патрика Андерсона, на которой он в 2012 году предположил самый длинный возможный прямой маршрут по морю
В декабре 2012 года в подреддите /r/MapPorn разгорелась любопытная дискуссия. Один из пользователей под ником Kepleronlyknows (Патрик Андерсон) опубликовал изображение с картой мира, на котором изобразил прямой судоходный маршрут. Патрик высказал гипотезу, что это самый длинный прямой маршрут, который можно проложить по воде на нашей планете. Без единого поворота и смены курса вы проплывёте по прямой около 32 000 километров, стартовав в районе Пакистана и финишировав на Камчатке. Абсолютно прямой маршрут проходит мимо Африки, Южной Америки и через Тихий океан до самой России.
Конечно же, автор произвёл расчёт по интуиции. Он предложил форумчанам проверить его гипотезу и найти более длинный маршрут, если таковой существует. Или попробовать доказать, что именно этот маршрут — самый прямой.
Сообщение вызвало бурные дебаты: сотни форумчан склонились над картами и глобусами. Главный вопрос — можно ли побить этот рекорд? Попутно возник ещё один вопрос: а какой самый длинный в мире маршрут по прямой по суше, а не по морю? То есть сколько можно идти по прямой, ни разу не наткнувшись на море.
Понятно, что результирующая кривая должна принадлежать большой окружности вокруг сферы земного шара (для простоты можно считать его сферой). Эта окружность соединяет точки на поверхности сферы по кратчайшему возможному пути. Но как найти эти окружности с верным решением?
Окружность, которая соединяет самую высокую и самую низкую точки на поверхности Земли
Судя по всему, среди «горячих голов» на форуме Reddit нашлись-таки люди с фундаментальным образованием, которые основательно подошли к решению проблемы. Итак, ознакомьтесь с научной работой Рохана Чабуксвара (Rohan Chabukswar) из исследовательского центра United Technologies (Ирландия) и Кушала Мукерджи (Kushal Mukherjee) из научно-исследовательского подразделения IBM Research в Индии. Эти ребята разработали надёжный алгоритм для расчёта самого длинного прямолинейного пути на суше или на море. Научная статья опубликована 9 апреля 2018 года на сайте препринтов arXiv.og (arXiv:1804.07389v1).
Конечно, сразу приходит в голову решить задачу брутфорсом — перебрать все возможные окружности вдоль земной сферы. Но это слишком ресурсоёмкая задача: на карте мира с разрешением 1,85 км получится более 230 миллиардов таких окружностей. Каждая из них состоит из 21 600 отдельных пунктов, что составляет в общей сложности более пяти триллионов точек для расчёта.
Но Чабуксвар и Мукерджи разработали более быстрый метод на основе алгоритма, известного как метод ветвей и границ (branch and bound).
Метод ветвей и границ — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений. Фактически, вместо оценки всех решений алгоритм проверяет одну ветвь за другой (аналог брутфорса). Но другой метод, называемый ограничением, значительно уменьшает область перебора. Каждая ветвь содержит подмножество потенциальных решений, одним из которых является оптимальное решение. Хитрость в том, чтобы найти свойство подмножеств, которое зависит от того, насколько близко решения подходят к оптимальному.
Такой вариант вычислений потребовал гораздо меньше вычислительных ресурсов: «Алгоритм вернул самый длинный путь примерно за 10 минут вычислений для водного пути и 45 минут вычислений для земного пути на стандартном ноутбуке», — говорят исследователи.
И оказалось, что Kepleronlyknows был совершенно прав. Самый длинный прямой водный путь начинается в городе Сонмиани, провинция Белуджистан, Пакистан, где находится ракетно-испытательный полигон. Маршрут проходит между Африкой и Мадагаскаром, а затем между Антарктидой и Новой Зеландией в Южной Америке — и заканчивается в Карагинском районе Камчатского края в России. Длина маршрута 32089 километров 700 метров.
Самый длинный путь по суше начинается близ городского уезда Цзиньцзян в провинции Фуцзянь, округ Цюаньчжоу (Китай). Он идёт через Монголию Казахстан, Россию и, наконец, достигает Европы, чтобы завершиться около города Сагреш в Португалии. В целом маршрут проходит через 15 стран и составляет 11241 километр 100 метров — более 101 градуса по земной окружности.
Через какие страны проходит самый длинный в мире прямой сухопутный маршрут:
- Китай (Цзиньцзян, 24°32’55» N, 118°38’3» E)
- Монголия
- Казахстан
- Россия
- Беларусь
- Украина
- Польша
- Чехия
- Германия
- Австрия
- Лихтенштейн
- Швейцария
- Франция
- Испания
- Португалия (Сагреш, 37°1’30» N, 8°55’0» W)
Если вам интересно, можете посчитать, через какие конкретно города проходит рекордный в мире маршрут. Вдруг какой-нибудь сумасшедший путешественник решит пройти строго по прямой через всю Азию и Европу. Хотя, наверное, вопрос нужно ставить по-другому: кто это сделает первым и когда?
Источник
