Учёные предложили близкое к оптимальному решение асимметричной задачи коммивояжёра

Одна из самых знаменитых задач комбинаторной оптимизации — задача коммивояжёра, заключается в следующем. По заданному критерию оптимальности (самый быстрый, самый дешёвый путь, их совокупность и так далее) необходимо найти самый выгодный маршрут, проходящий через указанные города хотя бы по одному разу с последующим возвратом в исходный город.

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

Асимметричная задача коммивояжёра

Исходная задача коммивояжёра подразумевает, что маршрут между двумя городами в обоих направлениях имеет одинаковую стоимость, что противоречит реальному миру. Примером служат цены на авиабилеты между городами РФ и Европы. Именно такой тип проблем реального мира и называется асимметричной задачей коммивояжёра.

И, в отличие от исходной задачи коммивояжёра, исследователи не могли найти близкое к оптимальному решение для маршрута, пролегающему через большое число городов. До момента, когда сотрудники федеральной политехнической школы Лозанны и Лондонской школы экономики предложили свой подход к решению проблемы.

Сложность асимметричной задачи

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

Как говорит один из авторов статьи, Ола Свенссон, разработка нового подхода началась ещё в 2008 году. За это время он придумал решение для более простой проблемы объединения городов в группы и посещения по крайней мере одного города из каждой группы.

Идея нового алгоритма

Затем, уже со своими коллегами Якубом Тарнавски и Ласло Вегхом, он начал разработку алгоритма, который итеративно формирует меньшие подгруппы в группах городов, до тех пор, пока не найдёт оптимальные маршруты внутри каждой из них. Затем уже найденные пути внутри групп, используя ранее разработанный Свенссоном алгоритм, складываются в единый глобальный маршрут.

Мнения экспертов

Кен Реган из университета Баффало отметил вклад учёных:

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

По словам Свенссона, он и его коллеги планируют представить свои находки для официального рецензирования на предстоящем, пятидесятом по счёту, ежегодном симпозиуме по теории вычислений.