보고서

HW #02

(Traveling Salesperson Problem)

과목명 : 알고리즘

제출일 : 07년 10월 8일

학  번 : 20021558

성  명 : 경 규 성

제목 : TSP(외판원문제) 의 구현과 알고리즘 분석

개요 : Traveling Salesperson Probelem을 이해한 후, 아래의 요구사항을 고려하여 구현해본다.

- Path를 출력하는 알고리즘을 개발하여 추가한다.

- 출력결과와 Time Complexity를 분석한다.

- input graph에 대한 최적 tour와 그 길이를 출력한다.

- 연습용 input graph은 그림 3.16과 130쪽 문제5의 그림을 각각 적용한다.

- 다른 graph들도 적용하여 결과를 확인한다.

- vertex 번호는 0부터 n-1까지로 사용한다.

- vertex subset {v2, v0}의 번호는 5 (00101)로 표현하여 이진수로는 포함되는 vertex 번호와

일치하는 bit를 1로 표시하는 방법을 적용해본다.

- Brute Force로도 구현하여 Time Complexity를 비교한다.

기본 알고리즘과 설명 :

::알고리즘 3.11:: Dynamic Approach

입력 : 가중치포함 방향그래프, n(정점의 개수). 그래프는 행과 열의 인덱스의 범위가 모두 1부터 n까지인 2차원 배열 W로 표현한다. 여기서 W[i][j]는 I번째 정점에서 J번째 정점을 연결하는 이음선의 가중치이다.

출력 : 변수 minlength (최단거리), 2차원 배열 P (경로저장), P의 행은 인덱스 범위가 1부터 n까지이고, 열은 인덱스 범위가 V-{v1} 의 모든 부분집합이 된다. P[i][A]는 A에 속한 모든 정점을 정확히 한 번만 거쳐서 vi에서 v1로 가는 최단경로에서 vi다음에 오는 첫 번째 정점의 인덱스이다.

void travel (int n, const number W[][], index P[][], number& minlength) {

index i, j, k;

number D[1..n][subset of V-{v1}];

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

D[i][Æ] = W[i][1];

for(k=1; k<= n-2; k++)

for(all subsets AÍV-{v1} containing k vertices)

for(i such that i¹1 and vi is not in A){

D[i][A] = min(j:vjÎA)(W[i][j]+D[j][A-{vj}]);

P[i][A] = value of j that gave the minimum;

}

D[1][V-{v1}] = min(2£j£n)(W[1][j]+D[j][A-{v1,vj}]);

P[1][V-{v1}] = value of j that gave the minimum;

minlength = D[1][V-{v1}]

}

교과서 그림 3.16의 그래프로 알고리즘을 분석해보면,

V = { v0, v1, v2, v3 } 이고 모든 정점의 집합을 말한다.

A = V의 모든 부분집합.

D[Vi][A] = A에 속한 정점을 각각 한 번씩만 거쳐서 Vi에서 V1으로 가는 최단경로 길이.

가중치 그래프를 행렬로 옴기면 다음과 같다.

int W[4][4] = {

{             0,           2,             9,     INFINITY},

{             1,           0,             6,             4},

{     INFINITY,           7,             0,             8},

{             6,           3,     INFINITY,             0}     };

알고리즘을 이용해 행렬 W에서 D를 채워간다.

어느 정점도 거쳐가지 않고 갈 때 경우,

D[v1][0] = W[0][1] = 1

D[v2][0] = W[0][2] = INFINITY

D[v3][0] = W[0][3] = 6

k = 1 하나만 거쳐서 갈 때,

D[v1][v2] = min( W[1][j] + D[vj][{v2} - {vj}] ) = W[1][2] + D[v2][0] = 6 + INFINITY

D[v1][v3] = min( W[1][j] + D[vj][{v3} - {vj}] ) = W[1][3] + D[v3][0] = 4 + 6 = 10

D[v2][v1] = min( W[2][j] + D[vj][{v1} - {vj}] ) = W[2][1] + D[v1][0] = 7 + 1 = 8

D[v2][v3] = min( W[2][j] + D[vj][{v3} - {vj}] ) = W[2][3] + D[v3][0] = 8 + 6 = 14

D[v3][v1] = min( W[3][j] + D[vj][{v1} - {vj}] ) = W[3][1] + D[v1][0] = 3 + 1 = 4

