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==
해당 문단에서는 어진 집합의 모든 부분집합(2<sup>2</sup>개)을 백트래킹을 이용해서 생성하는 방법에 대해 설명한다. 즉, {1, 2, 3, …, n} 같은 집합이 있을 때 가능한 모든 조합(포함/비포함)을 탐색하는 문제에 대해서 다룬다. 이를 해결하기 위해서 각 원소 a[i]는 True/False 값을 가지는 크기가 n인 배열 a를 만들 수 있다. 이 경우 하나의 배열 a는 하나의 부분집합을 표현할 수 있다. 예를 들어, a = [True, False, True]는 부분집합 {1, 3}을 의미한다. 이를 백트래킹 표현으로 보면:
# 각 단계 k마다 후보 집합 S<sub>k</sub> = (True,False)
# 해가 완성되는 시점은 k가 n 이상, 즉 모든 원소에 대해 포함 여부를 결정했을 때이다.
결과적으로 가능한 조합 2<sup>n</sup>개가 모두 생선된다.

===Subset Generation Tree / Order===
Figure는 부분집합을 생성하는 탐색 트리(Generation Tree)를 시각화한 것이다. 해당 트리는 루트에서 시작해서 각 단계마다 “포함한다”또는 “포함하지 않는다”의 두 가지 선택지를 가진다. 이때 트리의 깊이는 집합의 원소 개수 n과 같으며, leaf 노드는 완성된 부분집합을 의미한다.  

이러한 원리를 백트래킹 코드에 대해 적용할 수 있다. 이를 위해 아래와 같은 조건을 이해하자:
* 길이가 n인 True/False 벡터를 통해 부분집합을 표현.
* 각 단계의 후보 집합 S<sub>k</sub>=(True,False).
* 모든 원소를 처리했을 때 (k == n) → 완성된 해.

===Constructing Subsets===
이를 아래와 같이 적용할 수 있다:
<syntaxhighlight lang="c">
int is_a_solution(int a[], int k, int n) {
    return (k == n);
}
</syntaxhighlight>
위는 트리 깊이가 n단계가 되었는지를 확인하여 모든 원소를 처리했는가에 대해서 확인한다.
<syntaxhighlight lang="c">
void construct_candidates(int a[], int k, int n, int c[], int *nc) {
    c[0] = true;
    c[1] = false;
    *nc = 2;
}
</syntaxhighlight>
각 단계마다 가능한 선택지는 항상 두 가지(True/False)이므로 이에 맞게 설정한다.
<syntaxhighlight lang="c">
void process_solution(int a[], int k, int input) {
    int i;
    printf("{");
    for (i = 1; i <= k; i++) {
        if (a[i] == true) printf(" %d", i);
    }
    printf(" }\n");
}
</syntaxhighlight>
위는 주어진 모든 부분 집합을 출력하는 코드이다. 이때 출력 대신 다른 검사를 수행하여 알고리즘의 기능을 확장할 수도 있다.
<syntaxhighlight lang="c">
void generate_subsets(int n) {
    int a[NMAX];   /* solution vector */
    backtrack(a, 0, n);
}
</syntaxhighlight>
위는 전체 프로그램을 실제로 실행시키는 함수이다.

==Constructing Permutations by Backtracking==
해당 문단에서는 백트래킹 기법을 이용하여 모든 순열을 생성하는 방법에 대해 설명한다. 순열(permutation)이란 n개의 원소를 서로 다른 순서로 배열하는 모든 경우의 수를 의미한다. 예를 들어, {1, 2, 3}의 순열은 123, 132, 213, 231, 312, 321이다. 이때 n개의 원소로 만들 수 있는 순열의 개수는 n!(팩토리얼)이다. 

순열을 표현하기 위해서는 a라는 배열을 만들어야 하며, 이때 a[i]는 순열의 i번째 자리에 올 숫자를 나타낸다. 따라서 각 a[i]는 아직 사용되지 않은 숫자 중 하나를 선택해야 한다. 이를 백트래킹 알고리즘의 일반 형태로 표현하면:
 <math>S_k = \{1, 2, ..., n\} - v</math>
즉, 아직 선택되지 않은 원소들의 집합이며, 이에 따라 완전한 해답은 k가 n 이상일 때 얻을 수 있다. Figure 는 순열이 만들어지는 과정을 시각적으로 보여준다. 이는 루트 노드에서 시작하여, 가능한 후보들 중 하나를 선택하며 아래쪽으로 진행함에 따라 더욱 완전한 순열을 만들어 간다. 마지막 leaf 노드들은 완전한 순열들인 {123, 132, 213, 231, 312, 321}을 나타낸다. 

===Constructing All Permutations===
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>

==각주==