План многомесячного пьяного тура: ученые узнали, как лучше всего посетить все бары

Фото: Unsplash

Группа исследователей составила теоретический пешеходный маршрут, который проходит через все 81 998 баров Южной Кореи. Этот эксперимент является очень сложным примером "задачи коммивояжера" — математической задачи, которая заключается в нахождении кратчайшего маршрута с посещением нескольких точек ровно один раз и возвращением к началу. Об этом пишет IFLScience.

Уильям Кук, профессор Университета Ватерлоо, возглавлял команду, которая провела это монументальное вычисление. "Общее время пешего путешествия в оба конца составляет 15 386 177 секунд, или 178 дней, 1 час, 56 минут и 17 секунд", — пояснил Кук.

Ученый в шутку добавил: "По дороге вам нужно будет останавливаться, чтобы выпить много напитков". Несмотря на беззаботную презентацию, проект стал серьезной демонстрацией передовых методов оптимизации, а не планом многомесячного пьяного тура.

Задача коммивояжера, впервые сформулированная в XIX веке, широко известна своей сложностью. Она относится к категории "NP-тяжелых", что означает, что с увеличением количества пунктов назначения вычислительные усилия, необходимые для решения задачи, растут с необычайной скоростью.

Вариант задачи для южнокорейского паба предусматривал вычисление более 3,3 миллиарда временных интервалов между отдельными точками. Чтобы справиться с этим, команда Кука использовала эвристику Лин-Кернигана — эффективный алгоритм для генерирования близких к оптимальным решений — и метод плоскости отсечения, который упрощает массивные задачи маршрутизации, устраняя избыточные пути.

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

"Мир имеет ограниченные ресурсы, и цель математической оптимизации и исследования операций — помочь нам эффективно использовать эти ресурсы", — заявил он.

Хотя количество возможных путей между 81 998 барами почти не поддается пониманию — их количество составляет 2 с 367 000 нулями после нее — исследователи показали, что комбинация умных алгоритмов все еще может генерировать реалистичные, почти идеальные решения.

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

Ирина Скиба / Skibair
Журналист ARDinform