Algorithm problem-44

1. 문제

• 각 도시의 위치가 주어지고 외판원이 모든 도시를 방문하는 최단거리를 리턴
• 각 도시 간 거리를 구하는 식은 주어져있음
• 해밀턴 경로, 조합 최적화 문제, NP-hard, 완전 탐색(exhaustive search)

2. 시도

• 완전 탐색 이외의 방법은 존재하지 않는다, 즉 순열로 모든 조합을 만든 후
• 안전한 가장 큰 수(Number.MAX_SAFE_INTEGER)로 결과값을 넣을 변수를 선언해두고
• 모든 조합의 지점 간 이동 거리를 전부 계산해서 작은 값이 나오면 결과값을 갱신
• 마지막까지 돌리고 난 후, 결과값을 리턴하는 방식으로 풀어야 할 듯
• 순열 조합을 구할 내부 함수를 구현하고
• 최단 이동거리를 저장할 이동결과값 변수를 최대안전수로 선언해 둔다
• 나온 조합의 모든 값을 이중반복문으로 모두 이동 거리를 결과값에 누적시켜서 계산하고
• 그 결과값이 이동결과값과 비교해서 작으면 갱신하는 방식으로 구현하고
• 반복문이 종료한 후 이동결과값을 리턴하면 완료
• 시간 내에 순열 생성 함수를 구현하지 못했다

3. 수도코드

// 거리 계산 함수는 레퍼런스 참조
const TSP = function (places) {
  // 순열 조합을 구할 내부 함수를 구현하고(미구현)
  const searcher = (arr, num) => {
    const cities = [];
    if (num === 1) return;
  }
  // 최단 이동거리를 저장할 이동결과값 변수를 최대안전수로 선언해 둔다
  let result = Number.MAX_SAFE_INTEGER;
  // 나온 조합의 모든 값을 이중반복문으로 모두 이동 거리를 결과값에 누적시켜서 계산하고
  const routes = searcher();
  // 그 결과값이 이동결과값과 비교해서 작으면 갱신하는 방식으로 구현하고
  for (let i = 0; i < routes.length; i++) {
    let distance = 0;
    for (let j = 0; j < routes.length - 1; j++) {
      distance += calculateDistance(routes[i][j], routes[i][j + 1]);
    }
    if (distance < result) {
      result = distance;
    }
  }
  // 반복문이 종료한 후 이동결과값을 리턴하면 완료
  return result;
};

4. 레퍼런스

// 이동 거리 계산 함수식
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
};