TSP 소개 및 예시문제

'Traveling Salesman Problem (TSP)' 문제의 예시

문제 설명:
TSP는 NP-hard 문제로 알려져 있으며, 그 해결책을 찾기 위한 효율적인 알고리즘은 아직 없습니다. 문제는 아래와 같습니다.

주어진 도시들의 목록과 그들 간의 거리에 대한 정보가 있습니다. 여행자가 각 도시를 정확히 한 번 방문한 다음 시작점으로 돌아오는 최단 경로를 찾아야 합니다. 여행자는 한 도시에서 다른 도시로 이동할 때마다 거리에 따른 비용이 발생합니다. 목표는 전체 비용이 최소가 되는 경로를 찾는 것입니다.

입력:

n (2 <= n <= 15): 도시의 수
도시간 거리 행렬 (nxn)

 

출력:

최소 비용 경로의 길이

 

해설: 
TSP 문제는 전역 최적해를 찾기 위해 완전 탐색 알고리즘(예: 백트래킹, 동적 계획법)을 사용할 수 있지만, 이러한 방법은 많은 계산 시간이 필요하다. 따라서 근사 알고리즘(예: 최소 신장 트리 기반 휴리스틱, 유전자 알고리즘)을 사용하여 문제를 풀 수도 있다고 한다. 이러한 접근법은 정확한 해를 찾지 못할 수 있지만, 주어진 시간 제한 내에 근사치를 구할 수 있기에 매우 까다로운 알고리즘 문제라고 한다.

 

적용 알고리즘: 최소신장트리

 

import java.util.Arrays;

public class TSPHeuristic {

    public static void main(String[] args) {
        double[][] distanceMatrix = {
                {0, 10, 15, 20},
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0}
        };

        double result = approximateTSP(distanceMatrix);
        System.out.println("Approximate TSP cost: " + result);
    }

    public static double approximateTSP(double[][] distanceMatrix) {
        int n = distanceMatrix.length;
        boolean[] visited = new boolean[n];
        double totalCost = 0;
        int currentNode = 0;
        visited[currentNode] = true;

        for (int i = 1; i < n; i++) {
            int nextNode = findNearestUnvisitedNode(distanceMatrix[currentNode], visited);
            totalCost += distanceMatrix[currentNode][nextNode];
            currentNode = nextNode;
            visited[currentNode] = true;
        }
        
        // Return to the starting city
        totalCost += distanceMatrix[currentNode][0];
        
        return totalCost;
    }

    public static int findNearestUnvisitedNode(double[] distances, boolean[] visited) {
        int nearestNode = -1;
        double minDistance = Double.MAX_VALUE;

        for (int i = 0; i < distances.length; i++) {
            if (!visited[i] && distances[i] < minDistance) {
                minDistance = distances[i];
                nearestNode = i;
            }
        }

        return nearestNode;
    }
}