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

Об этом пишет IFLScience.

У Фокус.Технологии появился свой Telegram-канал. Подписывайтесь, чтобы не пропускать самые свежие и захватывающие новости из мира науки!

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

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

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

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

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

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

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

Важно ИИ помогает исследователям: ученые расшифровали таинственный свиток из Геркуланума (фото)

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

Также мы рассказывали о самой молодой стране мира. Ей всего 14 лет, однако совсем скоро может появиться новая страна, которая заберет этот титул.