Кратчайший пешеходный тур по пабам Великобритании

Маршрут имеет длину 45 495 км, это больше окружности Земли

University of Waterloo Март 2018

Уильям Кук (William Cook), Университет Ватерлоо (University of Waterloo), Канада, Даниэль Эспиноза (Daniel Espinoza), Gurobi Optimization, США, Маркос Гойкулея (Marcos Goycoolea), Университет Адольфо Ибанеса (Universidad Adolfo Ibanez), Чили, Келд Хельсгаун (Keld Helsgaun), Университет Роскилле (Roskilde University), Дания, публикуют результаты грандиозного труда "Кратчайший пешеходный тур по пабам Великобритании" (A shortest-possible walking tour through the pubs of the United Kingdom), University of Waterloo, Март 2018.

Как последовательно, от одного к другому, кратчайшем путем, посетить все пабы и вернуться домой? Команда математиков решила эту задачу за два года. Используя географические координаты 24 727 пабов, предоставленных сайтом Pubs Galore (Изобилие пабов), и измеряя расстояние между любыми двумя пабами как длину маршрута, созданного Google Maps, авторы проложили самый короткий путь между всеми пабами Великобритании. Точнее не пабами, а остановками рядом с пабами.

Всего существует 305 699 901 пар пабов. Список из 24 727 пабов, расположенных один за другим в правильном порядке, напоминает телефонную книгу большого размера. Чтобы добраться до острова Мэн, Северной Ирландии и островов Шотландии, используются регулярные маршруты пассажирских паромов (там тоже можно купить и пиво, и другие алкогольные напитки). Построение пути - это решение проблемы коммивояжера (TSP), одна из самых известных задач комбинаторной оптимизации. Инструмент, называемый линейным программированием, позволяет решать подобные задачи. В расчетах использовалась улучшенная версия реализации Concorde метода TSP.

Запущен метод плоскости резки в тандеме с вариантом кода Келда Хельсгауна LKH. Использована процедура поиска ветвей и границ. В этом процессе набор маршрутов неоднократно подразделяется и метод результирующей плоскости применяется к результирующим подзадачам TSP. Общее количество компьютерного времени составило 305,2 дня на одном процессорном ядре сервера Linux. На самом деле, результата не пришлось ждать целых 10 месяцев, так как поиск выполняли параллельно на 48 ядрах. Используя различные настройки для проверки правил выбора, запустили фазу ветвления и привязки второй раз. Этот второй прогон занял в общей сложности 1381,1 дня.

Кратчайший пешеходный тур по пабам

Оптимальный маршрут имеет длину 45 495 239 метров, это больше, чем окружность Земли. Мы не ставили перед собой задачу увеличить число поклонников блуждания по пабам, чтобы пропустить пинту-другую,- сообщил руководитель проекта, профессор Уильям Кук. Проблема британского паба использовалась как средство для разработки и тестирования методов оптимизации общего назначения, которые широко применяются в науке, промышленности и торговле.

Следующая цель - кратчайший пешеходный маршрут через 49 603 остановки из Национального реестра исторических мест США. Проблема просто зверь. В настоящее время у нас есть путь длиной 350,201,525 метров. Это немного меньше, чем расстояние от Земли до Луны. Шнобелевская премия отдыхает.

Комментарий:

Шнобелевская премия - 2003 - прикладная наука

Джону Полу Стэппу, Эдварду Эй. Мерфи мл и Джорджу Николсу за закон Мерфи, который звучит так: Если существует два или более вариантов сделать что-либо, один из которых может привести к катастрофе, то кто-то обязательно выберет именно этот вариант из всех
подробнее

Шнобелевская премия 2004 медицина

Доктор Стивен Стэк, университет Вэйна, Детройт, Мичиган, США, и профессор социологии Джеймс Гандлах, университет Оберна, Алабама, США, опубликовали исследование - Влияние музыки кантри на самоубийство в журнале Social Forces. Проанализировали 1400 хитов
подробнее

Источник - пресса

Шнобель Процедура Пресса Анналы Архив Статьи Шнобелист