Как далеко можно идти по прямой, никуда не сворачивая?

Земля пока еще на три четверти покрыта водой и рыбами. Поэтому, откуда бы ты ни вышел, рано или поздно упрешься в океан. Недавно людям стало интересно, каким может быть самый длинный прямой пешеходный маршрут. Вычислить его оказалось крайне сложно!



Большинство наших стереотипов о строении Земли проистекает из того, что мы разучились пользоваться теплыми ламповыми глобусами. Для нас мир — это в первую очередь плоская проекция в виде карты, которая, как ты и сам наверняка знаешь, дает невероятно искаженную картину.




Например, по карте проблематично проложить кратчайший воздушный маршрут, в то время как на глобусе Земли это делается одним движением: берешь нитку, прижимаешь один конец к началу пути, другой — к пункту назначения. Траектория выйдет совсем иной, чем представлялась при взгляде на плоскую карту.

Пора заканчивать предисловие. Началась наша история в 2012 году, когда юзеры «Реддита», объевшись глобусов, стали спорить о том, как можно проложить самый длинный прямолинейный морской путь. Некий Патрик Андерсон уверял, что нашел его. И выглядит прямая так:

Этот путь проходит из Пакистана к Камчатке и покрывает 32 тысячи километров по прямой (точнее, по дуге, огибающей земную поверхность). Маршрут Патрик вычислил чисто интуитивно, поэтому тотчас нашлись желающие оспорить его вывод и найти морской маршрут еще длиннее. Люди долго вертели глобусами, прикладывали рулетки и нитки, в итоге другого решения не нашли.

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

В апреле 2018 года на сайте Корнеллского университета была размещена исследовательская работа от Rohan Chabukswar и Kushal Mukherjee. Эти двое создали алгоритм для поиска самых длинных линейных путей по поверхности Земли.

Перебирать все варианты дуг вдоль поверхности Земли оказалось непосильной задачей даже для современных вычислительных систем: счет вариантов шел на миллиарды. Потому исследователи взяли на вооружение метод ветвей и границ. Если описывать его в двух словах, то это тоже алгоритм перебора вариантов, но в его ходе заранее отсеиваются те группы решений, которые заведомо не подойдут.

Как только задача была составлена с умом, компьютер справился с ней играючи: за 10 минут ноутбук вычислил морской путь и за 45 минут — сухопутный.

Математики доказали, что Патрик Андерсон был прав, интуиция его не подвела. Самый длинный морской путь без поворотов начинается в пакистанском городе Сонмиани, а заканчивается на Камчатке, в Карагинском районе. Условное судно преодолеет 32 089 километров 700 метров.

Что касается сухопутного маршрута, то интуитивно можно было бы предположить, что он окажется где-то в Евразии. Так и есть. Стартует он в китайской провинции Фуцзянь и в результате упирается в португальский город Сагреш. Протяженность — 11 241 километр 100 метров. Интересно, что этот путь пересекает аж 15 стран, включая Россию.

Остается только купить велосипед, спилить мешающие горы и гнать вперед, никуда не сворачивая!

Источник