Самый длинный путь по воде без выхода на сушу составляет более 30 тыс. километров, выяснили программисты, использовав алгоритм оптимизации для расчета самых длинных прямых маршрутов по суше и по воде. Препринт статьи опубликован на сайте arXiv, коротко об истории поиска маршрута сообщает N+1 со ссылкой на MIT Technology Review.
В конце декабря 2012 года один из пользователей сообщества Reddit r/MapPorn предложил самый длинный прямой маршрут по воде без выхода на сушу: он занимал примерно 20 тыс. миль (около 32 тыс. километров) и проходил от побережья Аравийского моря в Пакистане до полуострова Камчатка. Нарисованная карта вызвала множество обсуждений: как правильности предложенного маршрута, так и расчета прямого пути по суше.
Решение подобной задачи вручную - достаточно трудоемкий процесс, так как нажно много карт очень большого разрешения. Автоматический перебор всех возможных маршрутов из прямых линий, которые обычно можно увидеть на глобусах, тоже занял бы много времени даже для относительно мощного компьютера.
Роуэн Чабуксвар из ирландского исследовательского центра United Technologies и Кушал Мухержи из индийского подразделения IBM предложили использовать алгоритм перебора, но с дополнительной оптимизацией - отсеиванием неподходящих маршрутов на ранних стадиях. Соглано решению программистов, все множество возможных вариантов делится на подмножества меньших размеров и таким образом формируется дерево поиска. Затем верхняя граница (наибольшее значение) подмножества сравнивается с верхней границей предшествующего ему подмножества: если она меньше, то это подмножество отбрасывается за отсутствием подходящих вариантов, если же больше - то она становится "рекордом" (наибольшим значением), и границы последующих множеств сравниваются уже с ней.
Использование подобного алгоритма оптимизации позволило исследователям автоматически рассчитать самые длинные прямые маршруты по суше и воде за 10 и 45 минут соответственно: так, по воде этот путь лежит из Пакистана в Камчатку и занимает 32 089 километров, а по суше - от побережья Восточно-Китайского моря до Португалии (примерно 11 241 километр).
