План багатомісячного пияцького туру: вчені дізналися, як найкраще відвідати всі бари

Про це пише IFLScience.

У Фокус.Технології з'явився свій Telegram-канал. Підписуйтеся, щоб не пропускати найсвіжіші та найзахопливіші новини зі світу науки!

Вільям Кук, професор Університету Ватерлоо, очолював команду, яка провела це монументальне обчислення. "Загальний час пішої подорожі в обидва кінці становить 15 386 177 секунд, або 178 днів, 1 годину, 56 хвилин і 17 секунд", — пояснив Кук.

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

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

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

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

"Світ має обмежені ресурси, і мета математичної оптимізації та дослідження операцій — допомогти нам ефективно використовувати ці ресурси", — заявив він.

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

Важливо ШІ допомагає дослідникам: вчені розшифрували таємничий сувій із Геркулануму (фото)

Хоча навряд чи хтось піде цим шляхом пішки, проєкт демонструє корисність прикладної математики у вирішенні складних логістичних завдань. Від міського планування до управління ланцюгами поставок, такі проблеми, як задача комівояжера, залишаються центральними для того, як ми організовуємо ресурси, час і рух у сучасному світі.

Раніше Фокус писав про підземне місто Дерінкую у Туреччині. Дослідники вважають, що воно виникло у фрігійський період, приблизно у VIII-VII століттях до нашої ери.

Також ми розповідали про наймолодшу країну світу. Їй лише 14 років, проте зовсім скоро може з'явитися нова країна, яка забере цей титул.