[알고리즘] 백트래킹 (Back Tracking), 되추적 알고리즘-C++

백트래킹 (back Tracking)

되추적 알고리즘

• 되추적 알고리즘은 상태공간트리에서 깊이 우선 탐색 (DFS)를 실시
• 유망하지 않은 노드들은 가지( pruning )쳐서 검색하지 않는다.
• 유망한 노드에 대해서만 그 노드의 자식 노드들을 검색한다.

🎯 상태공간트리( state space tree)
root에서 leaf까지의 경로가 해답 후보가 되는 트리, 깊이 우선 검색으로 그 해답 후보 중 해답을 찾을 수 있다.

유망성과 되추적

정의 : promising ( 유망하다 )

• 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않다. (non-promising)
• 해답이 나올 가능성이 있는 노드를 유망하다(promising) 고 한다.

정의 : 되추적이란?

• 어떤 노드의 유망성을 점검하고
• 유망하지 않다고 판정되면
• 그 노드의 부모(parent) 노드로 돌아가서 (되추적)
• 다음 후손 노드에 대한 검색을 계속 진행하는 과정

백트래킹 : 모든 노드 중 특정한 조건을 만족하는 해가 될 것 같은 노드만 살펴보는 것이다. 불필요한 부분을 쳐내고 최대한 올바른 해만 찾아보는 방식

진행 절차

1. 상태공간트리의 깊이우선 탐색 (Depth -first-Search) 실시
2. 각 노드가 유망한 지 점검( 해답이 나올 가능성이 있는가)
3. 만일 그 노드가 유망하지 않다면, 그 노드의 부모 노드로 돌아가 검색을 계속한다.

DFS와의 차이

DFS 깊이우선탐색은 가능한 모든 경로를 탐색한다.

백트래킹은 유망한 경로만 탐색한다.

• 불필요한 경로를 사전에 차단하지 않고 모든 경로를 탐색하기 때문에 경우의 수를 최적으로 줄이지 못한다.
• 반면에 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보기 때문에 가지치기(pruning) 에 따라 효율이 달라질 수 있다.

되추적 알고리즘 의사코드

void checknode (node v) {
	node u;
	if(v노드가 유망하다면){
		if( v노드에 해답이 있다면)
			해답 찾기;
		else
			for( v의 각 자식노드 u에 대해)
				checknode(u);
		}
}

Monte Carlo 기법

몬테 카를로 기법을 사용한 백트래킹 알고리즘의 수행 시간 추정

• 몬테 카를로 기법 : 무작위 변수를 이용해 기대값을 추정한다.
• 샘플 공간에서 샘플을 뽑아 평균을 내고 이를 반복해 기대값을 추정한다.

→ 열어야하는 노드의 갯수를 계산하지 않고 추정한다.

몬테 카를로 기법의 조건

1. 상태공간트리에서 같은 수준 (same level)에 있는 모든 노드에서 같은 유망함수를 사용해야한다.
2. 상태공간트리에서 같은 수준 (same level) 에 있는 모든 노드들은 같은 수의 자식노드를 가져야한다.

Monte Carlo 기법을 사용한 백트래킹 알고리즘의 수행시간 추정 방법

1. root 노드의 유망한 자식 노드의 개수를 M_0라고 한다.
2. 상태공간트리의 수준 1 (root노드의 자식세대) 에서 유망한 노드 하나를 무작위로 정하고, 그 노드의 유망한 자식 노드의 개수를 M_1라고 한다.
3. 위에서 정한 노드의 유망한 노드 하나를 다시 무작위로 정하고 , 그 노드의 유망한 자식 노드의 개수를 M_2라고 한다.
4. 더 이상 유망한 자식노드가 없을 때까지 이 과정 반복

M_i : 수준 i의 마디들에서 유망한 자식 마디의 평균 개수 추정치

T_i : 수준 i의 어떤 노드의 자식 노드의 총 개수

검사한 마디 총 개수의 추정치 :

1 + T_0 + M_0T_1+M_1T_2+M_2T_3….+M_i-1T_i

몬테 카를로 기법은 2번 이상 실행해 추정치를 구하고 여러 번 수행하면 좋은 추정치를 구할 확률이 높아진다. 하지만 그 확률을 보장할 수는 없다.

백트래킹 알고리즘 활용

• 0-1 knapsack 문제
• n-Queens problem 백준 9663번 N-Queen
• 부분 집합의 합 구하기
• 그래프 탐색