05. 조합 탐색

[1. 개요]

동적 계획법이나 분할 정복 등의 문제 해결 방법을 모든 문제에 적용 할 수 없다.

캐시를 위한 메모리를 너무 많이 사용하거나 적절한 분할 방법이 없는 경우가 존재하기 때문이다.

 

이 경우 완전 탐색에서 다시 돌아와 생각 해야 한다.

부분 답과 완성된 답의 집합을 탐색공간이라 부른다.

완전 탐새의 수행 시간은 탐색 공간의 크기에 비례한다.

 

유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘을 조합 탐색이라 부르기로 한다.

기본적으로 최적해가 될 가능성이 없는 답들을 탐색하지 않는다.

---

[2. 가지치기 기법]

pruning 기법은 현재 상태에서 답의 나머지를 완성했을 때

얻을 수 있는 가장 좋은 답이 지금까지 우리가 구한 최적해보다 나쁘면 탐색을 더 하지 않는다.

 

똑똑한 가지치기 기법들은 여러 방법을 이용해 현재상태에서

얻을 수 있는 가장 좋은 답의 상한을 찾는다.

 

좋은 답을 빨리 찾아내는 방법은 보통

A> 탐색의 순서를 바꾸거나

B> 탐색 시작 전 탐욕법을 이용해 적당히 좋은 답을 우선 찾는다.

---

[3. 예제]

TSP 를 푸는 탐색 알고리즘에 적요하면서 그 변화를 비교해보도록 한다.

 

A> 완전 탐색을 이용한 TSP 해결

• 재귀를 이용한 완전 탐색

 

B> 기초적인 가지치기 기법:

• 현재 상태의 답이 지금까지 구한 최적해와 같거나 더 나쁜 경우 중단

 

C> 간단한 휴리스틱을 이용한 가지치기

=> 답의 남은 부분을 대략적으로 추정한다.

=> 문제를 과소평가하는 휴리스틱 또는 낙관적인 휴리스틱

=> 현재 가장 좋은 답의 길이가 best / 현재 까지 경로의 길이가 length 일 때,

=> 최적해를 계속 갱신하려면, best-length 미만인 경로로 남은 도시들을 모두 방문하고, 시작점으로 돌아가야 함.

=> 이거보다 길면 탐색을 중단 할 수 있다.

=> 그러나 실제 필요한 경로보다 더 긴 경로가 필요하다고 잘못 짐작하면 최적해를 못 찾을 수 도 있다.

=> 그래서, 휴리스트의 반환 값은 항상 남은 최단 경로의 길이보다 작거나 같아야 한다.

=> 실제 답 이하이면서도 가능한 가장 큰값을 구해야 한다.

==> 이를 위해서 문제의 제약 조건을 일부 없앤 더 단순한 형태의 문제를 풀도록 한다.

=> 아직 방문하지 않은 도시들에 대해 인접한 간선 중 가장 짧은 간선의 길이를 더하도록 한다.

=> 가장 짧은 간선들만 더하여 남은 부분을 유추했는데도 최적해보다 길면 탐색을 중단 할 수 있다.

 

 

D> 가까운 도시부터 방문 (탐욕법)

=> 각 재귀호출에서는 다음에 어느 도시를 방문 할 지를 결정하는데

=> 더 가까운 것부터 방문하면 좋은 답을 빨리 찾아낼 수 있는 경우가 있다.

=> 이러한 전략이 항상 최적해를 가져다 주는 것은 아니지만,

=> 좋은 답을 일찍 찾을 수록 가지치기를 더 많이 할 수 있다.

=> 각 도시마다 다른 모든 도시들을 거리 순으로 미리 정렬해서 저장한다.

 

 

E> 지나온 경로를 이용한 가지치기

=> 지금까지 만든 부분 답을 검사해서 가지치기 할 수도 있다.

=> 지금까지 만든 경로가 최적해를 이루는 경로가 아니라고 하면, 탐색을 계속할 이유가 없다.

=> 남은 조각들 (남은 도시를 방문하는 경로) 의 최소 비용은 똑같을 것 이다.

