Решение задачи коммивояжера с помощью алгоритма Дейкстры

Размещено на http://www.allbest.ru/

Введение

В 1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.

Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений - задача коммивояжера, имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем.

Задача коммивояжёра актуально и по сей день т.к. люди ищут кратчайшие пути и затраты на эти кратчайшие пути.

Цель курсового проекта: Решение задачи коммивояжера с помощью алгоритма Дейкстры.

Задачи курсового проекта:

1) Составить математическую модель;

2) Разработать схему алгоритма;

3) Составить программный код;

4) Провести анализ полученных результатов.



1. Постановка задачи

Определить длину (Q) кратчайшего маршрута (L) коммивояжера.

Расстояния (Q_ij) между шестью городами представлены в таблице 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 - число городов.

X_{i j} , i, j=1..N - матрица затрат, где C_{i j} - затраты на переход из i-го города в j-й.

X_{i j} - матрица переходов с компонентами:

X_{i j} = -1, если коммивояжер совершает переход из i-го города в j-й,

X_{i j} = 0, если не совершает перехода,

где i, j = 1..N и ij.

Критерий:

, (1)

где С_ij - матрица стоимости переходов,

X_ij - матрица переходов, где x_ij=0, если переход совершен и x_ij=1 в противном случае

Ограничения:

, i = 1..N (2)

, j = 1..N (3)

U_i - U_j + N X_{i 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) коммивояжера. Расстояния (Q_IJ) между шестью городами представлены в таблице 1.

Пройдем алгоритм вручную.

Начинаем движение с первого города в нашей таблице (Рисунок 3).

Рисунок 3 - Первый шаг расчета

После этого, мы движемся во второй город, выбирая из доступных, с минимальным расстоянием (Рисунок 4).

Рисунок 4 - Второй шаг расчета

Таким образом, проделываем следующие шаги до последнего города.

Условия примера представляют собой симметричную задачу.

После выполненного расчета мы видим, что ответ удовлетворяет условиям. Так же в программе проводилось несколько других тестирований, ответы были положительны.



2.5 Анализ полученных результатов

После успешного тестирования программы, в качестве исходных данных использовались параметры, заданные в курсовом проектировании. Результаты расчета приведены в следующем рисунке 5:

Рисунок 5 - Основная форма программы после вывода конечных данных

Ответ: длина маршрута равна 52, порядок обхода городов:

1>3>2>5>6>4>1

При выполнение ручных расчётов результаты получились положительными.



Заключение

В ходе выполнения курсового проекта были решены следующие задачи:

1) Построена математическая модель;

2) Описан алгоритм задачи;

3) Разработан программный код на языке программирования C++;

4) Решена поставленная задача с помощью разработанной программы;

5) Проанализированы результаты;

Таким образом, можно считать, что цель курсового проекта достигнута.



Приложение 1

Код программы «Решение задачи коммивояжера с помощью алгоритма Дейкстры»

//

#include <vcl.h>

#include <tchar.h>

#include <stdio.h>

#include <conio.h>

//

void main()

{

int c2,c3,i,k,j,n,e,q,v,m,z,x,min,a,min2,h=0,c=0;

printf("Koli4estvo gorodov : ");scanf("%i",&n); //ввод количество городов

int *t=new int[n];

int *t2=new int[n];

int **kg=new int*[n];

for(i=0;i<n;i++)

kg[i]=new int[n];

int **kg1=new int*[n];

for(i=0;i<n;i++)

kg1[i]=new int[n];

for(i=0;i<n;i++)

for(j=0;j<n;j++)

kg[i][j]=0;

for(i=0;i<n;i++) //заполнение расстояние между городами

for(j=i+1;j<n;j++)

{

printf("vedite racto9nnie %i do %i: ",i+1,j+1);

scanf("%i",&kg[i][j]);

kg1[i][j]=kg[i][j];

}

clrscr();

printf(" ");

for(i=0;i<n;i++)

printf("%3i",i+1);

printf("\n\n\n\n");

for(i=0;i<n;i++) // заполнение массива городов симметрично

{

printf("%2i ",i+1);

for(j=0;j<n;j++)

{

kg[j][i]=kg[i][j];

kg1[j][i]=kg[i][j];

printf("%3i",kg[i][j]);

}

printf("\n\n");

}

printf("Vvedite na4al'nuy to4ky : ");scanf("%i",&k); //ввод с какого города гачгётся путь

k--;

e=k;x=k;

q=1;c2=0;

v=0;z=2;

t[0]=k;

do //поиск минимального пути между городами

{

min=99999;

for(j=x+1;j<n;j++)

if(min>=kg[x][j] && kg1[x][j]!=-1)

{

min=kg[x][j];

m=j;

}

for(j=0;j<x;j++)

if(min>kg[j][x] && kg1[j][x]!=-1)

{

min=kg[j][x];

m=j;

}

t2[q]=x;

t[q]=m;

for(j=x+1;j<n;j++)

kg1[x][j]=-1;

for(j=0;j<x;j++)

kg1[j][x]=-1;

x=m;

z=0;

for(i=0;i<n && z!=1;i++)

for(j=i+1;j<n;j++)

if(kg1[i][j]==-1)

v=1;

else

{v=3;z=1;break;}

q++;

}

while(v!=1);

t2[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]];

c2=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]];}

if(c>c2 && q!=0 && z<q)

{

z=t2[e];

t2[e]=t2[e-1];

t2[e-1]=z;

z=t[q-1];

t[q-1]=t[q-2];

t[q-2]=z;

z=q;

q=-1;e=-1;c=0;c2=0;

}

q++;

e++;

}

while(v!=q);

printf("\n\nput : %i",t[0]+1); //вывод пути

for(i=1;i<q;i++)

printf("-%i",t[i]+1);

printf("\n\n");

printf("dlina puti : %i",c);//вывод длинны пути

getch();

}

Размещено на Allbest.ru