판매원 알고리즘 Travelling Salesman Problem (TSP)

판매원 알고리즘은 시간이 팩토리얼로 걸리기 때문에 들러야 할 도시가 8번이 넘어간다면 굉장히 오래걸리기 때문에, 완전탐색을 해야 하되 8번 이상은 별 다른 기법을 도입해야한다.

제일 적은 거리를 이동해 모든 도시를 도는 방법은 어떻게 되는가?

보통은 다시 되돌아오는 경우를 생각하지만 여기서는 출발지와 도착지를 모두 고려한다.

먼저, 다음과 같이 값들이 있다고 친다.

  final static int x[] = { 0, 14, 25, 50, 20, 2, 100 };
 final static int y[] = {1,1,10,70,40,99,100};

x[0], y[0] 은 시작지점이며

x[6], y[6] 은 끝지점이다.

시작지점과 끝지점이 결정되었다고 했을때, 중간에 어떤 루트를 타야할지 계산해야한다.

일단, distance라는 이차원배열에다가 쉽게 식별할수 있도록 거리를 넣을수 있게 설계를 해본다. 일단 거리를 재는 방법은 아래와 같이 맨하탄 거리를 이용하도록 한다. 왜냐구? 정수가 나오게끔 식을 단순화하고 싶어서이다.

 public static int getDistanceBetweenTwo(int x1, int x2, int y1, int y2) {
  return (Math.abs(x1 - x2) + Math.abs(y1 - y2));
 }

그다음에 각 점의 거리를 구하면 된다. 이차원밖에 되지않으니 굳이 재귀를 돌리지 않아도 쉽게 이중루프로 구현이 가능하다.

 public static int[][] getDistanceList(int[] x, int[] y) {
  
  int[][] distance = new int[x.length][y.length];
  
  for (int i = 0; i < x.length; i++) {
   for (int j = 0; j < y.length; j++) {
    distance[i][j] = (getDistanceBetweenTwo(x[i], x[j], y[i], y[j]));
   }
  }
  return distance; 
 }

O(n제곱) 의 시간이 걸리는데, 이정도면 일단은 각 도시가 천개 이상이 있어도 쉽게 돌리는 수준이다.

그리고 메인에는 필요한 사전작업을 해준다.

 static int n;
 static int[][] distance;
 
 public static void main(String[] args) {
  
  Vector<Integer> path = new Vector<Integer>();
  Vector<Boolean> isVisited = new Vector<Boolean>();
  
  n = x.length; // 갯수
  
  for (int i = 0; i < n; i++) {
   isVisited.add(false);  //아직 도시를 들르지 않았다는 사전작업
  }
  
  distance = getDistanceList(x,y); //각 거리 측정
    
 }

현재 distance[][] 에 각 거리가 저장이 되어있고 isVisited는 특이하게도 false로 저장된 상태이다. path 벡터에는 차례로 도시의 인덱스를 add하게 된다.

다음은 중요한 코어 로직인 getPath를 작성하도록 한다. 재귀를 돌면서 지금까지의 path를 저장하고 방문여부를 저장하는 isVisited, 그리고 마지막으로 앞단에서 계산했던 거리를 저장할 totalDistance를 하나 지정한다.

실제, 재귀로 자신을 호출하기 전에, 최종적으로 마지막 element에 다다를때 루프를 탈출하도록 해 거리를 계산하도록 하여야 하기 때문에 일단 아래와 같이 구현한다.

 public static int getPathAndTotalDistance(Vector<Integer> path, Vector<Boolean> isVisited, int totalDistance) {
  if(path.size() == n-1) return totalDistance + distance[path.lastElement()][n-1];

//로직구현필요

 }

즉, 마지막 도착지를 제외한 갯수 (n-1) 까지 모두 돌았을때는 마지막 도착지를 한번 연결해주고 끝나도록 구현을 했다. ( lastElement()는 최근에 추가한 path를 튕겨나오게 한다. )

이제, 기저부분에 대해서 구현을 했으니 (재귀를 끊는 부분) 재귀를 돌리는 부분을 구현을 해야한다. 일반적으로 트리형태의 재귀에서는 for문 안에서 재귀를 호출한다.

일단, 한번 방문한 곳은 재귀를 태울 필요가 없다.

  for (int i = 0; i < n - 1; i++) {
   if (isVisited.get(i))
    continue; // 한번 들렀으면 계산할 필요가 없음
   

//여기에 계속해서 로직

  }

