А. Головнёв

Точные и приближённые алгоритмы решения задачи о коммивояжёре (TSP)

1. Постановка задачи, различные вариации задачи, NP-сложность задач.
2. Точные алгоритмы решения TSP.
1. Алгоритм на основе экспоненциального метода "разделяй и властвуй" (O*(4^n * n^logn), полиномиальная память).
2. Мемоизация (O*(3^n), экспоненциальная память).
3. Алгоритм Хелда-Карпа (динамическое программирование, O*(2^n),
   экспоненциальная память).
4. Алгоритм на основе формулы включений-исключений (O*(2^n*C),
   память O*(C)).
3. Приближённые алгоритмы решения TSP.
1. Результаты о неприближаемости задачи о коммивояжёре.
2. Метрический TSP, дерево Штейнера.
3. Жадный алгоритм для метрического TSP (ratio=O(logN)).
4. Алгоритм на основе MST для метрического TSP (ratio=2).
5. Алгоритм Кристофидеса для метрического TSP (ratio=1.5).
4. Асимметрический TSP.
1. Точные алгоритмы.
2. Приближённые алгоритмы.
3. logN-приближенный алгоритм для асимметрического TSP.
5. Новые приближённые алгоритмы для частных случаев метрического TSP.