D[v3][v2] = min( W[3][j] + D[vj][{v2} - {vj}] ) = W[3][2] + D[v2][0] = INFINITY + INFINITY

k = 2 두개 거쳐 갈 때 ,

D[v1][{v2, v3}] = min( W[1][j] + D[vj][{v2, v3} - {vj}] )

= min( W[1][2] + D[v2][{v3}], W[1][3] + D[v3][{v2}] )

= min( 6 + 14, 4 + INFINITY) = 20

D[v2][{v1, v3}] = min( W[2][j] + D[vj][{v1, v3} - {vj}] )

= min( W[2][1] + D[v1][{v3}], W[2][3] + D[v3][{v1}] )

= min( 7 + 10, 8 + 4) = 12

D[v3][{v1, v2}] = min( W[3][j] + D[vj][{v1, v2} - {vj}] )

= min( W[3][1] + D[v1][{v2}], W[3][2] + D[v2][{v1}] )

= min( 3 + INFINITY, INFINITY + 8 ) = INFINITY

k = 3 (n-2) 세 개 거쳐 갈 때,

D[v0][{v1, v2, v3}] = min( W[0][j] + D[vj][{v1, v2, v3} - {vj}] )

= min( W[0][1] + D[v1][{v2, v3}],

W[0][2] + D[v2][{v1, v3}],

W[0][3] + D[v3][{v1, v2}] )

= min( 2 + 20, 9 + 12, INFINITY + INFINITY ) = 21

따라서 최단경로는 v0, v2, v3, v1, v0 이고 21이다.

구현의 핵심인 부분집합을 어떻게 나타낼 것인지 생각해보자

예를 들어보면 그림 3.16에서

V = { v0, v1, v2, v3 } 는

1, 0001 은 v0

2, 0010 은 v1

4, 0100 은 v2

8, 1000 은 v3

V - {v0} 은 1110로 나타낼 수 있다. {v0, v2} 은 0101 이고 {v1, v3}은 1010이 될 것이다.

책에선 다음과 같이 나타내지만 01 0001 {v1} 02 0010 {v2} 03 0011 {v1, v2} 04 0100 {v3} 05 0101 {v1, v3} 06 0110 {v2, v3} 07 0111 {v1, v2, v3} 08 1000 {v4} 09 1001 {v1, v4} 10 1010 {v2, v4} 11 1011 {v1, v2, v4} 12 1100 {v3, v4} 13 1101 {v1, v3, v4} 14 1110 {v2, v3, v4} 15 1111 {v1, v2, v3, v4}	행렬을 이용을 위해 0001을 v0으로 시작한다. 01 0001 {v0} 02 0010 {v1} 03 0011 {v0, v1} 04 0100 {v2} 05 0101 {v0, v2} 06 0110 {v1, v2} 07 0111 {v0, v1, v2} 08 1000 {v3} 09 1001 {v0, v3} 10 1010 {v1, v3} 11 1011 {v0, v1, v3} 12 1100 {v2, v3} 13 1101 {v0, v2, v3} 14 1110 {v1, v2, v3} 15 1111 {v0, v1, v2, v3}

실행 후 배열 D의 내용은 아래와 같이 될 것이다. (99는 INFINITY)

n = 4

D = [i][pow(2,n)-1]

00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 21, 00

01, 00, 00, 00, 99, 00, 00, 00, 10, 00, 00, 00, 20, 00, 00, 00

99, 00, 08, 00, 00, 00, 00, 00, 14, 00, 12, 00, 00, 00, 00, 00

06, 00, 04, 99, 00, 99, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00

이런 식으로 D의 값들이 들어가 이용된다.

경로저장과 출력

경로를 저장하기 위해 P[][]라는 구조체 배열을 썼다. 부분집합을 검사하는 부분에서 지금 거쳐가는 노드와 바로 전에 거쳐갔던 노드를 now와 next에 저장해 마지막 D[0][V-v0]에 해당하는 P[0][V-v0]에서 P[0][V-v0].next를 계속 이어서 출력하면 된다. 출력화면은 뒷부분에 시간복잡도 분석 때 나온다.

