알고리즘: 최적알고리즘(분기한정법)으로 외판원문제(TSP)를 풀 수 있을까?

 

이전의 포스팅에서는 동적계획법을 이용하여 20개의 도시에 대한 외판원문제(TSP)를 풀었다.

 

하지만 40개의 도시에 대한 문제로 확장했을 때, 문제를 푸는데 6년이상 걸리므로 해밀토니안

회로 문제를 푸는 되추적 알고리즘을 이용하여 그저 아무경로나 취하는걸로 만족하게 되었다.  

 

하지만 이 알고리즘은 경로를 효율적으로 찾기는 하겠지만 최적의 여행경로와는 거리가 멀 수 있다.

 

그래서 이번 포스팅에서는 최적의 값을 찾는데 특화된 분기 한정법을 이용하여 40개의 도시에

대한 최적 여행 경로를 구할 수 있는지 알아본다.

 

 

 

다음은 이 포스팅을 읽기전에 참고하면 좋은 것들이다. 

 

알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드)

 

알고리즘: 해밀턴 회로문제(Hamiltonian Circuit Problem)(Backtracking 문제)

 

알고리즘: 분기한정법(Branch-and-bound)을 이용한 0-1 배낭채우기문제 (0-1 knapsack problem) 공부하기!

 

 

 

분기한정법을 이용하여 외판원 문제를 풀기위해 예시를 통해서 알아보겠다.

 

다음은 5개의 정점에 대한 최적경로문제 예시이다. 

 

좌측은 모든 정점을 연결하는 그래프의 인접행렬, 우측은 최적 경로를 이루는 그래프를 나타낸 것

 

 

 

 

 

< 상태공간 트리 구축하기 >

 

- 각 마디는 출발 마디로부터의 일주여행경로를 나타내게 된다.

 

- 예를 들어 뿌리 마디의 여행 경로는 [1]이 되고  뿌리 마디에서 뻗어 나가는

수준1에 있는 여행경로는 각각 [1, 2], [1, 3], [1, 4], [1, 5] 가 되고

[1, 2]에서 뻗어나가는 수준 2에 있는 마디들의 여행경로는 [1, 2, 3], [1, 2, 4], [1, 2, 5]가 된다.

 

- 따라서 최적 일주여행경로를 구하기 위해서는 잎마디에 있는 일주여행 경로를 모두 검사하여

그 중에서 가장 길이가 짧은 일주여행경로를 찾으면 된다. 

 

 

 

 

 

 

이제부터는 본격적으로 분기한정법을 이용하여 풀어보자

 

분기한정법에서는 최고 우선 검색을 이용하므로 각 마디의 한계값(bound)을 구할 수 있어야 한다.

 

0-1 배낭 채우기문제에서는 총 무게가 W를 넘지 않도록 하면서 이익을 최대로 하는게 

목표였기 때문에, 주어진 마디에서부터 뻗어나가서 얻을 수 있는 이익의 상한을 계산하였다.

 

그리고 어떤 마디에서 당시 최대이익보다 한계값이 큰 경우에 그 마디를 유망하다고 했다.

 

이 문제에서는 주어진 마디에서부터 뻗어나가서 얻을 수 있는 여행경로 길이의 하한을 구할 필요가 있다.

 

그리고 당시 최소 경로 길이보다 한계값이 작은 경우에 그 마디를 유망하다고 한다.

 

한계값은 다음과 같이 구한다.

 

어떤 여행 경로라도, 정점을 떠날 때 선택한 이음선의

길이는 그 정점에서 나오는 가장 짧은 이음선의 길이만큼은 최소한 길다. 

 

 

TSP의 한계값 구하기

 

 

가지친 상태공간트리 

 

 

다음과 같은 절차로 상태공간트리를 확장해나간다. 

 

1. [1]을 포함하는 마디를 방문한다.

a) 한계값을 계산하면 21이된다.

b) minlength를 무한대라 한다.

 

 

2. [1, 2]을 포함하는 마디를 방문한다.

a) 한계값을 계산하면 31이된다.

 

 

3. [1, 2]을 포함하는 마디를 방문한다.

a) 한계값을 계산하면 31이된다.

 

 

4. [1, 2]을 포함하는 마디를 방문한다.

a) 한계값을 계산하면 31이된다.

 

 

5. [1, 2]을 포함하는 마디를 방문한다.

a) 한계값을 계산하면 31이된다.

 

 

6. 한계값이 가장 작은 유망하고 확장하지 않은 마디를 결정한다. 

a) [1, 3]이 가장 한계값이 작으므로 그 마디의 자식마디부터 방문한다.

 

 

7. [1, 3, 2]을 포함하는 마디를 방문한다.

a) 한계값을 계산하면 22이된다.

 

 

8. [1, 3, 4]을 포함하는 마디를 방문한다.

a) 한계값을 계산하면 27이된다.

 

 

9. [1, 3, 5]을 포함하는 마디를 방문한다.

a) 한계값을 계산하면 39이된다.

 

 

10. 한계값이 가장 작은 유망하고 확장하지 않은 마디를 결정한다.

a) [1, 3, 2]이 가장 한계값이 작으므로 그 마디의 자식마디부터 방문한다.

 

 

위의 방식을 반복하여 최적의 값을 찾는다. 

 

 

 

 

 

<분기한정법을 이용한 TSP 풀기>

 

Struct node { 
	int level;
	ordered_set path; 
	number bound; 
}

 

void travel2(int n, const number W[][], ordered_set &opttour, number &minlength) {
	priority_queue_of_node PQ;
	node u, v;
	initialize(PQ);
	v.level =0;
	v.path = [1]; 
	v.bound = bound(v);
	minlength = INFINITE;
	insert(PQ, v);
	while (!empty(PQ)) {
		remove(PQ, v);
		if (v.bound < minlength) {
		u.level = v.level + 1;
		for ((all i such that 2< i< n) && (i is not in v.path)) {
			u.path = v.path; 
			put i at the end of u.path;
			if (u.level == n-2) {
				put index of only vertex not in u.path at the end of u.path;
				put 1 at the end of u.path;
				if (length(u)<minlength) { 
					minlength = length(u);
					opttour = u.path;
				}
			}
			else {
				u.bound = bound(u);
				if (u.bound < minlength) insert(PQ, u);
			} 
		}
	}
}

 

 

이 분기한정 알고리즘은 자식노드를 효율적으로 방문하기 때문 검사 마디의 개수가 더 적다.

 

하지만 알고리즘의 시간복잡도는 지수적이나 그보다 못하다.

 

즉 분기한정 알고리즘으로도 40개의 도시 사례에 대한 해답을 효율적으로 구하지 못한다는 의미이다.

 

그래서 이러한 문제를 취급하는 또 다른 방법은 근사 알고리즘을 개발하는 것이다.

 

근사 알고리즘은 최적해를 준다는 보장은 없지만 최적에 꽤 가까운 해답을 준다.

 

외판원 문제에 대한 근사 알고리즘은 다음 포스팅에서 알아보도록 하겠다.