Решена специальная задача коммивояжера 30-летней давности

16 январь, 2013 - 14:20Леонід Бараш

Наука о вычислительной сложности, в частности, преследует цель решить задачу коммивояжера, когда время, необходимое для получения оптимального решения, является жизненно важным для практических задач, возникающих сегодня, таких как управление воздушным движением или доставка свежих продуктов. Д-р Владимир Дейнеко из бизнес-школы Уорика (Warwick Business School, Coventry, UK) с коллегами решил специальный случай проблемы 30-летней давности.

Задача коммивояжера была сформулирована примерно 150 лет назад. Она заключалась в отыскании кратчайшего маршрута, при котором коммивояжер мог бы посетить всех своих заказчиков по одному разу и финишировать на старте. В XXI веке аналогичная проблема возникает в многочисленных случаях, к примеру, при доставке свежих продуктов в супермаркеты, поставке компонентов на производственные конвейеры и линии, управлении воздушным движением и даже при расшифровке ДНК. Основу для решения этих задач образуют сложные компьютерные программы оптимизации. Время, требуемое для получения оптимального решения, является крайне важным с точки зрения их практического применения.

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

Д-р Дейнеко совместно с Eranda Cela (University of Technology Graz, Austria) и Gerhard Woeginger (Eindhoven University, the Netherlands) решил специальный случай задачи коммивояжера, или открытую проблему, впервые сформулированную 30 лет назад.

Он прокомментировал исследование следующим образом: «Задача коммивояжера служит в качестве тестовой для всех новых и существенных подходов к решению оптимизационных задач. Она принадлежит к множеству задач класса NP, которые недетерминированная машина Тьюринга в состоянии решить за полиномиальное количество времени. Очевидно, имеются некоторые специальные случаи, когда задача коммивояжера может быть эффективно решена. Простейший возможный случай, когда города расположены на прямой линии и расстояние между ними также измеряется по прямой. Вероятно, следующий наиболее простой случай, когда города расположены на двух перпендикулярных линиях и расстояния между ним также измеряются по прямой. «Вопреки очевидной простоте, этот специальный случай проблемы обсуждается в научном сообществе уже около 30 лет. Вплоть до появления нашей работы не было известно, существует ли алгоритм, который гарантирует нахождение оптимального решения для какого-нибудь случая этой проблемы в пределах разумного времени. Теперь мы доказали, что этот случай может быть легко решен за число шагов, пропорциональное квадрату количества городов».