TSP - DFS

#include <iostream>

#include <cmath>

#include <time.h>

#include <windows.h>

using namespace std;

#define MAX 150

typedef struct Vertex* Vertex_Pointer;

int Top = -1;

struct Vertex

{

double x, y;

double distance;

int dept;

int check[10];

Vertex_Pointer link;

};

Vertex_Pointer Stack[MAX];

void Stack_push(Vertex_Pointer input)

{

if(Top == MAX - 1){

cout<<"스택이 가득찼습니다.\n"<<endl;

return;

}

Stack[++Top] = input;

}

Vertex_Pointer Stack_pop()

{

if(Top < 0){

cout<<"스택이 비었습니다.\n"<<endl;

exit(0);

}

return Stack[Top--];

}

Vertex_Pointer vertex_Create(Vertex, int index);

Vertex_Pointer vertex_Create();

Vertex_Pointer vertex_copy(Vertex_Pointer);

void print_path(Vertex_Pointer);

void travel(Vertex_Pointer, Vertex_Pointer);

Vertex P[10] = {{2,8}, {4,5}, {7,3}, {11,17}, {5,13}, {12,7}, {1,6}, {7,2}, {11,3}, {13,6}};

double compare = 999;

Vertex_Pointer result;

float during_t;

LARGE_INTEGER frequency, start_t, finish_t;

void main()

{ 

Vertex_Pointer ptr,tmp;

Stack_push(vertex_Create(P[0],0));

srand(time(NULL));

    QueryPerformanceFrequency( &frequency );

QueryPerformanceCounter( &start_t );

while(Top > -1)

{

ptr = Stack_pop();

tmp = vertex_copy(ptr);

travel(ptr, tmp);

}

QueryPerformanceCounter( &finish_t );  // get finish time..

cout<<"최단 경로 : "<<P[0].x<<", "<<P[0].y;

print_path(result);

cout<<" - > "<<P[0].x<<", "<<P[0].y;

cout<<" 최단 거리 : "<<compare<<endl;

during_t = ( (float)finish_t.QuadPart - (float)start_t.QuadPart ) / (float)frequency.QuadPart * (float)1000.0;

if( during_t < 1000.) // print millisecond

        printf("* During Time .. %.4f(msec)\n", during_t);

    else if( during_t/1000. < 60.) // print second

        printf("* During Time .. %.1f(sec)\n", during_t/1000);

    else if( during_t/60000. < 60.) // print min

        printf("* During Time .. %.0f(min)\n", during_t/60000.);

    else  //print hour

        printf("* During Time .. %.0f(hour)\n", during_t/3600000.);

return;

}

void travel(Vertex_Pointer pp, Vertex_Pointer bkup)

{

for(int i = 0; i < 10; i++)

{

if(pp->check[i] == false)

{

pp->check[i] = true;

pp->x = P[i].x; 

pp->y = P[i].y;

pp->dept++;

pp->distance += sqrt(pow(pp->x - bkup->x,2) + pow(pp->y - bkup->y, 2));

pp->link = bkup;

Stack_push(pp);

if(pp->dept == 10)

{

if(compare > pp->distance + sqrt(pow(pp->x - P[0].x,2) + pow(pp->y - P[0].y, 2)))

{ 

compare = pp->distance + sqrt(pow(pp->x - P[0].x,2) + pow(pp->y - P[0].y, 2));

result = vertex_copy(pp);

cout<<"최단 경로 : "<<P[0].x<<", "<<P[0].y;

print_path(result);

cout<<" - > "<<P[0].x<<", "<<P[0].y;

cout<<" 최단 거리 : "<<compare<<endl;

}

if(compare <= pp->distance + sqrt(pow(pp->x - P[0].x,2) + pow(pp->y - P[0].y, 2)))

{

result = vertex_copy(pp);

cout<<" 경로 : "<<P[0].x<<", "<<P[0].y;

print_path(result);

cout<<" - > "<<P[0].x<<", "<<P[0].y<<endl;

}

}

}

pp = vertex_copy(bkup);

}

}

Vertex_Pointer vertex_Create(Vertex p, int index)

{

Vertex_Pointer tmp = new struct Vertex;

tmp->x = p.x;

tmp->y = p.y;

tmp->distance = 0;

tmp->link = 0;

tmp->dept = 1;

for(int i = 0 ; i < 10 ; i++)

tmp->check[i] = false;

tmp->check[index] = true;

return tmp;

}

Vertex_Pointer vertex_Create()

{

Vertex_Pointer tmp = new struct Vertex;

tmp->x = 0;

tmp->y = 0;

tmp->distance = 0;

tmp->link;

tmp->dept = 1;

for(int i = 0 ; i < 10 ; i++)

tmp->check[i] = false;

return tmp;

}

Vertex_Pointer vertex_copy(Vertex_Pointer ori)

{

Vertex_Pointer copy = vertex_Create();

copy->x = ori->x;

copy->y = ori->y;

copy->distance = ori->distance;

copy->link = ori->link;

copy->dept = ori->dept;

for(int i = 0 ; i < 10 ; i++)

copy->check[i] = ori->check[i];

return copy;

}

void print_path(Vertex_Pointer ptr)

{

if(ptr->link != NULL)

print_path(ptr->link);

if(ptr->link == NULL) return;

cout<<" -> "<<ptr->x<<", "<<ptr->y;

}