html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

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

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

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

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

Reddit


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

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

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

Chabukswar & Mukherjee / arXiv 2018

Chabukswar & Mukherjee / arXiv 2018


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

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

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

Читать дальше
Twitter
Одноклассники
Мой Мир

материал с nplus1.ru

1

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • nplus1.ru
          • ученые
          • исследования
          • домен nplus1.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции