[기말] 해 탐색

여기서 살펴볼 알고리즘은

Backtracking

Branch&Bound

두 개이다.

 

Backtracking은 DFS, 깊이 우선 탐색이고,

Branch&Bound는 좀 다른데,

이 알고리즘들은 NP-완전 문제의 근사해가 아닌 최적해를 탐색하기 위한 방법들이다.

 

---

1. Backtracking

 

 PS를 하다보면 DFS알고리즘으로 접하기 쉬운 백트래킹이다.

백트래킹을 이용해 해를 구할 수 있는 문제의 종류는 다음과 같다.

 - 최적화 문제 (Optimization) : 최소,최댓값을 구하는 문제

 - 결정 문제 (Decision) : 해의 존재 여부를 구하는 문제

 

 일반적으로 백트래킹은 트리 구조에서, 가장 왼쪽 가장 깊은 트리부터

오른쪽으로 모든 트리를 탐색하는 방식이라고 생각하면 쉽다.

대충 이런식으로 모든 트리를 탐색하면서 최적해를 찾는 방식이다.

 

---

2. Branch and Bound

 

 번역은 분기 한정 기법이라고 되어있다.

위의 DFS방식은 거의 모든 노드를 탐색해야하고, 그래서 입력의 크기가 커지면 걸리는 시간이 기하급수적으로 늘어난다.

이러한 단점을 해결하기 위해 사용하는 기법이 분기 한정 기법이다.

 

분기 한정 기업은 BFS와 유사한 모습을 보이는데,

 - 첫 노드에서 연결된 모든 노드의 한정값을 구한다.

 - 한정값중 최소값을 갖는 노드로 가서 그 노드와 연결된 모든 노드의 한정값을 구한다.

 - 이를 반복하면서 Leap node에 도착하면 해를 구한다.

 - 다시 올라갔을 때, 먼저 구한 해와 같거나 큰 노드들은 탐색하지 않는다. ( 어차피 같거나 더 커질 것이므로 )

DFS와 BFS가 반반 섞인 모습이라고 해도 될 것 같다.

 

대충 이런 느낌이다.

 

그렇다면 한정값을 구하는 방식은 무엇인가?

책에 나온 그래프의 예시에서는 각 정점에서 연결된 간선 가중치중 가장 낮은 2개의 가중치의 합의 평균으로 정했다.

---