문제링크 입니다

[TSP2] 문제 😊😊😊😊😊

NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 정확히 한 번씩 방문하는 가장 짧은 경로를 찾는 문제이다. 이 문제를 다항 시간에 해결할 수 있는 방법은 현재까지는 존재하지 않지만, 도시의 숫자가 작은 경우에는 비교적 사용 가능한 시간 안에 문제를 해결할 수 있다.

AOJ 에서 이 문제는 같은 내용을 가진 문제 여러 개로 구성된다. 문제 번호에 비례해 도시의 개수가 올라가므로, 뒤로 갈수록 더욱 효율적인 방법을 써야 해결할 수 있다.

도시의 수 N <= 15 라고 할 때, 여행하는 외판원 문제를 해결하는 프로그램을 작성하라.

[풀이]

일반적인 DP단원에서 배웠던 메모이제이션 기법을 이용하여 shortestPath2(지금위치, 방문했던 곳) 을 구현하여 문제를 해결하였습니다.
특별한 점은 15개의 방문하는 visited를 비트값을 이용하여 연산해 처리 속도를 증가시켰습니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 이 주어진다. 각 테스트 케이스의 첫 줄에는 도시의 수 N (3 <= N <= 15) 이 주어진다. 그 후 N 줄에, 각 N 개씩의 실수로 도시간의 거리가 주어진다. 도시들은 1 부터 N 까지의 숫자로 표현되며, i 번째 줄의 j 번째 실수는 i번째 도시와 j번째 도시 사이의 거리이다. 각 거리는 0 이상 1415 이하이고, 소수점 밑 열 자리까지 주어진다.

주어진 행렬은 대칭이며, 입력되는 거리들은 삼각 부등식 (triangle inequality) 을 만족한다고 가정해도 좋다.

출력

테스트 케이스마다 한 줄에 최소 경로의 길이를 소수점 밑 열 자리까지 출력한다. 1e-7 이하의 절대/상대 오차가 있어도 맞는 답으로 인정한다.

입력 예제

2
3
0.0000000000  611.6157225201  648.7500617289
611.6157225201  0.0000000000  743.8557967501
648.7500617289  743.8557967501  0.0000000000
4
0.0000000000  326.0008994586  503.1066076077  290.0250922998
326.0008994586  0.0000000000  225.1785728436  395.4019367384
503.1066076077  225.1785728436  0.0000000000  620.3945520632
290.0250922998  395.4019367384  620.3945520632  0.0000000000

출력 예제

1260.3657842490
841.2045646020

전체 코드는 다음과 같습니다.

//
//  TSP2.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/10/27.
//

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("TSP.txt");

const int MAX = 15;
const double INF = 1e200;
double cache[MAX][1<<MAX];
int N;
double dist[MAX][MAX];
// here: 현재 위치
// visited: 각 도시의 방문 여부
// here 에서 시작해 남은 도시들을 방문할 수 있는 최단 경로의 길이를 반환한다.
// 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다
double shortestPath2(int here, int visited) {
// 기저 사례: 모든 도시를 다 방문했을 때는 0번 도시로 돌아가고 종료한다
    if(visited == (1<<N)-1) return 0;
    // 메모이제이션
    double& ret = cache[here][visited];
    if(ret > 0) return ret;

    ret = INF; // 매우 큰 값으로 초기화

    // 다음 방문할 도시를 전부 시도해 본다
    for(int next = 0; next < N; ++next) {
        // 이미 방문한 도시인 경우
        if(visited & (1<<next)) continue;
        double cand = dist[here][next] + shortestPath2(next, visited + (1<<next));
        ret = min(ret, cand);
    }
    return ret;
}

void initialize(){
    for(int i=0 ; i<MAX; i++){
        for(int j=0; j<(1<<MAX); j++){
            cache[i][j] = -1.0;
        }
    }
}
int main(){

     int test_case = 0;
     fin >> test_case;
     for(int test=0; test<test_case; test++){
         fin >> N;
         for(int i=0; i<N; i++){
             for(int j=0; j<N; j++){
                 fin >> dist[i][j];
             }
         }
         initialize(); // 캐시초기화

         cout.setf(ios::fixed, ios::floatfield);
         double result= INF;
         for(int i=0; i<N; i++){
             result = min(result, shortestPath2(i,(1<<i)));
         }
         cout.precision(10); // 소숫점 아래 열번째까지.
         cout << result << endl;
     }
     return 0;
 }

TSP2

Comments