자바에서 JGraphT 를 써서 Christofides의 알고리즘 구현하기 (1)

안녕하세요. 오늘은 외판원 문제 (travelling salesperson problem) 의 대표적인 풀이법인 Christofides 알고리즘을 JGraphT로 구현하는 예제를 살펴보고자 합니다.

JGraphT는 자바에서 쓸 수 있는 그래프 이론 관련한 라이브러리입니다. 자세한 사용방법은 jgrapht.org를 방문해 주시기 바랍니다.

외판원 문제는 도시 리스트와 각 도시 사이의 거리가 주어졌을 때, 모든 도시를 돌아서 시작 도시로 돌아오는 가장 짧은 경로를 찾는 문제입니다.

위 그림은 http://mathworld.wolfram.com/TravelingSalesmanProblem.html 에서 가져온 최단 순회 경로를 나타낸 그림입니다.

이 문제를 풀기 위해서는 모든 두 도시 사이의 거리가 다 주어졌다고 할 때, 모든 시작점에 대해 고려해보면 생각해볼 수 있는 경로 수는 도시 수의 팩토리얼입니다.

도시수가 20개만 되도 지금 컴퓨터로 완벽한 답을 얻기 위해 거의 영원히 경로를 탐색해봐야 합니다.

완벽한 답을 얻지 못한다면 가장 짧은 경로보다 아무리 안좋은 경로라도 최대 몇 배 까지만 한계가 정해진다면? 그래서 1976년 Nicos Christofides 가 최악의 경우 가장 짧은 순회 경로보다 3/2배 긴 경로를 찾아내는 알고리즘을 제안했습니다. (어떻게 해서 최악의 경우에 최소 경로보다 3/2배 긴 경로를 찾는지는 지나가는 공대 대학원생에게 물어봐주세요 ㅎㅎ)

Christofides algorithm 위키피디아 페이지를 보면 알고리즘 동작 순서는 아래와 같습니다. 모든 도시로 만든 그래프가 G라고 했을 때, (이때 G는 완전 그래프. 아래 그림은 https://en.wikipedia.org/wiki/Christofides_algorithm 에서 링크)

[모든 도시 사이로 만든 완전 그래프 G]

1. G의 최소 신장 트리 (minimum spanning tree) 인 T를 구합니다.

[G에서 구한 최소 신장 트리 T]

2-1. T에서 차수(degree)가 홀수인 노드 O를 구합니다.

[T에서 차수가 홀수인 노드 O]

2-2. 맨 처음 주어진 그래프 G에서 노드 O만을 이용해 부분그래프(subgraph)를 구합니다.

 

[G에서 O만으로 만든 부분그래프]

3. 위에서 구한 부분그래프에서 최소 가중치 완전 부합(minimum-weight perfect matching) M을 구합니다.

[최소 가중치 완전 부합 M]

4. 앞서 구한 T와 M의 합집합으로 이루어진 다중 그래프(multi graph)를 구합니다.

[T, M 합집합으로 구한 다중 그래프]

5. 위에서 구한 다중 그래프의 한붓 그리기(Euler tour)를 구합니다.

[한붓 그리기]

6. 한붓 그리기한 결과의 해밀턴 경로(Hamiltonian path)를 구하되 이미 방문했던 엣지(edge)에 대해서는 지름길을 택합니다.

[지름길을 쓴 해밀턴 경로]

알고리즘을 자바로 구현할 때, JGraphT를 쓰면 위 단계 대부분이 라이브러리로 구현되어 있기 때문에 빠르게 구현할 수 있습니다. 다음 글에서 구현하는 예제 코드를 보겠습니다.