Azza's Blog

'C로 구현한 알고리즘' (Algorithms with C) 의 간단한 리뷰를 남겨본다.

먼저 자료구조 부분은 괜찮았다.

실제로 동작하는 소스 코드도 제공하고,

어느 정도 기본을 익히기에는 충분하다고 생각한다.

알고리즘 부분에 대해선 내가 원하는 스타일은 아니었다.

내가 원했던 것은, 알고리즘 접근 방법에 따라 분류를 나누고

(Divide&Conquer, Dynamic Programming, Greedy Algorithm, Heuristic Algorithms 등...)

이 방법을 이용해 문제를 해결하는 것을 원하였는데,

이런 설명 보다는 적용 분야에 따라 주제를 나누고 설명한 것이 별로였다고 본다.

( 물론 기하 알고리즘과 같은 새로운 분야에 대한 이야기는 흥미로지만 )

특히, 강력하지만 익숙해지기 어려운 Dynamic Programming 에 대한 설명은

거의 전무했다는 점에 대해선 실망스럽다.

결론은,

컴퓨터 프로그래밍 공부를 위해 알고리즘 책을 선택해야 한다면, 추천하고 싶진 않다.

앞에도 이야기 했듯, 자료 구조 내용은 나쁘진 않았지만,

알고리즘 책으로써는 별로라고 생각한다.

1. 선분 교차 테스트

2. 컨벡스 헐

3. 구면 위의 호의 길이

를 다룬다.

이전 TSP 에서 선분교차에 대해서 자세한 방법에 대한 이해를 못하여,

대충 직사각형 교차 체크만 하고 넘어갔기에, 거기에 대해 좀 자세히 알아보고,

나머지는 개념만 이해하고 넘어가겠다.

1. 선분 교차 테스트

점 A, B, C, D 에 대하여

선분 AB 와 선분 CD 가 서로 교차하는지,

컴퓨터를 이용하여 확인하는 방법에 대한 것이다.

수학에서라면 간단히 두 선분의 직선의 방정식의 해를 구하여

그 해가 선분의 범위안에 들어가는지 체크하면 쉽지만,

일반적으로 정확한 실수 연산이 되지 않는 컴퓨터 언어로는

그렇게 간단히 되지 않는다.

그래서 다음과 같은 2 단계를 따른다.

i) 선분의 양 끝 점을 대각선으로 하는 직사각형을 그려 교차하는 부분이 있는지 체크 한다.

   교차하는 부분이 없다면 교차하지 않음. 교차하는 부분이 있다면 ii) 로.

ii) 삼각형 ABC와 삼각형 ABD의 Signed Area의 곱이 <= 0, (곱이 0 이라면 선분이 겹치는 경우)

   AND 삼각형 CDA와 삼각형 CDB의 Signed Area의 곱이 <= 0 인지 확인.

i) 조건을 패스하고 ii) 조건이 True 가 된다면 두 선분은 교차한다.

Signed Area 는 세 점으로 만들어지는 면적을 구하는 데,

세 점의 방향에 따라 '+' 나 '-' 값을 가진다.

Signed Area 를 구하는 방법은 다음과 같다.

점 A, B, C 의 (x, y) 좌표를 각각 (a[0], a[1]), (b[0], b[1]), (c[0], c[1]) 이라고 했을 때,

삼각형 ABC의 Signed Area = ( a[0]*b[1] - a[1]*b[0] + b[0]*c[1] - b[1]*c[0] + c[0]*a[1] - c[1]*a[0] ) / 2

공식으로 구할 수 있다.

2. 컨벡스 헐(Convex Hull)

어떤 점 집합의 컨벡스 헐은 그 집합의 모든 점들을 포함하는 가장 작은 볼록 다각형을 말한다.

(출처: http://en.wikipedia.org/wiki/File:ConvexHull.svg )

위 그림에서 파란색으로 표시된 다각형이 바로 컨벡스 헐이다.

점 집합 P에 대한 컨벡스 헐을 만드는 한 방법은 Jarvis 행진(Jarvis's march)이라는 방법을 사용하는 것이다.

위와 같이 P0 에서 시작하여 각 점에 대하여 각도가 가장 작거나 큰 점들을 찾아서 계속 연결해 나가면 된다.

3. 구면 위의 호의 길이

구면 위의 두 점이 있을 때, 두 점의 거리(호의 길이를 말함)를 계산하는 방법에 대한 것이다.

자세한 수식은 생략하고 간단히 과정을 설명하겠다.

1. 두 점 A, B 의 좌표가 (x,y,z) 형태가 아닌,

   (구의 중심으로 부터의 거리, xz평면에서 y축 방향으로의 각도, yz평면에서 x축 방향으로의 각도) 형태로

   주어질 경우 (x,y,z) 형태의 좌표로 바꾼다.

2. 벡터의 내적을 이용하여 두 점 A, B의 각도(a)를 구한다.

3. 아래와 같이 원의 호를 구하는 공식을 이용하여, 호의 길이를 구한다.

결론

기하 문제들을 컴퓨터로 표현하고 해결하는 것은 흥미로운 과정이다.

특히, 게임 프로그래밍에 관심이 있다면 필수 과목이 아닐까?

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

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 을 사용한다면 방법이 있는거 같다.

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

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

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

-- 각주 --