[종만북][알고스팟] Traveling Salesman Problem 2(TSP2), 여행하는 외판원 문제 2- 동적계획법(Dynamic Programming, DP) + 비트마스킹(BitMask) + 완전탐색(BruteForce) JAVA

https://www.algospot.com/judge/problem/read/TSP2

algospot.com :: TSP2

코드설명

동적계획법(Dynamic Programming, DP) + 비트마스킹(BitMask) + 완전탐색(BruteForce) 을 활용합니다.

 

TSP1 과는 다르게, N은 15입니다. 그렇기에 시간복잡도는 O(N!)임에 따라, 15! 인데, 이는 엄청나게 큰 숫자입니다.

그러므로, 메모이제이션을 활용합니다.

 

이떄 메모이제이션에, (현재 위치) (지금까지 방문한 위치)의 데이터를 통해 메모이제이션 합니다.

평소에 과거의 데이터를 가지고 있는 (이 문제의 경우 과거의 데이터란 지금까지 방문한 위치를 의미합니다.) 이 문제가 최적 부분 구조가 성립하는것인가? 라는 의문이 있었습니다.

항상, 이전의 데이터를 가지고 있을때에는 최적 부분구조가 성립하기 어렵다라는 생각을 했었는데, 가지고 있는 데이터들을 최소한으로 하여서 최적 부분 구조를 사용할 수 있습니다.

 

이 문제에서 최적 부분 구조가 성립시키려면 아래와 같이 함수를 정의합니다.

shortestPath2(int here, int visited) : here 위치에서 visited 위치들을 모두 방문한 상태일떄의 최소비용을 반환한다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	private static int C, N, W, H;
    private static int[][] arr;
    private static int answer = 0;
    private static double[][] dist;
    private static double[][] cache;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        C = Integer.parseInt(st.nextToken());
        while(C-- > 0){
        	st = new StringTokenizer(br.readLine());
        	N = Integer.parseInt(st.nextToken());
        	dist = new double[N][N];
        	cache = new double[N][1<<N];
        	
        	for(int i=0;i<N;i++) {
        		st = new StringTokenizer(br.readLine());
        		for(int j=0;j<N; j++) {
        			dist[i][j] = Double.parseDouble(st.nextToken());
        		}
        	}

        	double answer = Double.MAX_VALUE;
            //cache는 모든 출발지에서 사용해도 같이 공유가 가능합니다.
        	for (double[] row : cache) {
        		Arrays.fill(row, -1);
        	}
        	for(int i=0;i<N;i++) {
        		answer = Math.min(answer, shortestPath2(i, 1<<i));
        	}
        	System.out.println(String.format("%.10f", answer));
        }
        
    }
    
    private static double shortestPath2(int here, int visited) {
    	if(visited == (1 << (N)) - 1) {
    		return 0;
    	}
    	
    	if(cache[here][visited] >= 0) return cache[here][visited];
    	double ret = Double.MAX_VALUE;
    	for(int next = 0; next < N; next++) {
    		if( (visited & (1 << next)) != 0) {
    			continue;
    		}
    		
    		double cand = dist[here][next] + shortestPath2(next, visited + (1<<next));
    		ret =Math.min(ret, cand);
    	}
    	return cache[here][visited] = ret;
    }
}