Задача коммивояжера

Изучены эвристический, приближенный и точный алгоритмы решения ЗК.Точные алгоритмы решения ЗК – это полный перебор или усовершенствованный перебор. Оба они, особенно первый, не эффективны при большом числе вершин графа.
Предложен собственный эффективный метод решения ЗК на основе по-строения выпуклого многоугольника и включения в него центральных вершин (городов).
Проведён анализ наиболее рациональных методов решения ЗК и определены области их эффективного действия: для малого числа вершин можно использовать точный метод лексического перебора; для большого числа вершин рациональнее применять метод ветвей и границ или метод автора работы (Анищенко Сергея Александровича).
Изучены практические применения ЗК и задачи с переналадками, сводимые к ЗК.
Приведены тексты программ, позволяющие решить ЗК различными методами.

Введение 3
1. Задача коммивояжера. Общее описание 5
2. Методы решения ЗК 7
2.1. Жадный алгоритм 7
2.2. Деревянный алгоритм 11
2.3. Метод ветвей и границ 16
3.Практическое применение задачи коммивояжера 17
Заключение 19
Список литературы 20