Задача коммивояжера (проект) — различия между версиями
Gusakov (обсуждение | вклад) (→Критерии оценки) |
|||
| (не показано 13 промежуточных версии 4 участников) | |||
| Строка 1: | Строка 1: | ||
{{Карточка_проекта | {{Карточка_проекта | ||
| − | |name=Задача коммивояжера | + | |name=Задача коммивояжера |
|mentor=Алексей Гусаков | |mentor=Алексей Гусаков | ||
| − | |mentor_login={{URLENCODE: | + | |mentor_login={{URLENCODE:Gusakov|WIKI}} |
|semester=Весна 2015 | |semester=Весна 2015 | ||
|course=1 | |course=1 | ||
|summer= | |summer= | ||
|categorize=yes | |categorize=yes | ||
| + | |is_archived=yes | ||
}} | }} | ||
| Строка 24: | Строка 25: | ||
=== Какие будут использоваться технологии? === | === Какие будут использоваться технологии? === | ||
| − | * | + | * Визуализация на python |
| + | * Библиотека Lemon для алгоритмов на графах | ||
* gtest | * gtest | ||
| Строка 37: | Строка 39: | ||
=== Критерии оценки === | === Критерии оценки === | ||
Как уже сказано, есть два пути решения задачи - точный и приближённый. | Как уже сказано, есть два пути решения задачи - точный и приближённый. | ||
| + | |||
Точный путь: | Точный путь: | ||
| − | * | + | * 4: Алгоритм работает на графе до 20 вершин |
| − | * | + | * 6: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин |
| − | * | + | * 8: Метод ветвей и границ с линейным программированием |
| + | |||
| + | +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм. | ||
| + | |||
| + | +1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не получается добиться точного решения? | ||
Приближённый путь: | Приближённый путь: | ||
| − | * | + | * 4: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку |
| − | * | + | * 6: 2-приближение с помощью эйлерова цикла |
| − | * | + | * 8: 3/2-приближение с использованием поиска паросочетания |
| + | |||
| + | +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм. | ||
| + | |||
| + | +1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не удаётся получить лучшего решения, чем описанные? | ||
Текущая версия на 10:42, 20 октября 2015
| Ментор | Алексей Гусаков |
| Учебный семестр | Весна 2015 |
| Учебный курс | 1-й курс |
| Внимание! Данный проект находится в архиве и реализован не будет. |
Что это за проект?
Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо "не сильно" (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.
Чему вы научитесь?
- Основам теории графов
- Основам приближённых алгоритмов
- Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор
- Писать код без ошибок (ну почти что)
- Визуализировать решение
Какие начальные требования?
- Программирование на C/C++ (в рамках прослушанного курса)
- Желание разбираться в алгоритмах
Какие будут использоваться технологии?
- Визуализация на python
- Библиотека Lemon для алгоритмов на графах
- gtest
Темы вводных занятий
- Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)
- Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение
- Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование
Направления развития
Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.
Критерии оценки
Как уже сказано, есть два пути решения задачи - точный и приближённый.
Точный путь:
- 4: Алгоритм работает на графе до 20 вершин
- 6: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин
- 8: Метод ветвей и границ с линейным программированием
+1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.
+1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не получается добиться точного решения?
Приближённый путь:
- 4: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку
- 6: 2-приближение с помощью эйлерова цикла
- 8: 3/2-приближение с использованием поиска паросочетания
+1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.
+1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не удаётся получить лучшего решения, чем описанные?
