Построение кратчайшего пути коммивояжера

Министерство образования и науки, молодежи и спорта

Национальный аэрокосмический университет им. Н.Е.Жуковского “ХАИ”

кафедра 304

Лабораторная работа №9

по предмету «Дискретная математика»

Выполнила студентка

325 группы

Абкеримова Рушена

Проверил

Чернышов Ю.К.

_______________

Харьков2013

ЛАБОРАТОРНАЯ РАБОТА № 9

«Задача Коммивояжера»

Вариант 7

Заданы координаты пунктов, которые должен посетить коммивояжер ровно по одному разу, начиная с точки (0;0) и возвращаясь в нее же. Найти такую последовательность посещений, при которой суммарное расстояние было бы наименьшим.

(38,-43); (5,12); (-46,23); (-16,15); (-26,-35); (35,44).

Текстыпрограмм:

// коммивояжер.cpp : Defines the entry point for the console application.

//

#include"stdafx.h"

#include<iostream>

#include"math.h"

using namespace std;

const int max_len = 6;//количествопунктов

struct Koord

{

       // автомат содержит данные:

       double x;   // координата х

             double y;   // координатау

};

void vivod(Koord *A);

void vvod(Koord *A);

void vivod_T(Koord T);

double rasst(Koord t1, Koord t2);

double min_L(double *L, int max, int number);

int factorial(int n);

int _tmain(intargc, _TCHAR* argv[])

{

       setlocale(LC_ALL,".1251");

       KoordT[max_len]; // данныепункты, черезкоторыедолженпройтикоммивояжер

       Koord O; // начальный и конечный пункт

       O.x=0;

       O.y=0;

       // ввод

             cout<<"Введите координаты точек пунктов: "<<endl;

             vvod(T);

             int k=factorial(max_len); //количество перестановок, max_len!

             double *mass_L=newdouble[k];

             Koord *mass_T1=newKoord[k];

             Koord *mass_T2=newKoord[k];

             Koord *mass_T3=newKoord[k];

             Koord *mass_T4=newKoord[k];

             Koord *mass_T5=newKoord[k];

             Koord *mass_T6=newKoord[k];

             double L;

             int i=0;

       // генерирование перестановок

for(int i1=0; i1<max_len; i1++)

for(int i2=0; i2<max_len; i2++)

       if(i2!=i1)

       {

             for(int i3=0; i3<max_len; i3++)

             if(i3!=i1&&i3!=i2)

             {

                    for(int i4=0; i4<max_len; i4++)

                    if(i4!=i1&&i4!=i2&&i4!=i3)

                    {

                           for(int i5=0; i5<max_len; i5++)

                          if(i5!=i1&&i5!=i2&&i5!=i3&&i5!=i4)

                          {

                                 for(int i6=0; i6<max_len; i6++)

                                 if(i6!=i1&&i6!=i2&&i6!=i3&&i6!=i4&&i6!=i5)

                                 {                                                                              /*                                                                                   vivod_T(T[i1]);                                                                      vivod_T(T[i2]);                                                                      vivod_T(T[i3]);                                                                      vivod_T(T[i4]);                                                                       vivod_T(T[i5]);                                                                         vivod_T(T[i6]);                                                                      */                                                                L=rasst(O,T[i1])+rasst(T[i2],T[i3])+rasst(T[i3],T[i4])+rasst(T[i4],T[i5])+rasst(T[i6],O);                                 /*cout<<"Суммарноерасстояние: "<<L<<endl<<endl;*/                                       mass_T1[i]=T[i1];                                                                    mass_T2[i]=T[i2];                                                                    mass_T3[i]=T[i3];                                                                    mass_T4[i]=T[i4];                                                                     mass_T5[i]=T[i5];                                                                         mass_T6[i]=T[i6];                                                                    mass_L[i]=L;

                                 i++;

                                 }

                          }

                    }

             }

       }

       int number=0;

       doubleres_L=min_L(mass_L,k,number);

       cout<<endl<<"Минимальноесуммарноерасстояние: "<<min_L(mass_L,k,number)<<endl<<endl;

       cout<<"Кратчайшийпуть: "<<endl;

       vivod_T(O);

       vivod_T(mass_T1[number]);

       vivod_T(mass_T2[number]);

       vivod_T(mass_T3[number]);

       vivod_T(mass_T4[number]);

       vivod_T(mass_T5[number]);

       vivod_T(mass_T6[number]);

       vivod_T(O);

       delete []mass_L;

       delete []mass_T1;

       delete []mass_T2;

       delete []mass_T3;

       delete []mass_T4;

       delete []mass_T5;

       delete []mass_T6;

       system("pause");

       return 0;

}

voidvvod(Koord *A)

{

             for(int j=0;j<max_len;j++)

              {

                    cout<<"Пункт № "<<j+1<<endl;

                    cout<<"Координатах: ";

                    cin>>A[j].x;

                    cout<<"Координата у: ";

                    cin>>A[j].y;

             }

}

voidvivod(Koord *A)

{

       for(int j=0;j<max_len;j++)

             {

                    cout<<"Пункт № "<<j+1<<endl;

                    cout<<"Координатах: "<<A[j].x<<endl;

                    cout<<"Координата y: "<<A[j].y<<endl;

             }           

}

voidvivod_T(Koord T)

{

             cout<<"("<<T.x<<","<<T.y<<")"<<endl;

}

doublerasst(Koord t1, Koord t2) // double x1,double y1,double x2,double y2

{

       double L=sqrt(pow((t2.x-t1.x),2)+pow((t2.y-t1.y),2));

       return L;

}

double min_L(double *L, int max, int number)

{

       double min=L[0];

       for(inti=1;i<max;i++)  

             if(L[i]<min)

             {

                    min=L[i];

                    number=i;

             }

       return min;

}

int factorial(int n)

{

       int f=1;

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

             f=f*i;

       return f;

}Результат:

Построение кратчайшего пути: