[알고리즘] 9주차

7장. 퇴각검색과 분기한정법

목차 

1. 퇴각검색법 개요

2. N-Queen 문제

3. 부분집합의 합

4. 0/1 배낭 문제

5. 분기한정법 개요

 

---

01. 퇴각검색법 개요

@퇴각검색 Backtracking

- 주어진 조건을 만족하는 최적해 또는 해들의 집합을 찾는 문제를 대상으로 함

- 해는 주로 n개의 요소로 구성된 순서리스트로 나타낸다.(n-tuple, x_1, ... , x_n)

- 욕심쟁이법 등으로 해결할 수 없는 문제에 적용함(지수 시간이 소요되는 문제)

 

 

대표 예제 문제 > 4-Queens 문제

문제조건 : 4바이4 로 구성된 행렬이 주어지고 같은 행, 같은 열, 같은 대각선 상에 없도록 Queen을 놓는다.

해의 표현 : (x1, x2, x3, x4) = (2, 4, 1, 3) ~> 첫행에 두번째 칸, 두번째 행에 4번째 칸... 마지막 행에 3번째 칸

이 해의 공간의 크기를 구하는 방식 : 첫행에 4가지 숫자(1,2,3,4)모두 올 수 있고, 다음 행으로 내려갈수록 올 수 있는 숫자가 하나 사라짐( 같은 숫자가 올 수 없으므로) 따라서 4 X 3 X 2 X 1 = 4!

=> N! (해 공간의 크기)

 

이런 해 공간의 크기를 상태 공간 트리(State Space Tree)로 구할 수 있다.

 

@상태 공간 트리(State Space Tree) >> 퇴각검색 알고리즘 동작 방식

 

백트랙킹은 해를  찾는 도중 해가 아니여서 막히면 되돌아가서 다시 해를 찾는 기법이다.(최적화 문제, 결정 문제)

DFS 깊이 우선 탐색(또는 BFS 너비우선)을 사용해서 조건에 맞지 않으면 중단하고 이전으로 돌아가서 다시 확인하는 것을 반복하면서 원하는 값을 찾는다.

 

1) 깊이 우선 탐색(비교군) : 가능한 모든 경로를 탐색함(불필요한 경우까지), n! 가지의 경우의 수를 가진 문제는 처리가 불가능함

2) 유망 함수 promising function : 탐색을 효율적으로 수행하기 위해 각 노드에서 수행되는 검사, 탐색이 필요없는 부분을 제외하여 탐색을 중지시킨 후 이전으로 돌아가서 다른 경우를 탐색. >> 실제 구현 시 모든 경우의 수를 '상태공간트리'로 표현
=> 가지치기 : 불필요한 경로를 조기에 차단(경우의 수 감소), 가지치기가 어떻게 되는지에 따라서 효율성이 결정됨.

 

상태공간트리

3) 퇴각검색 backtracking : 상태 공간 트리를 dfs방식으로 탐색,유망함수사용

backtracking의 유망성?

>> 어떤 노드가 해가 될 만한지 판단한 후 유망하지 않다고 결정되면, 그 이전 부모노드로 backtracking하여 다음 자식 노드로 돌아감

>> 해가 될 가능성이 있다 : '유망하다 (promising)' , 유망하지 않은 노드에 가지 않는 것 : '가지치기(pruning)'

 

 

깊이 우선 탐색 (DFS)를 사용하여 4-Queen 문제의 유망 함수를 구현하였다.

 

퇴각검색 알고리즘의 일반적인 구성을 수도코드로 나타내었다. 

DFS 방식을 선택함

void checknode(node v) {
    if (promising(v)) {              // 현재 노드 v가 유망(promising)하면
        if (there is a solution at v) // v가 하나의 해(solution)를 나타내면
            write the solution;       // 해를 출력한다
        else
            for (each child u of v)   // v의 각 자식 노드 u에 대해
                checknode(u);         // 재귀적으로 checknode(u)를 호출한다
    }
}