Задача коммивояжера (проект) — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показано 11 промежуточных версии 4 участников)
Строка 1: Строка 1:
 
{{Карточка_проекта
 
{{Карточка_проекта
|name=Задача коммивояжера
+
|name=Задача коммивояжера  
 
|mentor=Алексей Гусаков
 
|mentor=Алексей Гусаков
|mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}
+
|mentor_login={{URLENCODE:Gusakov|WIKI}}
 
|semester=Весна 2015
 
|semester=Весна 2015
 
|course=1
 
|course=1
 
|summer=
 
|summer=
 
|categorize=yes
 
|categorize=yes
 +
|is_archived=yes
 
}}
 
}}
  
Строка 24: Строка 25:
  
 
=== Какие будут использоваться технологии? ===
 
=== Какие будут использоваться технологии? ===
* gtest
 
 
* Визуализация на python
 
* Визуализация на python
 +
* Библиотека Lemon для алгоритмов на графах
 +
* gtest
  
 
=== Темы вводных занятий ===
 
=== Темы вводных занятий ===
Строка 39: Строка 41:
  
 
Точный путь:
 
Точный путь:
* удв: Алгоритм работает на графе до 20 вершин, с помощью визуализатора можно понять, как всё работает
+
* 4: Алгоритм работает на графе до 20 вершин
* хор: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин
+
* 6: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин
* отл: Метод ветвей и границ с линейным программированием
+
* 8: Метод ветвей и границ с линейным программированием
 +
 
 +
+1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.
 +
 
 +
+1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не получается добиться точного решения?
  
 
Приближённый путь:
 
Приближённый путь:
* удв: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку + визуализация
+
* 4: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку
* хор: 2-приближение с помощью эйлерова цикла
+
* 6: 2-приближение с помощью эйлерова цикла
* отл: 3/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 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не удаётся получить лучшего решения, чем описанные?