ВВЕДЕНИЕ 4
ПОСТАНОВКА ЗАДАЧИ 6
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ 8
1. ОПИСАНИЕ АЛГОРИТМОВ 10
1.1 Общее описание подхода Тата 10
1.2 Построение матрицы Татта 11
1.3. Эвристический алгоритм нахождения паросочетания минимального веса 12
1.4 Общее описание приближенных алгоритмов решения задачи
коммивояжера 14
1.5. Построение минимального остовного дерева 20
1.6. Алгоритм Флойда 23
1.7. Алгоритм Дейкстры 25
1.8. Вычисление определителя матрицы 26
1.9. Построение Эйлерова цикла 29
1.10. Построение Г амильтонова цикла 32
2. РЕАЛИЗАЦИЯ АЛГОРИТМОВ 34
2.1. Структуры, используемые для реализации алгоритма 34
2.2. Ввод начальных данных 35
2.3. Проверка неравенства треугольника 399
2.4. Минимальное остовное дерево 40
2.5. Алгоритм Флойда 42
2.6. Матрица Татта 42
2.7.Определитель матрицы 43
2.8. Алгоритм поиска паросочетания 44
2.9. Алгоритм Дейкстры 47
2.10. Построение мультиграфа 49
2.11. Эйлеров цикл 51
2.12. Гамильтонов цикл 52
2.13. Поиск веса пути коммивояжера 52
2.14. Вывод данных 53
2.15. Интерфейс программы 56
3. СРАВНЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ РЕАЛИЗОВАННОГО АЛГОРИТМА И 1-ПРИБЛИЖЕННОГО 58
ЗАКЛЮЧЕНИЕ 65
СПИСОК ЛИТЕРАТУРЫ 67
ПРИЛОЖЕНИЕ

Купить

Задача коммивояжера (англ. Travelling salesman problem, сокращённо TSP) занимает особое положение в комбинаторной оптимизации и исследовании операций и представляется значимой проблемой транспортной логистики и маршрутизации (сферы планирования транспортных перевозок). Задача коммивояжера стала известна в отечественной литературе в 1960-1970 годах как задача о бродячем торговце.
В данной задаче рассматривается n городов и матрица попарных расстояний между ними. Коммивояжеру необходимо объехать все n городов, при том каждый город должен посещаться ровно один раз, и, в конце концов, вернуться в исходный город. Единственным условием и смыслом задачи коммивояжера является поиск самого выгодного маршрута посещения городов. Критерием выгодности маршрута может служить общее время в пути, суммарная стоимость дороги или суммарно пройденное расстояние. С математической точки зрения, это задача нахождения гамильтонова цикла наименьшего веса в связном взвешенном неориентированном графе.
Постановка задачи коммивояжера относится к задачам за пределами класса NP, которые не легче NP-полных задач, и называются NP-трудными. Все точные алгоритмы фактически представляют собой оптимизированный полный перебор вариантов. В некоторых случаях эти алгоритмы достаточно быстро находят решения, но в общем случае приходится перебирать все n! циклов. Несмотря на простоту постановки, задача коммивояжера относится к числу трансвычислительных, так как с помощью метода полного перебора не сможет быть решена за время нескольких миллиардов лет никакими компьютерами. Все это служит толчком для математиков к нахождению и
разработке новых численных методов для решения задачи коммивояжера, с которой не получается справиться уже полвека.
Первоначально проблематика задачи коммивояжера была описана еще в 1832 году в книге с названием «Коммивояжер — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера». При дальнейшем исследовании и рассмотрении задача нашла применение в сфере маркетинга, а также областях управленческой деятельности, где имела место значительная территориальная рассредоточенность объектов на местности. Примерами практического применения предоставленного класса задач может служить определение оптимальных маршрутов:
- обслуживания территориально рассредоточенных торговых точек потребителей для доставки товаров;
- сбора почтовых отправлений из почтовых ящиков;
- обслуживания технических объектов военного назначения;
- составления графика движения школьных автобусов по заданным остановкам и другие.
- доставки бутилированной воды;
- сбора сотрудников для доставки вахтовым методом.
Дан взвешенный связный неориентированный граф G=(V,E), где V — множество вершин в графе, E — множество рёбер. Таким образом, вершины будут соответствовать городам, а ребра — дорогам, соединяющим эти города. Главной целью моей дипломной работы является разработка и реализация Windows-приложения на языке C# для нахождения решения Евклидовой задачи коммивояжера на основе алгоритма Кристофидеса с использованием подхода Татта. Алгоритм Кристофидеса является 3/2 - приближенным алгоритмом решения задачи коммивояжера. Таким образом, заменяя в нем шаг прямого поиска минимального совершенного паросочетания на эвристический метод, основанный на подходе Татта, получаем модифицированный алгоритм решения задачи коммивояжера. Стоит отметить, что задачей нового алгоритма является упрощение поиска пути коммивояжера при получении решения близкого к оптимальному. Приложение включает несколько этапов, использующие следующие элементарные алгоритмы:
1. Алгоритм нахождения минимального остовного дерева.
2. Алгоритм Флойда.
3. Алгоритм расчета определителя матрицы.
4. Алгоритм Татта для поиска паросочетаний.
5. Алгоритм Дейкстры.
6. Алгоритм нахождения Эйлерова цикла.
7. Алгоритм нахождения Гамильтонова цикла основе Эйлерова цикла для Евклидовой задачи коммивояжера.
В программе используются два метода поиска кратчайших расстояний: алгоритм Флойда и алгоритм Дейкстры. Стоит отметить, что алгоритм Флойда использован только для поиска матрицы кратчайших расстояний, а алгоритм Дейкстры (реализованный мной в курсовой работе) - для поиска самого пути от заданной вершины до всех остальных. Таким образом, применение уже готовой структуры поиска и вывода кратчайшего расстояния было целесообразным.
Требуется предоставить способ вывода оптимального маршрута коммивояжера и его вес.
Также целью данной дипломной работы является сравнение реализованного алгоритма с 1-приближенным алгоритмом Кристофидеса (реализованным мной в бакалаврской работе) по относительной погрешности и времени работы. Относительную погрешность для метрических данных небольшой размерности можно вычислить с помощью точного решения, находящегося в пакете Mathematica.

Купить