Математическая модель решения задачи коммивояжера. Поиск кратчайшего замкнутого пути обхода нескольких городов и возвращения в исходную точку. Описание программы и результатов ее тестирования. Основная форма программы после вывода конечных данных.
Аннотация к работе
Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, чтобы посетить каждую вершину однократно и возвратиться в исходную. Задача о гамильтоновых циклах в графе получила различные обобщения. В ходе выполнения курсового проекта требуется написать программу, выполняющую решение аналогичных задач линейного программирования с помощью алгоритма Дейкстры. Xi j - матрица переходов с компонентами: Xi j =-1, если коммивояжер совершает переход из i-го города в j-й, Xi j = 0, если не совершает перехода, где i, j = 1..N и i?j. Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) - въезжает в каждый город только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель; условие (5) - принцип треугольника: ранее выбранный путь оказался длиннее предыдущего.
Введение
В 1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.
Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений - задача коммивояжера, имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем.
Задача коммивояжера актуально и по сей день т.к. люди ищут кратчайшие пути и затраты на эти кратчайшие пути.
Цель курсового проекта: Решение задачи коммивояжера с помощью алгоритма Дейкстры.
Задачи курсового проекта: 1) Составить математическую модель;
2) Разработать схему алгоритма;
3) Составить программный код;
4) Провести анализ полученных результатов.
1. Постановка задачи
Определить длину (Q) кратчайшего маршрута (L) коммивояжера.
Расстояния (Qij) между шестью городами представлены в таблице 1.
Таблица 1 - Условие задачи
Город 1 2 3 4 5 6
1 6 4 12 14 22
2 6 3 8 7 20
3 4 3 10 11 18
4 12 8 10 9 16
5 14 7 11 9 10
6 22 20 18 16 10
В ходе выполнения курсового проекта требуется написать программу, выполняющую решение аналогичных задач линейного программирования с помощью алгоритма Дейкстры.
2. Этапы решения задачи
2.1 Математическая модель
Построим математическую модель: n - число городов.
Xi j , i, j=1..N - матрица затрат, где Ci j - затраты на переход из i-го города в j-й.
Xi j - матрица переходов с компонентами: Xi j = -1, если коммивояжер совершает переход из i-го города в j-й, Xi j = 0, если не совершает перехода, где i, j = 1..N и i?j.
Критерий: , (1) где Cij - матрица стоимости переходов, Xij - матрица переходов, где xij=0, если переход совершен и xij=1 в противном случае
Ограничения: , i = 1..N (2)
, j = 1..N (3)
Ui - Uj N ? Xi j ? N-1, i, j = 1..N, i ? j. (4)
, k= 1..N,t=k-1 (5)
Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) - въезжает в каждый город только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель; условие (5) - принцип треугольника: ранее выбранный путь оказался длиннее предыдущего.
2.2 Разработка алгоритма
Задача коммивояжера является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об нее, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) задача коммивояжера служит своеобразным полигоном, на котором испытываются все новые методы. В данном курсовом проекте реализуется задача коммивояжера методом алгоритма Дейкстры.
В 1959 г. Голландский математик Дейкстра предложил алгоритм, который решает задачу коммивояжера для любой матрицы исходный данных: симметричной, несимметричный и смешанной (отсутствуют некоторые ребра графа).
Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов и вернуться обратно в исходный город, при этом выполняя две проверки: 1) Длина найденного ребра графа должна быть меньше или равна симметричному ребру графа. В противном случае выбирается симметричное ребро
2) треугольника: ранее выбранный путь оказался длиннее предыдущего.
2.3 Описание программы
Для начала вычислений необходимо ввести количество городов.
На рисунке 1 показан этап выбора количества городов. программа задача коммивояжер тестирование
Рисунок 1 - Выбор количества городов
После ввода данных, необходимо нажать кнопку «Enter». После этого программа составит матрицу городов, после чего нам надо ввести с какого города будем стартовать, и заканчивать, и произведет расчет длины пути и порядок обхода городов. Когда программа завершит свой расчет, то в блоке ответа появятся данные конечного результата.
Рисунок 2 - Консоль программы после расчета данных
2.4 Тестирование программы
Определить длину (Q) кратчайшего маршрута (L) коммивояжера. Расстояния (QIJ) между шестью городами представлены в таблице 1.
Пройдем алгоритм вручную.
Начинаем движение с первого города в нашей таблице (Рисунок 3).
Рисунок 3 - Первый шаг расчета
После этого, мы движемся во второй город, выбирая из доступных, с минимальным расстоянием (Рисунок 4).
Рисунок 4 - Второй шаг расчета
Таким образом, проделываем следующие шаги до последнего города.
Условия примера представляют собой симметричную задачу.
После выполненного расчета мы видим, что ответ удовлетворяет условиям. Так же в программе проводилось несколько других тестирований, ответы были положительны.
2.5 Анализ полученных результатов
После успешного тестирования программы, в качестве исходных данных использовались параметры, заданные в курсовом проектировании. Результаты расчета приведены в следующем рисунке 5:
Рисунок 5 - Основная форма программы после вывода конечных данных
Ответ: длина маршрута равна 52, порядок обхода городов: 1>3>2>5>6>4>1
При выполнение ручных расчетов результаты получились положительными.
Вывод
В ходе выполнения курсового проекта были решены следующие задачи: 1) Построена математическая модель;
2) Описан алгоритм задачи;
3) Разработан программный код на языке программирования C ;
4) Решена поставленная задача с помощью разработанной программы;
5) Проанализированы результаты;
Таким образом, можно считать, что цель курсового проекта достигнута.