План многомесячного пьяного тура: ученые узнали, как лучше всего посетить все бары
Группа исследователей составила теоретический пешеходный маршрут, который проходит через все 81 998 баров Южной Кореи. Этот эксперимент является очень сложным примером "задачи коммивояжера" — математической задачи, которая заключается в нахождении кратчайшего маршрута с посещением нескольких точек ровно один раз и возвращением к началу.
Об этом пишет IFLScience.
У Фокус.Технологии появился свой Telegram-канал. Подписывайтесь, чтобы не пропускать самые свежие и захватывающие новости из мира науки!
Уильям Кук, профессор Университета Ватерлоо, возглавлял команду, которая провела это монументальное вычисление. "Общее время пешего путешествия в оба конца составляет 15 386 177 секунд, или 178 дней, 1 час, 56 минут и 17 секунд", — пояснил Кук.
Ученый в шутку добавил: "По дороге вам нужно будет останавливаться, чтобы выпить много напитков". Несмотря на беззаботную презентацию, проект стал серьезной демонстрацией передовых методов оптимизации, а не планом многомесячного пьяного тура.
Задача коммивояжера, впервые сформулированная в XIX веке, широко известна своей сложностью. Она относится к категории "NP-тяжелых", что означает, что с увеличением количества пунктов назначения вычислительные усилия, необходимые для решения задачи, растут с необычайной скоростью.
Вариант задачи для южнокорейского паба предусматривал вычисление более 3,3 миллиарда временных интервалов между отдельными точками. Чтобы справиться с этим, команда Кука использовала эвристику Лин-Кернигана — эффективный алгоритм для генерирования близких к оптимальным решений — и метод плоскости отсечения, который упрощает массивные задачи маршрутизации, устраняя избыточные пути.
Кук отметил, что целью этих масштабных задач является совершенствование инструментов оптимизации для использования в реальном мире.
"Мир имеет ограниченные ресурсы, и цель математической оптимизации и исследования операций — помочь нам эффективно использовать эти ресурсы", — заявил он.
Хотя количество возможных путей между 81 998 барами почти не поддается пониманию — их количество составляет 2 с 367 000 нулями после нее — исследователи показали, что комбинация умных алгоритмов все еще может генерировать реалистичные, почти идеальные решения.
ВажноХотя вряд ли кто-то пойдет по этому пути пешком, проект демонстрирует полезность прикладной математики в решении сложных логистических задач. От городского планирования до управления цепочками поставок, такие проблемы, как задача коммивояжера, остаются центральными для того, как мы организуем ресурсы, время и движение в современном мире.
Ранее Фокус писал о подземном городе Деринкую в Турции. Исследователи считают, что он возник во фригийский период, примерно в VIII-VII веках до нашей эры.
Также мы рассказывали о самой молодой стране мира. Ей всего 14 лет, однако совсем скоро может появиться новая страна, которая заберет этот титул.