[백트래킹] 백트래킹의 개념

CSP(제약 만족 문제, Constraint Satisfaction Problems)란 무엇인가?

CSP는 변수가 가지는 도메인 내에서, 주어진 제약 조건을 만족하는 해를 찾는 문제를 말한다. 제약 조건을 만족하는 상태가 CSP의 목적 상태이다. 백트래킹 또는 퇴각검색이란 제약 만족 문제(CSP, Constraint Satisfaction Problems)를 위해 해결하여 쓰이는 일반적인 문제 풀이 기법이다.

 

 

 

Backtracking algorithm

특징

첫째로, 제약 조건을 만족시키지 않는 경우 탐색 범위에서 제외되므로 탐색 공간을 줄일 수 있다. 전수검사(exhaustive search)에 해당하지만 가지치기(pruning)가 발생하기에 엄밀한 의미에서 전수검사는 아니다. 둘째로, 모든 상태가 제약 조건을 만족시키지 않는 경우 해가 없음을 미리 알 수 있으므로 예측적 성격을 갖는다. 셋째로, 어느 도메인에서든 제약 조건만 설정하면 적용 가능하므로 도메인 독립적이다. 넷째로, 해를 찾는 과정을 추적(trace)할 수 있다.

 

/* exhaustive search의 동작 */
ExhaustiveSearch(Node v) {
	if (Solution exist at v) Write Solution;
	else for (each child u of v) ExhaustiveSearch(u);
}

/* backtracking의 동작 */
/*	1. 해당 노드가 promising한지 확인한다.
	2. 모든 제약조건을 만족하는 해라면, 그 해를 solution에 저장한다.
	3. 그렇지 않다면, childNode가 promising한지 확인한다. */
Backtracking(Node v) {
	/* Promising()은 문제에 따라 다르겠지만,
       더 깊이 들어가는 것이 유의미한지를 판단함. */
	if (Promising(v))
		if (Solution exist at v) Write Solution;
		else for (each child u of v) Backtracking(u);
}

 

구성요소

상태공간트리(state space tree)로 구성된다. 상태공간트리는 탐색의 시작 상태인 [A]로부터 점들을 path에 추가하여 확장시켜 탐색한 모든 상태들로 형성된 트리를 말한다. 경우의 수를 나눌 때 트리 모양과 유사하다.

domain variable: 상태값이 저장되어 있는 변수. 각 변수 사이에는 제약조건(constraint)이 존재한다.

domain value: domain variable에 할당될 수 있는 값들의 집합

constraint: variable 사이에 존재하는 제약조건. 문제 해결을 위해 요구되는 제약조건.

 

일관성 검사 기법

NC: Node consistency

AC: Arc consistency

PC: Path consistency

 

예시

미로찾기에서, 입구에서 시작해 출구에서 끝나는 경로가 존재하는지 묻는 문제(n-Queen)

제약조건을 만족하는 부분집합이 존재하는지 묻는 문제(map coloring)

미로찾기에서, 출구까지 가는 경로 중 최단 경로를 찾는 문제(subset sum)

 

구현

일반적으로 DFS, BFS를 통해 구현된다. 가지치기(pruning)는 if문 내 break, return을 통해 구현된다.