[Algorithm] TSP 알고리즘(해밀턴 경로 방문 판매원 문제) Node.js

그래프 이론상에서 해밀턴 경로란 모든 꼭짓점을 한번씩 지나는 경로를 의미합니다. 

해밀턴 순환은 해밀턴 경로인 순환을 의미합니다.

해밀턴 경로를 가지는 그래프는 해밀턴 그래프 혹은 자취 존재 그래프(Traceable Graph)입니다.

 

 

 

NP hard란 무엇인가?

 

NP-hard는 Nondetermisitic Polynomial - Hard를 의미합니다. 비결정적 다항식으로 답을 도출해내기 난해한 문제를 의미합니다. 

예를 들어 다음과 같은 문제가 주어지면 x 값은 12라는 것을 도출해낼 수 있습니다. 변수를 정의할 상수가 충분히 존재하기 때문입니다.

x - 10 = 2

 

NP-hard의 대표적인 문제가 TSP(Traveling Saleman Problem)입니다. 어떤 출발점에서 해밀턴 경로를 충족하면서 최단거리를 구하는 문제입니다. 이 문제에서 어떤 도시를 먼저 방문하는 것이 가장 최단 거리를 뽑아낼 수 있는지에 대한 방정식을 세울 수 없습니다. 정확히 말하면 TSP를 방정식으로 만드는 수학적인 증명이 아직 등장하지 않았습니다.

 

 

NP-hard 문제를 해결하는 방법은 근사 알고리즘, 완전탐색 알고리즘으로 해결해야 합니다. 즉, 모든 값을 일일이 대입해보고 최적의 문제를 해결해야 합니다. 여기서 시간복잡도와 공간복잡도를 최적으로 구하는 알고리즘이 아직 등장하지 않았습니다.

 

 

TSP 알고리즘 문제

 

TSP(Traveling Salesman Problem)은 도시의 좌표값이 2차원 배열로 주어집니다. 모든 도시들을 한번만 방문하되 모든 도시를 방문하는데 걸리는 최단거리를 구해야 합니다. 

 

입력

• 배열을 요소로 가지는 배열 places가 주어집니다.
• places[i]는 number 타입으로 구성된 배열입니다.
• places[i].length = 2
• places[i][0]은 x좌표를, places[i][1]은 y좌표를 의미합니다.

출력

• number 타입의 최단거리를 반환합니다.

주의사항

• Salesman이 방문하는 도시의 출발점과 도착점은 정해져 있지 않습니다. 

입출력 예시

const placesToVisit = [
  [0, 0],
  [3, 3],
  [-3, 3],
  [2, 3],
  [1, 3],
];
output = TSP(placesToVisit);
console.log(output); // --> 940
// 방문 순서: [-3, 3], [1, 3], [2, 3], [3, 3], [0, 0]

 

TSP 알고리즘 풀이

 

예를 들어 [1,2,3,4] 4개의 도시가 존재하고, 1번 도시를 출발점으로 지정한다고 해봅시다. 

도시가 4개고 출발점 1개가 지정되니 최단거리를 구하는 경우의 수는 3의 팩토리얼 값만큼 해밀턴 경로가 존재하게 됩니다.

먼저 도시 1에서 도시 2로 가는 경우의 수는 2가지 입니다.

 

도시 1에서 도시 4로 가는 경우의 수는 2가지 입니다.

 

 

\

도시 1에서 도시 3으로 가는 경우의 수는 2가지 입니다.

 

한 도시를 방문하고 이동거리를 모두 더한 후 최소값과 비교를 해서 스왑을 진행해야 합니다. 모든 도시를 방문해야 하므로, 다음에 방문할 도시를 결정하기 위해 백트래킹 순회를 진행합니다.

출발점이 지정되어 있지 않으므로, 좌표값으로 구성된 배열 places길이만큼 백트래킹 순회가 이뤄져야 합니다.

총 2번의 백트래킹이 진행되고, 최단거리를 구하는 로직은 재귀함수의 탈출조건에서 비교진행합니다.

 

TSP 알고리즘 Node.js

 

