Задача коммивояжёра

Содержание

• 
  1История
  
• 
  2Формальное определение
  
  • 
    2.1Представление в виде графа
    
    • 
      2.1.1Асимметричная и симметричная задачи
      
    • 
      2.1.2Метрическая задача
      
  • 
    2.2Формулировка в виде задачи дискретной оптимизации
    
• 
  3Алгоритмическая сложность
  
• 
  4Замкнутый и незамкнутый варианты задачи
  
• 
  5Методы решения
  
  • 
    5.1Простейшие
    
  • 
    5.2Метод ветвей и границ
    
  • 
    5.3Метод эластичной сети
    
    • 
      5.3.1История
      
    • 
      5.3.2Алгоритм
      
  • 
    5.4Муравьиный алгоритм
    
  • 
    5.5Генетический алгоритм
    
  • 
    5.6Алгоритм динамического программирования
    
• 
  6См. также
  
• 
  7Примечания
  
• 
  8Литература
  

История[править | править код]
С задачей коммивояжёра связана задача о поиске гамильтонового цикла. Примером такой задачи является задача о ходе коня, известная по крайней мере с XVIII века^[1]. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию», датированную 1759 годом^[2]. Другим примером задачи на поиск гамильтонового цикла является икосиан: математическая головомка, в которой надо пройти по додекаэдру (графу с 20 узлами) побывав в каждой вершине ровно один раз. Эта задача была предложена Уильямом Гамильтоном в XIX веке, он же определил класс таких путей.
В 1832 году издана книга с названием «Коммивояжёр — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера» (нем. Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur), в которой описана задача, но математический аппарат для её решения не применяется. Зато в ней предложены примеры маршрутов для некоторых регионов Германии и Швейцарии.
Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру, который сформулировал её на математическом коллоквиуме в 1930 году так:
Мы называем задачей посыльного (поскольку этот вопрос возникает у каждого почтальона, в частности, её решают многие путешественники) задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известно.

Гамильтон Уильям Роуэн
Вскоре появилось известное сейчас название задача странствующего торговца (англ. traveling salesman problem), которую предложил Хасслер Уитни (англ. Hassler Whitney) из Принстонского университета.
Вместе с простотой определения и сравнительной простотой нахождения хороших решений задача коммивояжёра отличается тем, что нахождение действительно оптимального пути является достаточно сложной задачей. Учитывая эти свойства, начиная со второй половины XX века исследование задачи коммивояжёра имеет не столько практический смысл, сколько теоретический в качестве модели для разработки новых алгоритмов оптимизации.
Многие современные распространенные методы дискретной оптимизации, такие как метод отсечений, ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжёра.
В 1950-е и 1960-е годы задача коммивояжёра привлекла внимание ученых в США и Европе. Важный вклад в исследование задачи принадлежит Джорджу Данцигу, Делберту Рею Фалкерсону (англ. Delbert Ray Fulkerson) и Селмеру Джонсону (англ. Selmer M. Johnson), которые в 1954 году в институте RAND Corporation сформулировали задачу в виде задачи дискретной оптимизации и применили для её решения метод отсечений. Используя этот метод, они построили путь коммивояжёра для одной частной постановки задачи с 49 городами и обосновали его оптимальность. В 1960-е и 1970-е годы задача изучалась многими учеными как теоретически, так и с точки зрения её приложений в информатике, экономике, химии и биологии.
Ричард Карп в 1972 году доказал NP-полноту задачи поиска гамильтоновых путей, из чего, благодаря полиномиальной сводимости, вытекала NP-трудность задачи коммивояжёра. На основе этих свойств им было приведено теоретическое обоснование сложности поиска решений задачи на практике.
Больших успехов удалось достичь в конце 1970-х и 1980-х годах, когда Мартин Грётчел (нем. Martin Grötschel), Манфред Падберг (нем. Manfred Padberg) и Джованни Ринальди (итал. Giovanni Rinaldi) и другие, с применением новых методов деления плоскостью, ветвей и границ вычислили решение для отдельного случая задачи с 2393 городами.
В 1990-е годы Дэвид Аплгейт (англ. David Applegate), Роберт Биксби (англ. Robert Bixby), Вашек Хватал (чеш. Vašek Chvátal) и Уильям Кук (англ. William Cook) установили рекорды по программе Конкорд. Герхард Райнельт (нем. Gerhard Reinelt) создал TSPLIB — набор стандартизованных экземпляров задачи коммивояжёра различной степени сложности для сравнения результатов работы различных групп исследователей. В марте 2005 года задача с 33 810 узлами была решена программой Конкорд: был вычислен путь длиной в 66 048 945 и доказано отсутствие более коротких путей. В апреле 2006 было найдено решение для экземпляра с 85 900 узлами. Используя методы декомпозиции, можно вычислить решения для случаев задачи с миллионами узлов, длина которых менее, чем на 1 % больше оптимальной.
Формальное определение[править | править код]