while( s < sub  ){ //부분집합 모두

//s가 k개의 node이고, Vi 미포함, V0 미포함

if((bitc(s, MAX_Node) == k) && !(s & Sq2(i)) && !(s & 1) ){

//n비트만큼 시프트하면서 해당 부분집합 검사

for(int a=0; a<MAX_Node; a++){

if(s & one){

temp = (W7[i][J(one)] + D[J(one)][ s^one ]);

if(temp >= INF)

temp = INF;

if(temp <= min){

min = temp;

P[i][s].now = J(one); // 지금 노드

P[i][s].next = s^one; // 이전 노드

}

}

one = one << 1;

}

D[i][s] = min;

}

s++;

}

::막무가내 알고리즘:: Brute Force Approach

입력 : 자신을 입력으로 받는 재귀함수이다. 외부 선언된 배열 W는  가중치포함 방향그래프, D는 최단경로를 구하기 위해 이용할 배열이다. MAX_Node는 정점의 개수, 초기값 d는 부분집합의 개수, 초기값 w는 시작 노드이다.

출력 : 변수 minimum 최단거리이고, 2차원 배열 tour[][]는 경로를 저장할 배열이다.

int tspBF(int w, int d){

//처음 W[w][0]으로

if (d == 0) {

tour[w][d]=w; // 최종 경로

return (W7[w-1][0]);

}

//무한대로 초기화

int minimum = INFINITY;

//MAX_Node 갯수만큼 돌면서

for (int i = 1; i<=MAX_Node; i++) {

// 2^i 즉 i에 해당하는 부분집합은 모두

if (subsets A containing Vi vertices) {

//minimum(W[w][i] + D[Vi][V-vi]) --> minimum(W[w][i] + tspBF(i, V-vi))

minimum = min(minimum, W7[w-1][i] + tspBF(W[i][j]+D[j][A-{vj}]));

// minimum 값이 무한대가 아니고, 더할 W[i][j]값이 무한대가 아니면

if((minimum < INFINITY) && (W7[w-1][i] < INFINITY)){

//경로배열에 추가한다.

tour[w-1][d-1]=i;

}

}

}

return minimum;

}

알고리즘의 원리는 비슷하지만 bottom up 구조라, 필요없는 중복계산을 많이 한다. 재귀함수라 예를 들어 설명하기엔 무리가 있다. 원리는 단순히 입력 값에 대해 모든 경우에 대해서 따로 bottom에서부터 연산한 값을 top으로 올라오면서 합쳐간다는 원리다.

좌측의 사진은 경로를 저장하고 있는 과정을 변수들의 내용과 함께 출력한 화면이다. 눈으로 보아서는 어떤 패턴으로 실행되는지 알 수 없다. 호출된 각각의 재귀함수들이 bottom까지 내려갔다 올라오면서 중복되어 실행이 되기 때문에 과정을 출력하면 뒤죽박죽이다.

경로저장과 출력

함수의 의사코드는 다음과 같다.

void show_path (int 시작노드, int 총 부분집합 갯수){

if(부분집합의 갯수>=0){

cout<<"-> v"<<tour[노드][부분집합 개수]; // 경로에 해당하는 노드출력

print_node(tour[노드][부분집합 개수], 부분집합의 개수 - (tour[노드][부분집합 개수]));

}

}

W[i][j], Tour[i][s] 에 중점을 두고 130쪽 연습문제의 그래프를 예로 들고 설명하면, 출력 할 경로를 따라가는 방법은 다음과 같다. Tour에 저장된 건 다음 경로의 i값이고, 63 - 2^4 = 47 이다. 여기서 4는 s-2 즉 6-4이다.

W[1][6] = 10, m = 51, Tour[1][63] = 6   -> Tour 배열의 처음 이곳부터 시작한다.

Tour배열에는 다음 경로의 I값이 저장되어있다.  63 - 2^4 = [47]

W[6][7] = 10, m = 41, Tour[4][47] = 7

47 - 2^5 = 15

W[7][4] =  8, m = 31, Tour[7][15] = 4

15 - 2^2 = 11

W[4][5] =  2, m = 23, Tour[4][11] = 5

11 - 2^3 = 3

W[5][3] = 12, m = 21, Tour[5][3]  = 3

3 - 2^1 = 1

W[3][2] =  6, m =  9, Tour[3][1]  = 2

1 - 2^0 = 0

이런 식으로 다음 경로를 찾아간다.

130쪽 연습문제의 그래프를 예로 들고, 위의 경로출력 알고리즘을 적용하면 아래와 순서로 출력된다.

