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






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

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



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


Авторство в песнях Леннона-Маккартни

В течение трех лет эксперты обучали искусственный интеллект распознавать музыкантов, используя 70 песен, написанных исключительно Ленноном или Маккартни. В результате установлено, A Hard Days night с уверенностью до 90 процентов принадлежит Джону Леннону
подробнее

Каннибалы сорвали выборы в Папуа-Новой Гвинее, съев несколько колдунов

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


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