Задача нетривиальная. В математике у нее есть свое название: это так называемая Проблема коммивояжера — когда нужно найти кратчайший маршрут, который проходит через каждое место ровно один раз и заканчивается в отправной точке пути.
Насколько сложна эта задача, можно понять по примеру, который приводил в 2018 году The Washington Post: тогда на поиск кратчайшего пути между всего 22 пунктами на карте понадобилась тысяча лет т. н. вычислительного времени. Причем до последнего времени считалось, что поиск оптимального маршрута для 25 пунктов и более является вычислительно невозможным. А теперь сравните: в Нидерландах насчитывается 57 912 мест, где расположены различные памятники.
Тем не менее, в Центре количественных методов (Centre for Quantitative Methods), расположенном в Эйндховене, нашли ответ. Для этого потребовалось задействовать 320 мощных процессоров на десяти серверных кластерах в течение 90 лет вычислительного времени.⠀
Цифра, которую получили ученые, может огорчить даже самых заядлых любителей велопутешествий: кратчайший маршрут между всеми памятниками Нидерландов составит 20 тысяч 253 километра с «хвостиком»!
Найдется ли тот энтузиаст, который когда-то отправится по этому маршруту?
Источник: Посольство Нидерландов