주요 출력들과 설명 :

우선 input graph에 대한 최적 tour와 그 길이를 출력한다.

연습문제 5번의 그래프를 이용하여 만든 프로그램을 실행한 화면

노드가 4개일 때와 7개일 때를 실행하였고, 두 알고리즘을 1000번 반복하여 실행 시간차를 비교하였다.

아래는 brute force와 dynamic TSP 알고리즘의 실행시간을 비교한 화면이다.

BF(brute force)와 DY(dynamic) 알고리즘의 n번 실행에 따른 시간비교 (단위 : 초)

(Processor : Dual 2 core 1.87Ghz*2, Memory : 2Gbyte(DDR6400) , OS : XP , TOOL : VS 2005)

아래는 위 화면을 그래프로 그려 시간복잡도를 비교한 그래프이다.

BF(brute force)와 DY(dynamic) 알고리즘의 n번 실행에 따른 시간 그래프

부록. 소스원본

#include <iostream>

#include <cmath>

#include <windows.h>

using namespace std;

#define INF 90000

#define N2N (int)pow(2.0,MAX_Node)

#define MAX_Node 7

LARGE_INTEGER Timefeq, Beg1, End1, Beg2, End2;

int TSPBFway;

int TSPway;

// 그림 3.16

int W4[4][4] = {

{ 0, 2, 9, INF},

{ 1, 0, 6, 4},

{ INF, 7, 0, 8},

{ 6, 3, INF, 0} };

// 연습문제 5

int W7[7][7] = {

{	0,	4, INF,  INF, INF,  10, INF},

{	3,	0, INF,   18, INF, INF, INF},

{ INF,	6,	0,  INF, INF, INF, INF},

{ INF,	5,  15,    0,   2,  19,   5},

{ INF, INF, 12,	1,   0, INF, INF},

{ INF, INF, INF, INF,   2,   0,  10},

{ INF, INF, INF,   8, INF, INF,   0} };

typedef struct vertex {

int now;

int next;

}node;

int tour[7][64];	//BF7

node P[7][128];	//Dynamic7

//몇개의 노드를 포함하는지?

int bitc(int s, int n){

int count=0;

int one = 1;

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

if(s & one)

count++;

one = one << 1;

}

return count;

}

int J(int s){

int an = (int)(log10((double)s)/log10(2.0));

if(an<=0)

return 0;

else

return an;

}

int Sq2(int i){

return (int)pow(2.0, i);

}

void TSP_Dynamic4(int n){

int i, k, s;

int sub = (int)pow(2.0,n);

node P[4][16];

int D[4][16];

/*

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

for(int i=0; i<Sq2(n); i++){

W[i] = new int[n];

}

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

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

W[i][j] = Arr[i*n+j];

cout.width(8);

cout << W[i][j];

}

cout <<endl;

}

node** P = new node*[n];

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

P[i] = new node[n];

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

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

D[i] = new int[n];

*/

//int* P = new int[n-1]; // 경로저장

/*W 출력해보기

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

for(s=0; s<n; s++){

cout << W[i][s] << ' ';

}

cout << endl;

}

*/

//////  D, P 초기화   /////////////////

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

for(s=0; s<Sq2(n); s++)

D[i][s] = 0;

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

for(s=0; s<Sq2(n); s++){

P[i][s].now = 0;

P[i][s].next = 0;

//cout << P[i][s] << ' ';

}

//cout << endl;

}

///////////////////////////////////////

//아무것도 거쳐가지 않을때

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

D[i][0] = W4[i][0];

//cout << D[i][0] << " =? ";

//cout << D[i][22] <<"\n";

}

/////////////////////////////////////////////////

for(k=1; k< n-1; k++){ // 거쳐가는 node 수

//cout << k << "개를 거칠때"<< endl;

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

s=2;

while( s < sub  ){//부분집합 모두

int one = 1;

int temp = INF;

int min = INF*3;

//s가 k개의 node이고, Vi 미포함, V0 미포함

if((bitc(s, n) == k) && !(s & Sq2(i)) && !(s & 1) ){

//n비트만큼 시프트하면서 해당 부분집합 검사

for(int a=0; a<n; a++){

if(s & one){

temp = (W4[i][J(one)] + D[J(one)][ s^one ]);

if(temp >= INF)

temp = INF;

if(temp <= min){

min = temp;

P[i][s].now = J(one); //거쳐갈 노드

P[i][s].next = s^one;

}

}

one = one << 1;

}

D[i][s] = min;

}

s++;

}

}

}

