ВВЕДЕНИЕ 5
ГЛАВА 1 ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА 7
1.1 Общая характеристика задачи коммивояжера 7
1.1.1 Постановка задачи коммивояжера 7
1.1.2 Математическая модель задачи коммивояжера 9
1.2 Методы решения задачи коммивояжера 11
1.2.1 Точные методы 13
1.2.2 Приближенные и эвристические методы 30
ГЛАВА 2 РЕАЛИЗАЦИЯ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА 39
2.1 Структура программы 39
2.2 Реализация метода ближайшего соседа 40
2.3 Реализация метода ветвей и границ 42
2.4 Интерфейс приложения 45
ГЛАВА 3 СРАВНИТЕЛЬНЫЙ АНАЛИЗ РЕАЛИЗАЦИЙ 47
3.1 Технические данные для сравнительного анализа 47
3.2 Метод ближайшего соседа 47
3.3 Метод ветвей и границ 50
3.4 Сравнение двух реализованных алгоритмов 53
ЗАКЛЮЧЕНИЕ 56
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 57
ПРИЛОЖЕНИЕ А 60
Задача о коммивояжере - относится к классу NP-полных задач дискретной оптимизации. Время работы алгоритма, решающего задачу коммивояжера, существенно зависит от размера входных данных, то есть от количества городов.
Для нее до сих пор не найдено быстрых полиномиальных алгоритмов. Для графов задача формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе. То есть каждую вершину графа нужно посетить ровно один раз.
Актуальность: Задача коммивояжера на сегодняшнее время применяется в различных сферах, таких как: маршрутизация транспортных потоков и выбор оптимальной траектории движения рабочего инструмента, а также в сферах, которые на первый взгляд не связаны с маршрутизацией: секвенирования нуклеотидных последовательностей биополимеров, эвристического определения схожести строк, построения практических алгоритмов исследования специально определённых бесконечных грамматических структур и построения эволюционных деревьев.
Объект исследования - задача коммивояжера.
Предмет исследования - метод ветвей и границ и метод ближайшего соседа для решения задачи коммивояжера.
Цель бакалаврской работы - анализ существующих методов решения задачи коммивояжера и реализация рассмотренных алгоритмов, выявление их достоинств и недостатков.
Для достижения цели работы необходимо решить следующие задачи:
1. Рассмотреть существующие методы решения задачи коммивояжера;
2. Реализовать метод ветвей и границ для решения задачи
коммивояжера на языке программирования Python;
3. Реализовать метод ближайшего соседа для решения задачи коммивояжера на языке программирования Python;
4. Выявить достоинства каждого реализованного метода.
Обзор по главам:
1) В первой главе приводиться общая характеристика задачи коммивояжера, описание и постановки этой задачи, математическая модель и описание существующих методов решения задачи коммивояжера;
2) Во второй главе - разработка двух выбранных методов - ветвей и границ и ближайшего соседа, описание структуры программной реализации.
3) В третьей главе-проведение вычислительных экспериментов и сравнительный анализ полученных результатов.
В ходе выполнения бакалаврской работы были рассмотрены существующие методы решения задачи коммивояжера, достоинства и недоставки всех методов, а также была произведена реализация метода ближайшего соседа и метода ветвей и границ на языке программирования Python.
В ходе работы были выполнены следующие задачи:
1. Рассмотрены существующие методы решения задачи коммивояжера;
2. Реализован метод ближайшего соседа для решения задачи
коммивояжера на языке программирования Python;
3. Реализован метод ветвей и границ для решения задачи
коммивояжера на языке программирования Python;
4. Выявлены достоинства каждого реализованного метода.
5. Проведены сравнения реализованных методов.
Были пошагово реализованы методы ближайшего соседа и ветвей и границ на языке программирования Python, с использованием пользовательского графического интерфейса.
Проведены вычислительные эксперименты, состоящие в сравнении времени работы данных методов, которые показали, что метод ближайшего соседа работает намного быстрее, чем метод ветвей и границ.
