Задача коммивояжера (проект)
| Ментор | Алексей Гусаков |
| Учебный семестр | Весна 2015 |
| Учебный курс | 1-й курс |
Что это за проект?
Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо "не сильно" (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.
Чему вы научитесь?
- Основам теории графов
- Основам приближённых алгоритмов
- Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор
- Писать код без ошибок (ну почти что)
- Визуализировать решение
Какие начальные требования?
- Программирование на C/C++ (в рамках прослушанного курса)
- Желание разбираться в алгоритмах
Какие будут использоваться технологии?
- gtest
- Визуализация на python
Темы вводных занятий
- Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)
- Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение
- Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование
Направления развития
Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.
Критерии оценки
Как уже сказано, есть два пути решения задачи - точный и приближённый.
Точный путь:
- 4: Алгоритм работает на графе до 20 вершин
- 6: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин
- 8: Метод ветвей и границ с линейным программированием
+1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.
Приближённый путь:
- 4: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку
- 6: 2-приближение с помощью эйлерова цикла
- 8: 3/2-приближение с использованием поиска паросочетания
+1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.