// D[0][V-{v0}]

s = Sq2(n)-2;

int one = 1;

int temp = INF;

int min = INF*3;

for(int a=0; a<n; a++){

if(s & one){

temp = (W4[0][J(one)] + D[J(one)][ s^one ]);

if(temp < min){

min = temp;

P[0][Sq2(n)-2].now = J(one); // 최초경로

P[0][Sq2(n)-2].next = s^one;

//cout << "PATH P[0] = "<<J(one) << endl;

}

}

one = one << 1;

}

D[0][Sq2(n)-2] = min;

cout << "#Node가 "<<n<<"개일 때 최적경로 : "<<min << endl;

// P 출력해보기

int p = 0;

int q = Sq2(n)-2;

int temp1, temp2;

cout << "V1 -> ";

for(i=0; i<=n-2; i++){

cout << "V"<< P[p][q].now + 1<< " -> ";

temp1 = P[p][q].now;

temp2 = P[p][q].next;

p = temp1;

q = temp2;

}

cout << "V1" << endl<<endl;

}

void TSP_Dynamic7(double* tDY){

int i, k, s;

int sub = (int)pow(2.0,MAX_Node);

int D[7][128];

/*W 출력해보기

for(int i=0; i<MAX_Node; i++){

for(s=0; s<MAX_Node; s++){

cout << W7[i][s] << ' ';

}

cout << endl;

}

*/

//////  D, P 초기화   /////////////////

for(i=0; i<MAX_Node; i++){

for(s=0; s<Sq2(MAX_Node); s++){

D[i][s] = 0;

//cout << D[i][s] << ' ';

}

}

for(i=0; i<MAX_Node; i++){

for(s=0; s<Sq2(MAX_Node); s++){

P[i][s].now = 0;

P[i][s].next = 0;

//cout << P[i][s] << ' ';

}

//cout << endl;

}

///////////////////////////////////////

// 시간측정 /////////////

QueryPerformanceCounter(&Beg1); // start clock tick

//////////////////////////////

//아무것도 거쳐가지 않을 때

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

D[i][0] = W7[i][0];

for(k=1; k< MAX_Node-1; k++){ // 거쳐가는 node 수

//cout << k << "개를 거칠때"<< endl;

for(i=1; i<MAX_Node; i++){

s=2;

while( s < sub  ){//부분집합 모두

int one = 1;

int temp = INF;

int min = INF*3;

//s가 k개의 node이고, Vi 미포함, V0 미포함

if((bitc(s, MAX_Node) == k) && !(s & Sq2(i)) && !(s & 1) ){

//n비트만큼 시프트하면서 해당 부분집합 검사

for(int a=0; a<MAX_Node; a++){

if(s & one){

temp = (W7[i][J(one)] + D[J(one)][ s^one ]);

if(temp >= INF)

temp = INF;

if(temp <= min){

min = temp;

P[i][s].now = J(one); //거쳐갈 노드

P[i][s].next = s^one;

}

}

one = one << 1;

}

D[i][s] = min;

}

s++;

}

}

}

s = Sq2(MAX_Node)-2;

int one = 1;

int temp = INF;

int min = INF*3;

for(int a=0; a<MAX_Node; a++){

if(s & one){

temp = (W7[0][J(one)] + D[J(one)][ s^one ]);

if(temp < min){

min = temp;

P[0][Sq2(MAX_Node)-2].now = J(one); // 최초경로

P[0][Sq2(MAX_Node)-2].next = s^one;

//cout << "PATH P[0] = "<<J(one) << endl;

}

}

one = one << 1;

}

D[0][Sq2(MAX_Node)-2] = min;

TSPway = min;

QueryPerformanceCounter(&End1); // end clock tick

*tDY += (double)(End1.QuadPart-Beg1.QuadPart)/Timefeq.QuadPart;

// (end cpu clock tick - start cpu click tick) / CPU hz

///////////////////////////////////////////////////////////////////////////////////

/*

cout<<"\nDynamic_TSP 최적경로 = "<<min << endl;

// P 출력해보기

int p = 0;

int q = Sq2(MAX_Node)-2;

int temp1, temp2;

cout << "V1 -> ";

for(i=0; i<=MAX_Node-2; i++){

cout << "V"<< P[p][q].now + 1<< " -> ";

temp1 = P[p][q].now;

temp2 = P[p][q].next;

p = temp1;

q = temp2;

}

cout << "V1" << endl<<endl;

*/

}

