City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Algorithms for the traveling salesman problem
Saint Petersburg / autumn 2017, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

В мини-курсе будут рассмотрены алгоритмы для классической NP-трудной задачи — задачи коммивояжёра, которая формулируется следующим образом: даны \(n\) городов и попарные расстояния между ними, необходимо найти кратчайший маршрут, проходящий по всем городам ровно по одному разу. Практические применения данной задачи включают в себя разработку микросхем, планирование, сборку генома. Трудность данной задачи объясняется тем, что с ростом количества городов количество потенциальных маршрутов растёт очень быстро. Например, даже для пятнадцати городов количество таких маршрутов равно 43 589 145 600. Если считать, что компьютер может перебрать миллиард маршрутов в секунду, то искать решение для задачи с сотней городов ему придётся больше триллиона лет. В то же время в задачах, возникающих на практике, количество городов обычно составляет десятки тысяч. К счастью, всё же есть методы, позволяющие решать такие примеры на практике. Например, в 2004 году был найден оптимальный цикл по 24 978 городам Швеции, а в 2006 был вычислен оптимальный маршрут лазера при построении интегральной схемы через 85 900 точек.

Задаче коммивояжёра посвящено огромное количество статей и исследований, как практических, так и теоретических. На сайте http://www.tsp.gatech.edu/index.html можно найти множество ссылок (статьи, книги, датасеты, программы, игры, соревнования и даже фильм).

Для данной задачи мы узнаем:

  • методы, с помощью которых задачу коммивояжёра решают на практике, — метод ветвей и границ и метод локального поиска;
  • почему в общем случае для данной задачи приближённые алгоритмы вряд ли существуют;
  • \( 1.5 \)-приближённый алгоритмы для задачи коммивояжёра в метрическом пространстве (когда длины рёбер графа удовлетворяют неравенству треугольника);
  • \( 2/3 \)-приближённый алгоритм для случая, когда найти необходимо не минимальный, а максимальный путь коммивояжёра;
  • классический алгоритм, основанный на методе динамического программирования, со временем работы \( O^*(2^n) \);
  • алгоритм, основанный на формуле включений-исключений, со временем работы \( O^*(2^n) \) и псевдополиномиальной памятью;
  • алгоритм со временем работы \( O^*(4^nn^{\log n}) \) и полиномиальной памятью, основанный на методе перебора с возвратом;
  • недавний алгоритм, работающий за время \(O^*(1.66^n)\) для неориентированных графов, основанный на матрицах Татта и быстрой проверке на равенство нуля многочлена;
  • применения к другим NP-трудным задачам.

(Обозначение \(O^*(\cdot)\) выше скрывает множители, зависящие от размера входа полиномиально.)

Date and time Class|Name Venue|short Materials
26 November
11:15–12:45
Лекция 1, Lecture ПОМИ РАН video,  files
26 November
13:00–14:30
Лекция 2, Lecture ПОМИ РАН video