Backtracking

Introduction

백트래킹은 구하고자 하는 해를 튜플로 나타내고 튜플에 기준 함수(한정 함수)를 적용했을 때의 결과가 최대치, 최소치 혹은 일정 조건을 만족하게끔 만들어주는 퇴각 검색 기법으로 정의된다. 백트래킹은 해답이 될 수 있는 튜플을 완성해 나아가며 그 과정에서 미완성된 튜플에 한정 함수를 적용하여 해답의 가능성이 없는 튜플들은 더이상 진행시키지 않는 방법을 사용한다. 이때 튜플을 만드는 과정에서 스택(Stack)을 사용하여 한정 함수를 만족하면 push, 만족하지 않으면 pop을 하는 방법을 사용한다. 이런 과정이 퇴각과 전진하는 것과 비슷하다 하여 퇴각 검색 기법(백트래킹, backtracking)이라 불린다.

목표

나올 수 있는 모든 조합의 수를 DFS를 이용한 전체 탐색을 통해 확인

과정

백트래킹은 문제 상황을 상태 공간 트리로 표현한다.

이때 명시적 제약조건은 다음과 같다.

명시적 제약 조건 : 트리의 각 노드는 0 또는 1의 값을 가진다. 이때 i번째 높이의 노드는 i번째 원소의 선택 여부를 나타내며 0은 선택하지 않음, 1은 선택함을 나타낸다.

또한 i번째 높이의 노드는 문제 상황에서 만들어질 수 있는 집합 S 원소이다.

집합 S 예시: S = {ai: 1<=i<=n, a는 자연수}

루트 부터 DFS를 하여 불필요한 탐색을 하지 않고 한정 함수를 만족하는 (x[1], x[2], …, x[n])를 찾는 것을 목표로 한다.
각 노드 s 에 도착할 때마다 루트에서 s까지의 경로 예를 들어 k번째 선택에선 (x[1], x[2], …, x[k])의 튜플이 한정함수를 만족하는지 판단한다.
- 만족할 경우, (x[1], x[2], …, x[k])의 튜플이 한정 함수를 만족한다면 x[k] 노드를 live node이자 e-node로 변경한다.
- 만족하지 않을 경우, 한정함수를 만족하지 않는 다면 T(x[1], … x[k])의 노드들을 더이상 확장하지 않으며 dead node로 만든다.
k < n 일때 x[k]의 자식 노드들인 x[k+1] 들 즉, T(x[1], … x[k])을 탐색한다.
모든 자식 노드를 탐색했다면 현재 노드를 dead node로 변경한다.
진행 도중 한정함수를 만족하는 (x[1], x[2], …, x[n])에 도달하면 정답을 출력한다.
정답이 도출되었거나 모든 노드가 dead 노드가 되었다면 탐색을 종료한다. 이때 정답이 여러개 인 경우에 모든 정답을 찾고 싶다면 모든 노드가 dead 노드가 될때까지 탐색해야 한다.

의사코드

재귀

backtrack(int k){
    /*
        T(x[1], ... x[k-1]) : (x[1], ..., x[k])의 경로가 문제 상태에 속하도록 하는 모든 x[k]의 집합
        의 모든 원소에 대해 반복
    */
    for each x[k] in T(x[1], ..., x[k-1]){
        /*
            (x[1], x[2], ..., x[k])의 경로에 대하여 한정 함수를 만족하면 x[k]를 live node이자 E-node로 만듬
        */
        if(B_k(x[1], x[2], ..., x[k]) == true){
            /*
                (x[1], x[2], ..., x[k])가 한정함수를 만족하고 정답 노드라면 결과를 생성
            */
            if(x[1], x[2], ... x[k] 가 정답 노드라면 결과 out)
                
            /*
                k가 n보다 작으면 x[k]의 자식 노드들의 활성화를 위해 backtrack(k+1) 호출
            */
            if(k<n) backtrack(k+1);
            /*
                backtrack(k+1)를 통해 x[k]의 모든 자식 노드가 생성되었으므로
                x[k]를 dead node로 만듬
            */
        }
        
    }
}

반복문

ibacktrack(int n){
    int k = 1;
    while(k != 0){
        /*
            T(x[1], ... x[k-1]) : (x[1], ..., x[k])의 경로가 문제 상태에 속하도록 하는 모든 x[k]의 집합
            의 시도하지 않은 x[k]에 대해 (x[1], x[2], ..., x[k])가 한정함수를 만족하면 x[k]를 live node이자 E-node로 만듬
            이때 T(x[1], ... x[n])은 공집합이므로 바로 else로 진입함
        */
        if(there remains an untried x[k] in T(x[1], x[2], ... , x[k-1])
            and B_k(x[1], ... , x[k]) == true){
            if(x[1], ..., x[k] 가 정답 노드라면 결과 out)
            /*
                x[k]의 자식 노드들의 활성화를 위해 k를 증가
            */
            k = k + 1;
        }else{
            /*
                더 이상 확인할 자식이 없거나 한정함수를 만족하는 자식이 없다면 x[k]를 dead node로 만듬
            */
            k = k - 1;
        }
    }
}

ref. https://chanhuiseok.github.io/posts/algo-23/

2022 87

Kim Jisong

Backtracking

Introduction

목표

과정

의사코드

2022