=> 현재까지 만든 부분해에 간단한 조작을 해보고, 답이 더 좋아진다면 탐색을 중단하는 방식으로 구현

=> 경로가 다음과 같을 때, (... ,p, a, b, q, ... , here)

=> a 와 b 의 순서를 바꾸고, p ~ q 구간의 거리가 더 짧아 진다면, 원래 경로는 최적해가 될 수 없으니 탐색을 중단한다.

=> 항상 현재 도시 이전의 두 도시만을 뒤집어 본다는 것을 유의하도록 한다.

=> 한 도시를 경로 뒤에 추가할 때 마다, 이 방식이 수행되기 때문이다

=> 전체 경로의 일부분을 통째로 뒤집는 것이 더 좋다.

=> (... ,p, a, b, c, d, e, q, ... , here)

=> (a, b, c, d, e) 나 (e, d, c, b, a) 경로 자체의 길이는 같고, 달라지는 것은 p 와 q 에 인접한 도시 뿐이다.

=> 자기 자신을 교차하는 경로를 만들지 않도록 해야 한다.

=> 경로의 일부분을 뒤집었을 때 더 짧아지지 않는다는 말은 이 경로가 최소한 자기 자신과 교차하지 않음을 보장한다.

 

 

F> MST 휴리스틱을 이용한 가지치기

=> C 에서 다룬 단순한 휴리스틱에서는 문제의 제약을 너무 많이 없에서 답을 너무 과소평가하는 경향이 있다.

=> 좀 더 현실에 가까운 휴리스틱을 계산하는 알고리즘이 있다면, 

=> 깊이 우선 탐색의 효율에 큰 도움이 된다.

=> 다음과 같은 제약을 추가하도록 한다.

==> 1. 한 간선은 최대 한번만 선택가능, 2. 선택하지 않은 간선을 모두 지워도 그래프가 둘 이상으로 쪼개지면 안된다.

=> 선택한 간선들만 남겼을 때, 아직 방문하지 않은 정점들과 현재 정점이 연결되어 있어야 한다.

=> 최소 스패닝 트리: 
     현재 위치에서 시작해서 아직 방문하지 않은 정점들을 모두 방문 후, 시작점으로 되돌아 오는 최단 경로

=> MST 가중치의 합은 항상 최단 경로보다 작음을 알 수 있다.

 

 

G> 마지막 단계 메모이제이션

• 조합 탐색 과정에서 같은 상태를 여러 번 만나는 것은 흔한 일 이다.
  => 한번 풀었던 문제를 다시 풀어야 한다.
• 메모이제이션 적용을 고려 할 수 있다.
  => 메모리가 부족할 수 있으므로, 남은 조각의 수가 미리 정한 K 이하일 경우만 적용한다.
• TSP의 경우, 5개 이하 도시가 남았을 때만 메모이제이션을 적용
  => 이 경우, 도시의 개수가 20 일 때, 저장 할 상태의 개수는 대략 44만 개
• 보통 메모이제이션을 적용하기 위해서는 현재 상태에만 영향을 받아야 하지만, TSP 는 현재 상태까지 오기 위한 경로에 영향을 받게 된다.
• 가지치기를 사용하지 않는 동적 계획법 함수를 별도로 작성한 뒤, 마지막 k 단계에 도달할 때, 메모이제이션을 적용
•  

---

[4. TSP 전체 결과 비교]

최적화	n=12	n=16	n=20	n=24
동적 계획법	0.03	0.58	26.45	768.21
완전 탐색 (A)	89.74	Time out	Time out	Time out
간단한 가지치기 (B)	2.58	981.53	Time out	Time out
간단한 휴리스틱 (C)	0.85	84.18	Time out	Time out
탐욕 (D)	0.52	31.03	Time out	Time out
인접한 두 도시 가지치기 (E)	0.15	4.64	233.52	Time out
부분 경로 가지치기 (E)	0.07	1.13	33.29	1160.81
MST 휴리스틱 (F)	0.06	0.37	14.77	836.43
메모이제이션 (G)	0.06	0.28	2.91	25.24