백트래킹 Backtracking

백트래킹 개념

1. 여러 가지 선택지 (옵션) 들이 존재하는 상황에서 한 가지를 선택한다

2. 선택이 이루어지면 새로운 선택지들의 집합이 생성된다

3. 이런 선택을 반복하면서 최종 상태에 도달한다

4. 올바른 선택을 계속하면 목표 상태(goal state)에 도달한다

백트래킹과 깊이우선탐색(DFS)의 차이

DFS는 완전탐색의 방법 중 한 가지이다. 백트래킹은 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄인다. (Prunning 가지치기) 깊이 우선 탐색이 모든 경로를 추적하는데 비해, 백트래킹은 불필요한 경로를 조기에 차단한다. 깊이 우선 탐색을 하기에는 경우에 수가 너무나 많다. 즉 N! 가지의 경우의 수를 가진 문제에 대해 깊이 우선 탐색을 가하면 당연히 처리 불가능한 문제이다.

백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만 이 역시 최악의 경우에는 여전히 지수함수 시간 (Exponential Time) 을 요하므로 처리 불가능하다.

 

백트래킹 예시 문제로 N-Queen 문제가 있다. 

9663 N-Queen (Java)

백트래킹 기법

어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가 (backtracking) 다음 자식 노드로 간다. 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다.

가지치기(prunning): 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다.

백트래킹 알고리즘

1. 상태 공간 트리의 깊이 우선 검색을 실시한다.

2. 각 노드가 유망한지를 점검한다.

3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속한다.

checknode (node v)
	if promising(v)
		if there is a solution at v
			wrtie the solution
		else
			for each child u of v
				checknode(u)

상태 공간 트리를 구축하여 문제 해결

bool backtrack(선택 집합, 선택한 수 cnt, 모든 선택수 n) // n개에서 r개를 고를 때
{
	if (선택한 수 == 모든 선택수) // 더 이상 탐색할 노드가 없다
	{
		찾는 솔루션인지 체크;
		return 결과;
	}

	현재 선택한 상태집합에 포함되지 않는 후보 선택들 (노드) 생성
	모든 후보 선택들에 대해
	{
		선택 집합에 하나의 후보 선택을 추가
		선택한 수 += 1
		결과 = backtrack 호출 (선택집합, 선택한 수, 모든 선택수)
	
		if (결과 == 성공)
			return 성공; // 성공한 경우 상위로 전달
	}
	return 실패;
}

 

백트래킹을 사용해서 순열을 구할 수 있다. 마음의 숙제처럼 못 하고 있다가 이제서야 겨우 할 줄 알게 되었는데... 다음 글에서 살펴boza!!