두 좌표간의 거리를 계산하는 함수를 생성합니다.

function calculateDistance(p1, p2){
    const yDiffSquared = Math.pow(p2[0] - p1[0], 2);
    const xDiffSquared = Math.pow(p2[1] - p1[1], 2);
    const dist = Math.sqrt(yDiffSquared + xDiffSquared);
    return Math.floor(dist * 100);
}

 

최단거리인 min값을 가장 큰 수로 지정합니다.

인자로 주어진 places의 길이를 N으로 정의합니다.

방문여부를 체크하기 위한 1차원 Boolean 타입 배열을 선언합니다.

let min = Number.MAX_SAFE_INTEGER;
const N = places.length;
const visit = Array(N).fill(false);

 

완전 탐색을 진행해야 하므로, 재귀 함수를 선언합니다.

재귀 함수의 인자로는(이전 좌표값, 재귀 카운터, 방문 체크 배열, 계산된 거리)입니다.

탈출조건은 count가 places의 길이만큼 도달했을 때 입니다. 만약 탈출조건에 도달했을 때 까지 계산한 거리가 min보다 작은 경우 스왑 후 재귀 함수를 빠져나옵니다.

재귀 로직은 방문 배열을 순회합니다. 배열의 요소가 false 값인 경우 이전 좌표값과 현재 좌표간의 거리를 계산합니다.

방문 배열에서 현재 좌표를 방문 체크한 후 다음 단계의 재귀 함수를 실행합니다. 

만약 재귀 함수가 탈출조건에 도달하면 min값과 비교를 진행하고 현재 요소의 방문 여부를 삭제하고 다음 요소로 방문을 진행합니다. 백트래킹 알고리즘을 사용합니다. 

const recur = (before, count, visited, distance) => {
    if(count === N){
        if(min > distance) min = distance;
        return;
    }

    visited.forEach((item, idx)=>{
        if(!visited[idx]){
            const tempDist = calculateDistance(places[before], places[idx]);
            visited[idx] = true;
            recur(idx, count+1, visited, distance+tempDist);
            visited[idx] = false;
        }
    })
}

 

 

재귀 함수를 실행하는 로직은 백트래킹 알고리즘을 사용합니다. 이유는 도시를 방문하는 출발점이 지정되어 있지 않기 때문입니다. 즉 0번째 좌표에서의 최단거리를 구하는 문제라면 재귀 함수를 한번만 실행하면 되는데, 출발/도착 좌표값이 지정되어 있지 않아 주어진 places 배열을 순회하면서 백트래킹 알고리즘을 작동시킵니다.

for(let i=0; i<N; i++){
    visit[i] = true;
    recur(i, 1, visit, 0);
    visit[i] = false;
}

 

최종적으로 min 값을 출력합니다.

return min;

 

 

전체 소스코드

function calculateDistance(p1, p2){
    const yDiffSquared = Math.pow(p2[0] - p1[0], 2);
    const xDiffSquared = Math.pow(p2[1] - p1[1], 2);
    const dist = Math.sqrt(yDiffSquared + xDiffSquared);
    return Math.floor(dist * 100);

}

const TSP = function(places) {
    let min = Number.MAX_SAFE_INTEGER;
    const N = places.length;
    const visit = Array(N).fill(false);

    const recur = (before, count, visited, distance) => {
        if(count === N){
            if(min > distance) min = distance;
            return;
        }

        visited.forEach((item, idx)=>{
            if(!visited[idx]){
                const tempDist = calculateDistance(places[before], places[idx]);
                visited[idx] = true;
                recur(idx, count+1, visited, distance+tempDist);
                visited[idx] = false;
            }
        })
    }

    for(let i=0; i<N; i++){
        visit[i] = true;
        recur(i, 1, visit, 0);
        visit[i] = false;
    }

    return min;
}

 

 

[Algorithm] 병합 정렬(Merge Sort) 구현하기 Node.js

 

[Algorithm] 백준 2580 스도쿠 Node.js

 

[Algorithm] 최대 이진 힙 구현하기 Node.js/Javascript