TSP (TIL 102일차)

EenSung Kim·2021년 7월 16일

"도시, 방문, 최단"

Travelling Salesman Problem

Travelling Salesman Problem(TSP), 한국어로 외판원 문제라고 불린다고 합니다. 영문 위키백과에 따르면 TSP 는 다음과 같은 질문을 던지는 문제입니다.

"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"

여러 도시들의 목록과 도시간의 거리 (혹은 도시들을 이어주는 도로의 길이) 가 같이 주어질 때, 모든 도시들을 정확히 한 번씩 방문하고 원래의 도시로 돌아오는 가장 짧은 루트는 무엇인가?

최단 거리를 묻기도 하고 꼭 시작하는 도시로 돌아오지 않아도 되는 등 약간의 변형이 있지만, 기본적으로 이와 같은 질문을 던지는 알고리즘 문제를 TSP 문제라고 합니다.

위키백과에 따르면 TSP 문제는 1930년 등장했고 최적화와 관련해서 가장 집중적으로 연구된 문제라고 합니다. 매우 어려운 문제이지만 많은 방법들이 연구되었기 때문에, 도시의 숫자가 백만개가 되어도 1% 정도를 제외한 거의 대부분이 완벽하게 해결된다고 하네요.

많은 뛰어난 분들이 이를 해결했다지만, 거인의 어깨에 올라타려면 최소한 풀이방법이라도 이해해야 하겠죠. 그래서 이 문제를 블로깅해보려고 합니다.

핵심적인 내용

제가 생각하는 핵심적인 내용을 정리해보려고 합니다.

어떤 도시가 시작이 되어야 하는지 우리는 알 수 없으므로, 모든 도시에서 출발하는 경우의 수를 생각해보아야 한다.
모든 도시를 한 번만 방문해야 하므로 방문했음을 표시할 수 있는 무언가가 있어야 한다.
~~그리디 알고리즘처럼 가장 짧은 거리를 늘 선택하면 될 것이다.~~ 모든 경우를 다 탐색해봐야 한다.

핵심 코드

const aux = (lastVisited, isVisited, totalDist, visitedNum) => {
    if (visitedNum === places.length) {
      if(totalDist < curMinDist) {
        curMinDist = totalDist;
        return;
      }
    }

    for(let i = 0; i < isVisited.length; i++) {
      if (isVisited[i] === false) {
        let dist = calculateDistance(lastVisited, places[i]);
        isVisited[i] = true;
        aux(places[i], isVisited, totalDist + dist, visitedNum + 1);
        isVisited[i] = false;
      }
    }; 
  }