Город
|
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. Этапы решения задачи
.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)
где Сij - матрица
стоимости переходов,
Ограничения:
, 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 Разработка алгоритма
Задача коммивояжера является одной
из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об
неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей
области (оптимизации дискретных задач) задача коммивояжера служит своеобразным полигоном, на котором
испытываются всё новые методы. В данном курсовом проекте реализуется задача
коммивояжера методом алгоритма Дейкстры.
В 1959 г. Голландский математик
Дейкстра предложил алгоритм, который решает задачу коммивояжёра для любой
матрицы исходный данных: симметричной, несимметричный и смешанной (отсутствуют
некоторые ребра графа).
Суть задачи состоит в том, чтобы найти
кратчайший замкнутый путь обхода нескольких городов и вернуться обратно в
исходный город, при этом выполняя две проверки:
) Длина найденного ребра графа должна
быть меньше или равна симметричному ребру графа. В противном случае выбирается
симметричное ребро
) треугольника: ранее выбранный путь
оказался длиннее предыдущего.
.3 Описание программы
Для начала вычислений необходимо ввести
количество городов.
На рисунке 1 показан этап выбора количества
городов.
программа задача коммивояжер
тестирование
Рисунок 1 - Выбор количества городов
После ввода данных, необходимо нажать кнопку «Enter».
После этого программа составит матрицу городов, после чего нам надо ввести с
какого города будем стартовать, и заканчивать, и произведет расчет длины пути и
порядок обхода городов. Когда программа завершит свой расчет, то в блоке ответа
появятся данные конечного результата.
Рисунок 2 - Консоль программы после расчета
данных
2.4 Тестирование программы
Определить длину (Q)
кратчайшего маршрута (L)
коммивояжера. Расстояния (QIJ)
между шестью городами представлены в таблице 1.
Пройдем алгоритм вручную.
Начинаем движение с первого города в нашей
таблице (Рисунок 3).
Рисунок 3 - Первый шаг расчета
После этого, мы движемся во второй город,
выбирая из доступных, с минимальным расстоянием (Рисунок 4).
Рисунок 4 - Второй шаг расчета
Таким образом, проделываем следующие шаги до
последнего города.
Условия примера представляют собой симметричную
задачу.
После выполненного расчета мы видим, что ответ
удовлетворяет условиям. Так же в программе проводилось несколько других тестирований, ответы были положительны.
2.5 Анализ полученных результатов
После успешного тестирования программы, в
качестве исходных данных использовались параметры, заданные в курсовом
проектировании. Результаты расчета приведены в следующем рисунке 5:
Рисунок 5 - Основная форма программы после
вывода конечных данных
Ответ: длина
маршрута равна 52, порядок обхода городов:
→3→2→5→6→4→1
При выполнение ручных расчётов результаты
получились положительными.
Заключение
В ходе выполнения курсового проекта были решены
следующие задачи:
1) Построена математическая модель;
2) Описан алгоритм задачи;
) Разработан программный код на языке программирования C++;
) Решена поставленная задача с помощью
разработанной программы;
) Проанализированы результаты;
Таким образом, можно считать, что цель курсового
проекта достигнута.
Приложение 1
Код программы «Решение задачи коммивояжера с
помощью алгоритма Дейкстры»
//
#include <vcl.h>
#include <tchar.h>
#include <stdio.h>
#include <conio.h>
//main()
{c2,c3,i,k,j,n,e,q,v,m,z,x,min,a,min2,h=0,c=0;("Koli4estvo
gorodov : ");scanf("%i",&n); //ввод
количество
городов*t=new
int[n];*t2=new int[n];**kg=new int*[n];(i=0;i<n;i++)[i]=new int[n];**kg1=new
int*[n];(i=0;i<n;i++)[i]=new int[n];(i=0;i<n;i++)(j=0;j<n;j++)
kg[i][j]=0;(i=0;i<n;i++) //заполнение
расстояние между городами
for(j=i+1;j<n;j++)
{("vedite racto9nnie %i do %i:
",i+1,j+1);("%i",&kg[i][j]);[i][j]=kg[i][j];
}();(" ");(i=0;i<n;i++)("%3i",i+1);("\n\n\n\n");
for(i=0;i<n;i++) // заполнение массива
городов симметрично
{("%2i
",i+1);(j=0;j<n;j++)
{[j][i]=kg[i][j];[j][i]=kg[i][j];("%3i",kg[i][j]);
}("\n\n");
}("Vvedite na4al'nuy to4ky :
");scanf("%i",&k); //ввод
с
какого
города
гачгётся
путь-;=k;x=k;=1;c2=0;=0;z=2;[0]=k;
do //поиск минимального пути между городами
{=99999;(j=x+1;j<n;j++)(min>=kg[x][j]
&& kg1[x][j]!=-1)
{
min=kg[x][j];
}(j=0;j<x;j++)(min>kg[j][x]
&& kg1[j][x]!=-1)
{
min=kg[j][x];
m=j;
}[q]=x;[q]=m;(j=x+1;j<n;j++)[x][j]=-1;(j=0;j<x;j++)[j][x]=-1;=m;=0;(i=0;i<n
&& z!=1;i++)(j=i+1;j<n;j++)(kg1[i][j]==-1)
v=1;
{v=3;z=1;break;}++;
}(v!=1);[q]=x;t[q]=k;q++;v=q;z=0;q=0;c=0;c2=0;e=0;
do // проверка условий алгоритма Дейкстры
{
if(q!=0)
{ c=c+kg[t2[e]][t[q]];=c-kg[t2[e-1]][t[q-1]]-kg[t2[e]][t[q]]+kg[t[q]][t[q-1]]+kg[t2[e-1]][t[q]];}(c>c2
&& q!=0 && z<q)
{=t2[e];[e]=t2[e-1];[e-1]=z;=t[q-1];[q-1]=t[q-2];[q-2]=z;=q;=-1;e=-1;c=0;c2=0;
}++;++;
}(v!=q);("\n\nput :
%i",t[0]+1); //вывод пути(i=1;i<q;i++)("-%i",t[i]+1);("\n\n");("dlina
puti : %i",c);//вывод длинны
пути
getch();
}