Ch 09. 해 탐색 알고리즘 (1)

고로케살지마라탕·2022년 5월 24일

알고리즘

목록 보기

13/14

9.0 해 탐색 알고리즘

범용적 알고리즘

언제 해 탐색 알고리즘을 사용하는가?

문제가 매우 복잡
근사 알고리즘 설계가 어려움
다항식 시간 내 찾기 어려움

종류

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

9.1 백트래킹 기법

백트래킹 기법이란?

해를 찾는 도중에 막히면 되돌아가서 해를 탐색하는 방법
최적화 문제(최솟값, 최댓값 찾는 문제)와 결정 문제(해가 존재하는지 yes or no)를 해결 가능

과정

여행자 경로 문제

점 A = 시작점
tour = [A]
bestSolution = ([A], ∞) 초기화

[A]가 완전한 해가 아니므로 tour [A]를 확장할 수 있는 점 찾기
- 점 B, C, D, E
- 각 점에 대해 거리 합 구하기
먼저 점 B에 대해서 거리 합 구하기
- newTour=[A,B]
- newTour 거리: 2

newTour의 거리(2) < bestSolution의 거리(∞)
- BacktrackTSP([A,B]) 재귀 호출
- 확장 가능한 점 C, D, E에 대해서는 BacktrackTSP([A,B]) 호출을 다 마친 후에 각각 수행

첫 번째 완전한 해
- bestSolution=([A,B,C,D,E,A], 30)
더 짧은 해를 구해 업데이트
tour=[A,C] 탐색 결과
- bestSolution보다 더 우수한 해는 탐색되지 않음.
- x 상태의 거리 > bestSolution의 거리 -> 가지치기
tour=[A,D] 탐색 결과
- bestSolution보다 더 우수한 해는 탐색되지 않음.
- 같은 거리의 해 -> bestSolution tour의 역순
- x 상태의 거리 > bestSolution의 거리 -> 가지치기
tour=[A,E] 탐색 결과
- bestSolution보다 더 우수한 해는 탐색되지 않음.
최종해 [A, B, E, C, D, A], 거리 16

의사코드

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) // 재귀호출
		}
	}
}

시간복잡도

상태 공간 트리의 노드 수에 비례
n개의 점이 있는 입력 그래프, 최대 크기의 상태 공간 트리
- 단말 노드 수만 계산해도 (n-1)!
이진트리 형태의 상태 공간 트리
- 최악의 경우에 $2^n$ 개의 노드를 모두 탐색 -> 지수 시간
완결 탐색의 시간복잡도와 같음
- 그러나 가지치기 작업으로 훨씬 효율적으로 동작

9.2 분기 한정 기법

백트래킹 기법의 단점

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

분기 한정 기법이란?

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

탐색 원리

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

과정

여행자 경로 문제

한정값

시작점부터 점 x까지의 경로 길이에다가 점 x를 떠나서 남은 다른 점들을 1번씩만 방문하고 시작점으로 돌아오는 경로의 예측 길이

앞으로 방문해야 할 각 점 x에 연결된 선분 중에서 가장 짧은 두 선분의 가중치의 평균의 합 사용!
- 가중치의 합을 1/2로 곱하는(평균을 내는) 이유는 한 점에서 나가는 선분은 인접한(다른) 점으로부터 들어오는 선분과 동일
- 소수점 이하의 숫자는 올림

점 A = 시작점
초기 상태 = [A]

초기 상태 [A]의 한정값 계산
- 각 점의 인접한 선분 중에서 가장 작은 2개의 가중치
  A: 2, 3
  B: 2, 3
  C: 1, 3
  D: 3, 5
  E: 1, 4
- [(2+3) + (2+3) + (1+3) + (3+5) + (1+4)] x 1/2 = 27/2 = 14
activeNodes={S}, bestValue=∞로 각각 초기화
- activeNodes 집합이 공집합이 될 때까지
$S_{min}$ =[A], [A]가 activeNodes 집합으로부터 제거
$S_{min}$ ([A])의 자식 상태 노드 생성, 각각 한정값을 구한다.
S’1=[A,B], S’2=[A,C], S’3=[A,D], S’4=[A,E]
S’1, S’2, S’3, S’4를 activeNodes에 추가
- activeNodes = {[A,B], [A,C], [A,D], [A,E]}
계속 자식 생성하여 수행
첫 번째 해 발견, 경로 거리 < bestValue(∞)
- bestValue=18, bestSolution=[A,B,C,E,D,A]
[A, B, E] 탐색 시작, 최적해 발견
- [A,B,E,C,D,A] 최적해, 경로의 길이

의사코드

입력: 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 탐색 수행 
        }
    }
}