NP완전 문제

다항식 시간에 해결 가능한 알고리즘이 아직 발견되지 않았으며 그렇다고 어느 누구도 다항식 시간 내에 해결 불가능 하다고 증명하지도 못한 문제. 어느 한 문제라도 다항식 시간에 해결 가능한 알고리즘을 찾는다면 나머지 모든 문제들도 다항식 시간에 해결 가능한 알고리즘이 존재한다. 입력이 조금만 커지면 최적해를 찾는 최신 알고리즘을 사용하더라도 너무 오랜 시간이 걸림

여행하는 외판원 문제(TSP:Traveling Salesman Problem)

여행하는 외판원 문제는 대표적인 NP-완전 문제이다. 모든 도시들을 단 한 번만 방문하고 원래 출발한 도시로 돌아오는 최단 경로를 알아내는 문제이다.

욕심쟁이 방법에 기초하여 최적해에 가까운 근사해를 찾는 근사 알고리즘을 사용한다. 도시는 정점으로, 도로는 간선으로, 도시간 거리는 간선의 가중치로 나타낸 그래프로 모델링한다.

TSP의 조건

  • 대칭성

    두 도시간의 거리가 양방향으로 동일하다. 방향성이 없는 가중치 그래프이다.

  • 삼각 부등식(triangle inequality)

    삼각형으로 위치한 세 도시를 잇는 도로 가운데 두 도로의 길이의 합은 다른 도로의 길이보다 같거나 길다는 것이다.

  • 완전 그래프

    모든 도시들 간에 반드시 도로가 있다면 완전 그래프로 나타낸다.

시간 복잡도

  1. 무작위 기법 : Θ(n!)
  2. 동적 계획법 : O(n^2 * 2^n)

위 두 방법 모두 시간이 너무 오래 걸린다.

근사 TSP알고리즘(최근접 이웃 알고리즘)

모든 도시를 방문할 때까지 인접한 도시들 중 아직 방문하지 않은 가장 가까운 도시 방문한다. 구현하기 쉽고 나름 짧은 경로를 빠른 시간 내에 구함. 완전 그래프가 아니라면 경로가 존재한다 하더라도 경로 자체를 구하지 못할 수도 있다.

근사 TSP알고리즘(MST 이용 알고리즘)

MST로부터 깊이 우선 탐색과 삼각 부등식을 이용하여 선형 순서를 만든다.

방법

  1. MST를 구하고 출발점 S로부터 DFS를 실행
  2. 방문 순서에서 마지막에 다시 나오는 출발점을 제외하고 두번이상 중복 방문한 정점을 제거
list TSP_approximation(graph G, vertex s)
{
  tree T;
  list L;
  T = prim MST(G->V, G->E,s);
  L = T를 깊이 우선 탐색하여 방문되는 정점의 순서리스트;
  L에서 가장 마지막의 출발점을 제외하고는 중복된 정점을 제거;
  return L;
}

프림알고리즘의 복잡도와 동일하다.

욕심쟁이 방법을 마치며

  • 각 단계에서 내리는 선택이 최적이라는 사실이 수학적 귀납법으로 증명될 때 욕심쟁이 방법을 사용한다.
  • 부문제들이 중첩되는 경우는 동적 계획법을 사용한다.
  • 욕심쟁이 방법은 선택 후 부문제를 해결하려는 전략이므로 크기가 큰 문제에서 작은 문제로 줄여나가는 하향식 기법이다.