Azza's Blog

이번엔 그래프 알고리즘 두 번째,

Dijkstra 알고리즘과 TSP 문제에 대해서 정리해 보자.

- Dijkstra 알고리즘

일반적으로 '다익스트라'라고 읽었던 것 같은데...

위키피디아에는 '데이크스트라'가 제대로 된 이름이라고 하는거 같다.

이 Dijkstra 알고리즘은 Edge의 Weight가 양수인 Graph가 있을 때,

두 Vertex간의 Shortest Path를 찾는 알고리즘이다.

(* Edge의 Weight가 음수도 있을 경우는 Bellman-Ford 알고리즘을 사용한다)

(2012.7.30 수정)

Dijkstra 알고리즘은 Greedy Algorithm이지만, Optimal Solution을 찾는 알고리즘이다!

Dijkstra 알고리즘은 Dynamic Programming + Greedy 방법으로 Optimal Solution 을 찾는 알고리즘이다.
위키피디아에 있는 Pseudocode를 보면서 알고리즘의 아이디어를 알아보자.

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:                               // 초기화
 3          dist[v] := infinity ;                                  // v 로부터의 거리를 아직 모름
 5          previous[v] := undefined ;                             // 최적의 경로 배열 초기화
 7      
 8      dist[source] := 0 ;                                        // 시작점 -> 시작점의 거리는 0
 9      Q := the set of all nodes in Graph ;                       // 최초에는 그래프의 모든 노드에 대하여
10                                                                 // 체크를 해야함.

11      while Q is not empty:                                    // 메인 루프
12          u := vertex in Q with smallest distance in dist[] ;    // 처음에는 시작점에서 시작
13          if dist[u] = infinity:
14              break ;                                           // 시작점에서 접근 가능한 모든 노드에
15                                                                 // 대하여 체크가 끝났음.
16          
17          remove u from Q ;
18          for each neighbor v of u:                            // 단, 'v' 는 Q 에 포함된 노드.
20              alt := dist[u] + dist_between(u, v) ;
21              if alt < dist[v]:                                 // Relax (u,v,a) - dist, previous 업데이트
22                  dist[v] := alt ;
23                  previous[v] := u ;
24                  decrease-key v in Q;                          // dist[] 값이 변하므로, 필요시 Reorder Q.
25      return dist;

먼저 각 변수의 의미 및 설명인 필요한 라인에 대하여 알아보자.

- dist[v]: 시작 Vertex 에서 Vertex 'v' 까지의 거리. 알고리즘이 진행되면서 계속 업데이트 됨.

- previous[v]: 최적의 경로에서 Vertex 'v'의 이전 Vertex.

- Q : 최소 경로 확인이 끝나지 않는 Vertex 'v' 의 집함.

       Q 를 단순히 Linked List 나 Array 로 구성한다면, 복잡도가 O(V^2) 이 될 것이다. (그래도 구현이 쉽다)

       이 Q 의 v.key 값은 dist[v] 값이 되고, 이 key 값에 대해서 Binary Heap으로 Q를 구성한다면,

       복잡도는 O(E log V)가 된다. Fibonacci Heap 으로 Q를 구성한다면 O(E + V log V)가 된다.

                 반드시 확인해야 한다.

- 21번 라인: Relax (책에는 늦춘다) 라는 표현을 썼는데,

                 조금 설명을 해보자면 현재 dist[u] 는 최적의 경로이다.

                 여기에서 E(u,v) 를 더 했을 때 Weight 값(alt)이, 기존의 dist[v] 보다 작으면 alt 값을

                 dist[v] 의 새로운 최적의 경로로 설정하는 것이다.

- 24번 라인: Q 를 Min-Heap 등으로 구현하였을 경우,

                 Q 의 원소 'v' 의 key 값이 변경되므로 Q 를 재정렬할 필요가 있다.

위의 알고리즘이 끝난 뒤, Short Path 는 아래와 같은 Pseudocode 로 구할 수 있다.

1  S := empty sequence
2  u := target
3  while previous[u] is defined:
4      insert u at the beginning of S
5      u := previous[u]
6  end while ;

음..이건 따로 설명은 필요없어 보인다.

- TSP (Travelling Saleperson Problem, 외판원 여행 문제)

( http://en.wikipedia.org/wiki/Travelling_salesman_problem )

많은 알고리즘 책에서 설명하는 대표적인 NP-Hard 문제이다.

문제는 간단하다.

"여러 도시(Vertex)들이 있고 한 도시에서 다른 도시로 이동하는 비용(Edge weight)이 모두 주어졌을 때,

모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서는 무엇인가?"

그래프 이론의 용어로 설명하자면,

"Weighted Complete Graph^[각주:1](가중치가 있는 완전 그래프)에서

 가장 작은 가중치를 가지는 Hamiltonian cycle^[각주:2](해밀턴 사이클)을 구하라"

이다.

현재는 이런 문제를 다항시간에 풀 수 있는 알고리즘이 없으므로,

Heuristics(휴리스틱) 알고리즘이나 Approximation(근사) 알고리즘을 사용하여 빠르게 좋은 해를 찾는다.

(최근의 방법들은 높은 확률로 최적 해에서 2% ~ 3% 정도 오차가 있는 근사 해를 찾아낸다고 한다)

여기에는 여러가지 방법이 있을 수 있지만, 검색 좀 해보니 이런 방법들에 대한 연구는

거의 텀 프로젝트 수준이므로 패스하고,

Nearest Neighbor Algorithm 과 2-Opt Algorithm 에 대해서 설명하겠다.

- Nearest Neighbor Algorithm

( http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm )

이 방법은 단순하다. 일단 시작점이 주어지면, 시작점에서 가장 가까운 다음점을 찾아 연결한다.

그리고 그 다음점에서 다시 가장 가까운 점을 찾아 연결하는 과정으로 모든 점을 연결하고,

마지막 점과 시작점을 연결하는 것으로 완료된다.

- 2-Opt Algorithm

이 알고리즘은 처음부터 해를 찾는 알고리즘이 아니라,

NN Algorithm 등으로 찾은 해를 Improve 하는 알고리즘이다.

(더 이상 개선이 되지 않을 때 까지 반복을 하면, Local Optimal 이 되는 것이다)

(* 나의 경우엔, 두 선분의 Cross Check 가 귀찮아 대충 사각형을 그려서 겹치는 부분이 있으면,

    바꿔서 Length 를 구해보고 개선이 되면 바꾸는 방법을 사용하였기 때문에

    여러번 반복해야 했는지도 모르겠다)

간단하게 텍스트로 그려보면 아래와 같다.

 - V1   V2 -             - V1 - V3 -
      X         ==>     
 - V3   V4 -             - V2 - V4 -

V1-V4 와 V2-V3 가 Cross 하면, V1 - V2 - V3 - V4 순서를 V1 - V3 - V2 - V4 순서로 바꾸는 것이다.

요것도 그리 어렵진 않다.

하지만 TSP 문제가 아닌 Graph에서 사용하려면... Cross Check 하는 방법이 있긴 한지 잘 모르겠다.

2-Opt 의 좀 더 일반적인 방법인, Lin–Kernighan heuristic 을 사용한다면 방법이 있는거 같다.

(이것도 사실 잘 모르겠다)

어쨌거나 이렇게 근사해 구하고 개선하는 방법으로 풀면,

좋은 시간에 좋은 해를 구할 수 있는걸로~.

-- 각주 --