그리고 처음 부분도 결정해주어야 한다. 만약 처음부분이 결정되지 않은채로 랜덤한 위치에서 시작하고 싶다면 아래 부분은 굳이 필요가 없다.

   //만약 처음부분이 결정되지 않도록 한다면 아래 부분은 필요없다.
   if (i == 0) {
    path.add(0);
    isVisited.setElementAt(true, 0);
    continue;
   }

다음은 새로운 거리를 계산한다. 이전의 것과 현재의 인덱스간의 차이를 totalDistance에 더한다.

totalDistance = totalDistance + distance[path.lastElement()][i];

또한 이제 path와 isVisited에 인자를 더해준다.

      path.addElement(i);
   isVisited.setElementAt(true, i);

그런데, 사실 그냥 결과를 취하면 안되고, result로 저장해놓은 거리와 리턴받은 거리중에 더 작은것을 택해야한다.

int temp = getPathAndTotalDistance(path, isVisited, totalDistance);

   result = Math.min(result, temp);

다음은 참조형 변수 초기화

   path.remove(path.size() - 1);
   isVisited.setElementAt(false, i);

최종코드

import java.util.Vector;

public class TSP {

 final static int x[] = { 0, 14, 25, 50, 20, 2, 100 };
 final static int y[] = { 1, 1, 10, 70, 40, 99, 100 };
 static int n;
 static int[][] distance;

 public static void main(String[] args) {

  Vector<Integer> path = new Vector<Integer>();
  Vector<Boolean> isVisited = new Vector<Boolean>();

  n = x.length; // 갯수

  for (int i = 0; i < n; i++) {
   isVisited.add(false); // 아직 도시를 들르지 않았다는 사전작업
  }

  distance = getDistanceList(x, y); // 각 거리 측정
  int totalDistance = getPathAndTotalDistance(path, isVisited, 0);
  System.out.println(totalDistance);

 }

 public static int getPathAndTotalDistance(Vector<Integer> path, Vector<Boolean> isVisited, int totalDistance) {
  if (path.size() == n - 1) {
   return totalDistance + distance[path.lastElement()][n - 1];
  }
  
  int result = 1000000000; //초기화
  
  //끝부분이 결정되었으므로, n-1까지 돈다.
  for (int i = 0; i < n - 1; i++) {
   if (isVisited.get(i))
    continue; // 한번 들렀으면 계산할 필요가 없음
   
   //만약 처음부분이 결정되지 않도록 한다면 아래 부분은 필요없다.
   if (i == 0) {
    path.add(0);
    isVisited.setElementAt(true, 0);
    continue;
   }
   
   totalDistance = totalDistance + distance[path.lastElement()][i]; // 새로운 거리 계산

   path.addElement(i);
   isVisited.setElementAt(true, i);

   int temp = getPathAndTotalDistance(path, isVisited, totalDistance);

   result = Math.min(result, temp);

   // 자기호출을 탈출하고 나왔다면, 참조형 변수들은 초기화를 해주어야 한다. 다른 루프분기에 영향을 줄 수 있다.
   path.remove(path.size() - 1);
   isVisited.setElementAt(false, i);

  }

  return result;

 }

 public static int getDistanceBetweenTwo(int x1, int x2, int y1, int y2) {
  return (Math.abs(x1 - x2) + Math.abs(y1 - y2));
 }

 public static int[][] getDistanceList(int[] x, int[] y) {

  int[][] distance = new int[x.length][y.length];

  for (int i = 0; i < x.length; i++) {
   for (int j = 0; j < y.length; j++) {
    distance[i][j] = (getDistanceBetweenTwo(x[i], x[j], y[i], y[j]));
   }
  }
  return distance;
 }

}

조금만 변형하면 처음과 끝이 없고 순환구조로 만들수도 있고,

순환구조가 아닐수도있고,

처음만 있는구조일수도있고,

끝만 있는 구조로 작성할수도 있다.

재귀를 돌릴때는 다음과 같은 점을 명시하여야 한다.

1) 트리구조일때는 탈출로직 다음 바로 for문안에 자기 함수를 호출한다.

2) int나 double같은 로컬변수는 알아서 함수를 나올때마다 분기에서 갈라졌던 변수를 스택에서 기억해 사용할수 있지만

참조형변수는 (C에서의 &형식의 변수) 주소를 통해 값이 변하기 때문에 분기후에 갈라져서 처리했던 로직이 반영되어있다. 다른 분기에 영향을 주면 안되므로 이를 초기화 해야한다.

2017업데이트 --

재귀시, 메모이제이션을 해야하는데 무엇을 해야하는가? 지금까지 왔던 길 순서를 기억해야한다. 이는 비트마스크를 씌워 101011011 이런식으로 표현해서 이를 기억하고 있으면 된다.