Уильям Кук
Уильям Кук
Даниэль Эспиноза
Даниэль Эспиноза
Маркос Гойкулея
Маркос Гойкулея
Келд Хельсгаун
Келд Хельсгаун






Пресса о науке и не только

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



Маршрут имеет длину 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 метров. Это немного меньше, чем расстояние от Земли до Луны. Шнобелевская премия отдыхает.


Создание искусственных рогов носорога

Рог носорога не является рогом в традиционном смысле, как рог коровы или копыто. Фактически, рог носорога - это пучок волос, плотно упакованных и склеенных экссудатами сальных желез на носу животного. Авторы предлагают экономичный заменитель рога носорога
подробнее

Наблюдения за волосами доктора Роббинса

Длина волос в парках развлечений Флориды, распределение длины волос среди населения США
подробнее


facebook
Источник - пресса
Рейтинг@Mail.ru
(c) 2010-2020 Шнобелевская премия ig-nobel@mail.ru