[Toy Problem] TSP (travelling salesman problem)

문제 설명

외판원 문제(travelling salesman problem, 이하 TSP)는 아래와 같이 정의됩니다.

• 여러 도시들의 위치가 주어졌을 때, 모든 도시들을 단 한번씩 방문하는 최단 거리를 구하세요.

각 도시의 위치를 나타내는 좌표평면 위의 점들을 입력받아, TSP의 최단 거리를 리턴해야 합니다.

입력

인자 1: places

• 배열을 요소로 갖는 배열
• places[i]는 number 타입을 요소로 갖는 배열
• places[i].length는 2
• places[i]의 요소는 차례대로 좌표평면 위의 y좌표, x좌표

출력

• number 타입을 리턴해야 합니다.

주의사항

• 외판원이 출발하는 도시와 도착해야 하는 도시는 정해져 있지 않습니다. 모든 도시를 빠짐없이 한번씩 방문하는 경로 중 최단 거리를 리턴해야 합니다.
• 두 점 사이의 거리를 계산하는 함수 calculateDistance가 주어집니다. 도시 간 거리는 반드시 이 함수를 이용해서 계산해야 합니다.
• 함수 calculateDistance는 소수점 계산을 피하기 위해 두 점 사이의 거리에 100을 곱한 후 정수 부분만 취합니다. 최단 거리도 이 기준으로 판단합니다.

입출력 예시

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

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]

Advanced

• 아래 내용에 유념하여 TSP에 대해 학습해 보세요.
  • TSP 처럼 모든 꼭지점을 한 번씩 지나는 경로를 해밀턴 경로(Hamiltonian path)라고 합니다.
  • TSP는 조합 최적화 문제의 일종으로 NP-hard라는 것이 증명되었습니다.
  • 완전탐색(exhaustive search) 외의 방법이 존재하지 않습니다.

Solution

순열.

1. places에 들어있는 도시들을 순열의 조합을 만든다.
2. 탐색 시작
   2-1. 조합한 배열을 탐색하며 반복문의 현재 인덱스와 다음 인덱스의 도시간 거리를 계산한다.
   2-2. 두번째 반복문이 끝나면 계산한 도시간 거리가 result보다 작을경우 result에 할당한다.
3. result에는 모든 도시들을 방문했을때 가장 짧은거리가 할당되어 있으므로 리턴.

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

const TSP = function (places) {
    const getPermutations = function (arr, len) {
        const results = [];
        if (len === 1) return arr.map((el) => [el]);

        arr.forEach((fixed, idx, origin) => {
            const rest = [...origin.slice(0, idx), ...origin.slice(idx + 1)]
            const permutations = getPermutations(rest, len - 1);
            const attached = permutations.map((el) => [fixed, ...el]);
            results.push(...attached);
        });
        return results;
    };
    let cities = getPermutations(places, places.length)
    let result = Number.MAX_SAFE_INTEGER
    for (let i = 0; i < cities.length; i++) {
        let distance = 0
        for (let j = 0; j < cities[i].length - 1; j++) {
            distance += parseInt(calculateDistance(cities[i][j], cities[i][j + 1]))
        }
        if (distance < result) result = distance;
    }
    return result
};

GItHub repo