[알고리즘] Traveling Salesperson problem (외판원 문제) - by Dynamic Programming

알고리즘 시간에 가장 많이 예기하는 알고리즘 중에 하나가 이 문제가 아닐까 싶다.

문제는 회사원이 A도시부터 시작하여 모든 도시를 한번씩한 거처서 다시 A도시로 들어오는 방법이다.

그리고 그과정은 최적이어야 한다.

이 문제를 알고리즘을 이해하는것 그다시 어렵지 않다.

하지만 알고리즘을 직접 코드화 하는게 상당히 까다롭다.

많은 사람들이 집합을 어떻게 표현해야되나에 대해 고민한다.

그냥생각하기에는 배열? 정도가 생각나지만 배열로 하기에는 무리가 있다.

여기에서 유한 집합을 표현한다고 한다면 비트로 표현하는게 좋지 않을까 한다.

일단 비트로 표현하는 방법과 비트연산을 알아야 한다

이방법은 인터넷에 많이 나와있다. 비트연산자 혹은 논리연산자라고 검색하면 나온다

그래도 못찾겠다면 http://winapi.co.kr/ 를 뒤지면 나온다.. 

일단 비트와 집합을 어떻게 연관시키는가..

예를 들면 A라는 집합에 v1, v2, v3 라는 게 존재 한다면

A = {v1, v2, v3} 이렇게 표현가능할 것이다.

그리고 A의 부분집합을 표현할때는 공집합, {v1}, {v2}, ..... {v1,v2,v3} 이런게 존재한다.

생각해보자 

상자 3개가있다. 1번 상자는 1번 공만들어가거나 혹은 아무것도 없다.

2번 상자는 2번 공만들어가거나 혹은 아무것도 없다.

3번 상자는 3번 공만들어가거나 혹은 아무것도 없다.

뭔가 보이는가.. 집합 원소의 부분집합을 원소의 있다 or 없다로 표현이 가능하다

예) B = {v2, v3}    => v1 없고, v2있고 v3있다.

이런방식을 bitmap 방식이라 한다. 단순 있다 없다. 단 두가지 정보를 표현할때 컴퓨터에서 0과 1을 사용한다.

0이면 없고 1이면 있고.

그렇다면 이를 다시 bit로 표현하겠다. 

예) B = {v2, v3}    =>  011 or 110  

위에 방법중에 표현하는것은 여러분에 몫이다 011로 표현한것은 첫째자리부터는 v1,v2,v3으로 생각한것이고

110으로 표현한것은 첫째부터를 v3, v2, v1 으로 본것이다.

그럼면 모든것이 끝났다. 

아래는 첫째자리는 Vn부터 마지막자리를 V1로 본것이다.

또한 외판원 문제를 여러가지 방법으로 풀지만 여기에서는 DP(Dynamic Programming) 방법을 사용하였다.

그리고 아래는 전체 소스가 아니며 중요부분만 이해 하면 될것이다.

나머지는 직접 짜보시길...

void travel(int n, int W[VSIZE][VSIZE], int **P, int *minLength )

{

         int i, j, k, cnt;           

         int **D;

         int *setIndex, *findMinimum, *findPath;

         int set, minIndex, max;

         int mask_i=0, mask_j=0;

        

         max = 1 << n;

 

         D = (int**) malloc( sizeof(int*)*n);

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

                  D[i] = (int*)malloc(sizeof(int)*(max) );

        

        

         //A집합이공집합인경우

         printf("A={}\n");

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

         {

                  D[ i ][ 0 ] = W[ i ][ 0 ];

                  printf("--> D[%d][0] = %d\n",i, D[ i ][ 0 ]);

         }

        

 

         for( k = 1; k <= n - 2; k++ ){    //A집합노드뽑는개수

                  setIndex = ( int * ) malloc( sizeof( int ) * ( k + 1 ) );

                  findMinimum = ( int * ) malloc( sizeof( int ) * k );

                  findPath = ( int * ) malloc( sizeof( int ) * k );

                 

                  for( i = 0, set = 0; i <= k; i++ ){

                           setIndex[ i ] = 1 << i;

                           set |= setIndex[ i ];

                  }

                  setIndex[ 0 ] = 0;

                  set ^= 1;

 

                  while( 1 ){

                           printAset(set, n);

                           printf("}\n");

 

                           for( i = 1; i < n; i++ ){ //Vi 에서A집합을거쳐V1로

                                   if( ( set & ( 1 << i ) ) > 0 )  //Vi가V1이거나A집합에속하지않아야함.

                                            continue;

 

                                   for( j = 1, cnt = 0; cnt < k; ++j ) //A집합의조합수

                                   {

                                            if( ( set & ( 1 << j ) ) > 0 ){

                                                     findMinimum[ cnt ] = W[ i ][ j ] + D[ j ][ set ^ ( 1 << j ) ];

                                                     findPath[ cnt ] = j;

                                                     cnt++;

                                            }

                                   }

                                   D[i][ set ] = minimum( findMinimum, cnt, &minIndex );

                                   P[i][ set ] = findPath[ minIndex ];

                                  

                                   printf("--> D[%d][", i+1);

                                   printAset( (set), n);

                                   printf("}] =  %d \n", D[ i ][ set ]);

                           }

                          

                           //mask 를이용해다음집합조합선택

                           if(mask[mask_i][mask_j+1] == 0)

                           {

                                   mask_i++;

                                   mask_j=0;

                                   set = mask[mask_i][mask_j];

                                   break;

                           }else{

                                   mask_j++;

                                   set = mask[mask_i][mask_j];

                           }

                           if(mask[mask_i][mask_j] == 0)

                                   break;

                          

                          

                  }

                  free( setIndex );

                  free( findMinimum );

                  free( findPath );

                  if(mask[mask_i][mask_j] == 0)

                                   break;

         }

 

         //V1 -> A집합(V1을제외한모든노드)으로

         findMinimum = ( int * ) malloc( sizeof( int ) * n );

         findPath = ( int * ) malloc( sizeof( int ) * n );

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

                  set |= 1 << i;

         set ^= 1;

                                                                                                                                                              

         for( i = 1, cnt = 0; cnt < n - 1; ++i )

                  if( ( set & ( 1 << i ) ) > 0 ){

                           findMinimum[ cnt ] = W[ 0 ][ i ] + D[ i ][ set ^ ( 1 << i ) ];

                           findPath[ cnt ] = i;

                           cnt++;

                  }

         D[ 0 ][ set ] = minimum( findMinimum, cnt, &minIndex );

         P[ 0 ][ set ] = findPath[ minIndex ];   

         *minLength = D[ 0 ][ set ];    

 

         printf("--> D[0][");

         printAset( (set), n);

         printf("}] =  %d\n", D[0 ][ set ]);

 

         //메모리해제

         free( findMinimum );

         free( findPath );

         for( i = 0; i < n; i++ ) free( D[ i ] );

                  free( D );

}

※영건이형 감사드려요