[알고리즘] 9. 해 탐색 알고리즘

9. 해 탐색 알고리즘

종류

• 백트래킹 기법
• 분기 한정 기법
• 유전자 알고리즘
• 모의 담금질 기법

9.1 백트래킹 기법

백트래킹 기법이란?

• 기본적으로 DFS(깊이우선탐색)를 통해 해를 찾는 도중에 ‘막히면’ (즉, 해가 아니면) 되돌아가서 다시 해를 찾아 가는 기법이다
• 최적화 문제(최솟값, 최댓값 찾는 문제)와 결정 문제(해가 존재하는지 yes or no)를 해결 가능

 

여행자 문제(Traveling Salesman Problem, TSP) 를 위한 백트래킹 알고리즘

❑Line 1~3

– 현재 tour가 완전한 해이면서 현재까지 찾은 가장 우수한 해인 bestSolution의 거리보다 짧으면 현재 tour로 bestSolution을 갱신한다.

– bestSolution의 거리보다 길거나 같은 경우에는 갱신 없이 이전에 호출했던 곳으로 돌아간다.

 

❑Line 4~8

– tour가 아직 완전한 해가 아닐 때 수행된다.

 

❑Line 5~8의 for-루프

– 현재 tour에서 확장 가능한 각 점에 대해서 루프의 내부가 수행된다.

– 확장 가능한 점이란 현재 tour에 없는 점으로서 현재 tour의 가장 마지막 점과 선분으로 연결된 점을 말한다.

 

❑Line 6

– 현재 tour를 확장(즉, 확장 가능한 점을 기존 tour에 추가) 하여 newTour를 얻는다.

 

❑Line 7~8

– 확장된 newTour의 거리가 bestSolution의 거리보다 짧으면, newTour를 가지고 알고리즘을 재귀 호출한다.

– 만일 newTour의 거리가 bestSolution의 거리보다 길거나 같으면, newTour를 확장하여도 현재까지의 bestSolution의 거리보다 짧은 tour를 얻을 수 없기 때문에 가지치기(pruning)를 한다.

– 가지를 친 경우에는 다음의 확장 가능한 점에 대해서 루프가 수행된다.

 

의사코드

tour = [시작점]  // 점의 순서
bestSolution = (tour, ∞)  // 거리 무한대 초기화

BacktrackTSP(tour) {
	if (tour가 완전한 해이면)
		if (tour의 거리 < bestSolution의 거리)  // 더 짧은 해를  찾았을 때
			bestSolution = (tour, tour의 거리)
	else 
    {
		for (tour 확장 가능한 각 점 v) 
        {
			newTour = tour + v    // 기존 tour의 뒤에  v 를 추가
			if (newTour의 거리 < bestSolution의 거리)
				BacktrackTSP(newTour) // 재귀호출
		}
	}
}

 

시간복잡도

• • 문제에 따라서 이진트리 형태의 상태 공간 트리가 형성되기도 하는데 이때에도 최악의 경우에 2^n개의 노드를 모두 탐색해야 하므로 지수 시간이 걸림
  • 이는 모든 경우를 다 검사하여 해를 찾는 완결 탐색 (Exhaustive Search)의 시간복잡도와 같음
  • 그러나 일반적으로 백트래킹 기법은 조건에 해당하지 않는 노드를 ‘가지치기’하기 때문에 완결 탐색보다 훨씬 효율적임

 

8.2 분기 한정 기법

백트래킹 기법의 단점

• 백트래킹 기법은 깊이 우선 탐색(DFS)수행
• 최적화 문제에 대해서는 최적해가 상태 공간 트리의 어디에 있는지 알 수 없으므로, 트리에서 대부분의 노드를 탐색하여야 함
• 입력의 크기가 커지면 해를 찾는 것은 거의 불가능

분기 한정 기법이란?

• 상태 공간 트리의 각 노드(상태)에 특정한 값(한정값)을 부여
• 노드의 한정값을 활용하여 가지치기
• 백트래킹 기법보다 빠르게 해 탐색
• 가장 우수한 한정값을 가진 노드를 먼저 탐색하는 최선 우선 탐색으로 해 탐색
• 최적화 문제 해결에 적합

탐색 원리

• 최적해를 찾은 후에, 탐색하여야 할 나머지 노드의 한정값이 최적해의 값과 같거나 나쁘면 더 이상 탐색하지 않는다.
• 상태 공간 트리의 대부분의 노드가 문제의 조건에 맞지 않아서 해가 되지 못한다.
• 최적해가 있을 만한 영역을 먼저 탐색한다.

의사코드

• 입력: S, 문제의 초기 상태

Branch-and-Bound(S) {
	S의 한정값 계산
	activeNodes = { S }   // 탐색되어야 하는 상태 집합
	bestValue = ∞           // 현재까지 탐색된 해 중 최솟값
	while ( activeNodes ≠ ∅ ) 
    {
		S_min= activeNodes의 상태 중, 한정값이 최소인 상태
		S_min을 activeNodes에서 제거
		S_min의 확장 가능한 노드 S’1, S’2, ..., S’k 생성
		각각의 한정값 계산
        
        for i=1 to k 
        {      // 확장한 각 자식 S’i
			if (S’i의 한정값 ≥ bestValue)
				S’i 가지치기
			else if (S’i가 완전한 해 & S’i의 값 < bestValue) 
				bestValue = S’i의 값
				bestSolution = S’i
			else
				activeNodes에 S’i 추가한다. // 나중에 S’i 탐색 수행 
        }
    }
}