void TSP7_Show_ROOT(){

cout<<"\n\nDynamic_TSP 최적경로 = "<<TSPway << endl;

// P 출력해보기

int p = 0;

int q = Sq2(MAX_Node)-2;

int temp1, temp2;

cout << "V1 -> ";

for(int i=0; i<=MAX_Node-2; i++){

cout << "V"<< P[p][q].now + 1<< " -> ";

temp1 = P[p][q].now;

temp2 = P[p][q].next;

p = temp1;

q = temp2;

}

cout << "V1" << endl<<endl;

}

void print_node (int i, int a){

if(a>=0){

cout<<" -> V"<<tour[i][a]+1;

print_node(tour[i][a],a-((int)pow(2.0,(tour[i][a]-1))));

}

}//print_node..

int tspBF(int w, int d){

//처음 W[w][0]으로 시작

if (d == 0) {

tour[w][d]=w;

return (W7[w-1][0]);

}

//무한대로 초기화

int minimum = INF;

//MAX_Node 갯수만큼 돌면서

for (int i = 1; i<=MAX_Node; i++) {

if ((d & (int)(pow(2.0,i-1))) == (int)(pow(2.0,i-1))) {

minimum

= min(minimum, W7[w-1][i] + tspBF(i+1 , d^((int)pow(2.0,i-1))));

// minimum 값이 무한대가 아니고, 더할 W[i][j]값이 무한대가 아니면

if((minimum < INF) && (W7[w-1][i] < INF)){

//경로배열에 추가한다.

tour[w-1][d-1]=i;

}

}

}

return minimum;

}

void TSP_BF7(double* tBF){

for(int r=0; r<MAX_Node; r++)

for(int e=0; e<N2N; e++)

tour[r][e]=0;

//////////////////////////////

//   시간측정      ///////////

/////////////////////////////

QueryPerformanceCounter(&Beg2); // start clock tick

int temp = tspBF(1, ((int)pow(2.0,MAX_Node-1)-1));

TSPBFway = temp;

QueryPerformanceCounter(&End2); // end clock tick

*tBF += (double)(End2.QuadPart-Beg2.QuadPart)/Timefeq.QuadPart;	// (end cpu clock tick - start cpu click tick) / CPU hz

/////////////////////////////////////

}

void TSP_BF7_Show_ROOT(){

cout<<"\nBrute Force_TSP 최적경로 = "<<TSPBFway << endl;

cout<<"V1";

print_node (0, ((int)pow(2.0,MAX_Node-1))-2);

cout<<" -> V1";

}

int main(void){

QueryPerformanceFrequency(&Timefeq);

// CPU ClockTick/second = hz

double tDY=0, tBF=0; //runtime value

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

TSP_BF7(&tBF);	//Brute Force

TSP_Dynamic7(&tDY);	//Dynamic

}

// 최적 거리와 경로 보여주기

TSP_BF7_Show_ROOT();	//Brute Force 결과

TSP7_Show_ROOT();	//Dynamic 결과

//노드가 4개일때 Dynamic TSP

TSP_Dynamic4(4);

// Show runtime gap

cout << "\n-------" <<endl;

cout << "--- Brute Force와 Dynamic의 TSP알고리즘 시간차

(1000회반복) --- "<< endl;

cout << "BT_TSP - Dynamic_TSP = ";

cout.precision(16);

cout << tBF-tDY << "second"<<endl;

/*

unsigned long i, n;

for(i=10; i<9000000000; i<<=1){

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

TSP_BF7(&tBF);	//Brute Force

TSP_Dynamic7(&tDY);	//Dynamic

}

cout <<"BF n : "<< n << ", Btime : " << tBF << "\t";

cout <<"DY n : "<< n << ", Dtime : " << tDY << endl;

}

cout << endl << endl;

for(int j=0; j<100000; j+=10000){

for(int n=0; n<=j; n+=1000){

cout.width(10);

}

cout << endl;

}

*/

return 0;

}