На информационном ресурсе применяются рекомендательные технологии (информационные технологии предоставления информации на основе сбора, систематизации и анализа сведений, относящихся к предпочтениям пользователей сети "Интернет", находящихся на территории Российской Федерации)

Новости науки

6 933 подписчика

Свежие комментарии

  • Dim Rex
    поднять оперативку  по   источникам   =Маня  -Ваня итдитп  = по опер  части  гулага =лагерей  то   всплывали   такие ..."Неизвестная раса...
  • Dim Rex
    История  как  таковой  нет  Был  потоп   погибла     цивилизация     массовый исход из  СЕ +Верус =severus =север на ..."Неизвестная раса...
  • Александр Зонов
    Прошло почти 7 лет. Где эти мобильные АЭС? "Пандемия" коронавируса и проведение СВО на Украине - не при чём. Даже есл...Минобороны РФ к 2...

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

Самый длинный путь по воде без выхода на сушу составляет более 30 тысяч километров, выяснили программисты, использовав алгоритм оптимизации для рассчета самых длинных прямых маршрутов по суше и по воде. Препринт статьи опубликован на сайте arXiv, коротко об истории поиска маршрута сообщает MIT Technology Review.

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

Маршрут, предложенный в r/MapPorn

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

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

Использование подобного алгоритма оптимизации позволило исследователям автоматически рассчитать самые длинные прямые маршруты по суше и воде за 10 и 45 минут соответственно: так, по воде этот путь действительно лежит из Пакистана в Камчатку и занимает 32089 километров, а по суше — от побережья Восточно-Китайского моря до Португалии (примерно 11241 километр).

Chabukswar & Mukherjee / arXiv 2018

Поделиться

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

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

Ссылка на первоисточник
наверх