Backtracking 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]] 

==개요==
백트래킹은 탐색 공간(search space) 의 모든 가능한 구성을 체계적으로 탐색하는 방법dlek. 하지만 모든 문제에 똑같이 적용되는 알고리즘이 아니라, 각 문제에 맞게 커스터마이징해야 하는 일반적인 틀(general framework)이다. 이때 백트래킹은 결국 암묵적인 상태공간그래프(implicit state-space graph) 를 DFS 방식으로 탐색하는 것과 동일하며, 아래와 같은 특징을 가진다:
# Subsets/Permutations 탐색에 유용함: 백트래킹은 집합의 모든 부분집합이나 순열을 손쉽게 탐색할 수 있음.
# 정확성 보장: 가능한 모든 조합을 열거하므로, 누락 없이 정답을 찾을 수 있음.
# 효율성(Pruning): 단순 DFS보다 효율적으로 하기 위해 “불필요한 가지(dead branches)”를 잘라내야 함.

===Sudoku and Backtracking===
백트래킹(Backtracking)이란 모든 가능한 해(해답 공간, search space)를 탐색하면서 유망하지 않은 경로는 되돌아가는(recursive pruning)기법이다. 예를 들어 스도쿠를 해결하고자 할때 백트래킹 기법을 사용할 수 있다. 스도쿠는 모든 가능한 숫자 조합을 시도해야 하는 문제이기 때문에, 일종의 완전 탐색(exhaustive search)이 필요하다. 하지만 현실적으로 제약(Constraints) 을 이용하면 불가능한 경우를 일찍 걸러낼 수 있으며, 이러한 과정을 Pruning(가지치기)이라고 한다. 즉, 가능한 경우만 남기고 불가능한 경로는 조기 탈락시켜 효율을 높이는 것이다. 

스도코의 문제의 해(각 칸, 혹은 각 열)를 벡터 a로 표기하고, 각 원소 a<sub>i</sub>는 해의 i번째 요소를 의미한다고 하자. 이때 각 a<sub>i</sub>는 가능한 선택지 집합인 유한 집합 S<sub>i</sub> 중 하나에서 선택된다. 이렇게 해를 벡터 형태로 구성하여 가능한 모든 조합을 탐색하는 것이 백트래킹 방식이다. 예를 들어 순열 문제에서는 a<sub>i</sub>는 i번째 위치에 올 숫자를 의미한다. 또한 부분집합 문제에서는 a<sub>i</sub>는 i번째 원소가 포함되어 있을 경우 true, 아니면 false로 설정된다.

스도쿠 문제를 백트래킹을 통해서 해결하고자 할때는 아래와 같은 절차를 따른다:
# 부분 해(partial solution)가 <math>a = (a_1, a_2, \cdots, a_k)</math>와 같이 존재한다.
# 해를 확장하기 위해서 가능한 후보 a<sub>k+1</sub>을 선택한다.
# 확장된 해가 유효한지(valid) 검사하여 만약 완전한 해이면 저장한다.
#* 아니면, 아직 해가 될 가능성이 있다면 재귀(recursion)적으로 다음 단계를 진행한다.
#* 가능성이 없다면 현재 선택을 “되돌리고(backtrack)” 다른 선택을 시도한다.
즉, “Try → Check → Recur → Undo and Try Next”를 재귀적으로 반복하여 문제를 해결하는 것이 백트래킹의 구조이다. 

==Backtracking Implementation==
아래는 백트래킹의 핵심 알고리즘 구조를 보여주는 수도 코드이다:
<syntaxhighlight lang="go">
Backtrack(a, k)
    if a is a solution, print(a) 
    else {
        k = k + 1
        compute S_k
        while S_k ≠ ∅ do
            a_k = an element in S_k
            S_k = S_k - a_k
            Backtrack(a, k)
    }
</syntaxhighlight>
위 코드에서 각 변수는 아래와 같다:
* a: 현재까지 만들어진 부분해(partial solution) 벡터
* k: 현재 단계 (몇 번째 요소를 채우는 중인지)
* S_k: 현재 단계에서 가능한 후보(candidate) 집합
위 알고리즘은 아래와 같은 절차를 통해 작동한다:
# 기저 조건 검사: a가 완전한 해이면 출력(print(a))
# 아니라면 다음 단계로 확장
#* k를 1 증가 (다음 위치로 이동)
#* 가능한 후보 집합 S_k 계산
#* 후보가 남아 있는 동안 반복:
#*# 하나를 선택해 a_k에 저장
#*# 그 후보를 제외하고 (S_k = S_k - a_k)
#*# 재귀적으로 Backtrack(a, k) 호출
위 절차를 통해서 모든 가능한 조합을 체계적으로 탐색하게 되었다. 

===Backtracking Implementation on C===
아래는 백트래킹 기법을 C언어를 통해서 구현한 것이다:
<syntaxhighlight lang="c">
void backtrack(int a[], int k, data input) {
    int c[MAXCANDIDATES];  /* 후보 집합 */
    int nc;                /* 후보 수 */
    int i;                 /* 반복용 변수 */

    if (is_a_solution(a, k, input)) {
        process_solution(a, k, input);
    } else {
        k = k + 1;
        construct_candidates(a, k, input, c, &nc);
        for (i = 0; i < nc; i++) {
            a[k] = c[i];
            make_move(a, k, input);
            backtrack(a, k, input);
            unmake_move(a, k, input);
            if (finished) return; /* 조기 종료 조건 */
        }
    }
}
</syntaxhighlight>
아래는 위에서 등장한 함수들에 대한 설명이다:
# is_a_solution(a, k, input): 현재까지 채운 해가 완전한 해(complete solution) 인지 판단하는 함수이다. 
# construct_candidates(a, k, input, c, nc): 다음 단계에서 시도 가능한 후보들을 생성하는 함수이다. 
#* 현재까지 선택된 해 a[1..k-1]을 기반으로 k번째 위치에서 가능한 모든 선택지를 구한다. 
#* 후보들은 c 배열에 저장하며, 후보의 개수는 변수 nc에 저장한다. 
# process_solution(a, k): 해를 출력하거나 카운트하거나 저장하는 등, 해를 처리하는 함수이다.
위 코드에서 is_a_solution, construct_candidates, process_solution 함수만 바꾸면 원하는 문제를 해결하기 위한 맞춤형 백트래킹 프로그램을 구현할 수 있다.

==Constructing Subsets by Backtracking==

<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>

==각주==