위키원
역추적검색
역추적검색(Backtracking)은 제약조건 만족 문제(Constraint Satisfaction Problem)를 해결하기 위한 알고리즘이다. 역추적검색은 문제를 해결하기 위해 모든 해를 나열한다.
개요
역추적검색은 제약조건 만족 문제를 해결하기 위해 조합 알고리즘 문제에 대해 가능한 모든 해를 나열하는 것이다. 역추적검색은 해결 방법이 될 수 있는 튜플을 완성하며 그 과정에서 미완성된 튜플에 한정 함수를 적용해 해답의 가능성이 없는 튜플은 진행하지 않는 방법을 사용한다. 역추적검색의 목표는 상태 공간 트리를 깊이 우선 탐색(DFS)을 통해 해결 상태에 도달하는 데 있어 불필요한 탐색을 하지 않는 것이다. 제약조건 만족 문제는 완전한 해를 가진 문제이고, 요소들의 순서는 문제 되지 않는다. 그 문제는 값이 할당되어야 하는 일련의 변수들로 구성되며, 특별한 제약조건에 민감하다. 부분적인 조합을 시도해 보지 않아도 된다는 장점이 있으며, 조건을 만족할 경우 모든 경우의 수를 찾는 것보다 빠를 수 있다. 역추적검색이라는 용어는 1950년 미국의 수학자 데릭 레머(Derrick Lehmer)에 의해 만들어졌다. 역추적검색은 맞는 답을 구할 때까지 모든 가능성을 시도하며, 트리를 검사하기 위해 주로 깊이 우선 탐색을 사용한다. 역추적검색은 문제 상황을 상태 공간 트리로 표현하고, 루트부터 깊이 우선 탐색을 한다. 노드마다 한정 함수를 만족하는지 판단하고, 오답이면 이전 분기점으로 돌아가 시도해 보지 않은 방법이 있으면 시도하고, 해결 방법이 없으면 더 이전 분기점으로 돌아간다. 모든 트리의 노드를 검사해도 답을 못 찾을 경우 이 문제의 해결 방법은 존재하지 않는 것이다. 역추적검색은 보통 각각의 인스턴스가 하나 이상의 변수를 가지고 모든 이용 가능한 값을 그 변수에 할당하는 재귀 함수 형태를 가지고, 계속되는 재귀 호출과 일치하는 값을 유지한다. 역추적검색은 깊이 우선 탐색과 유사하지만 공간 사용이 덜하며 딱 한 개의 최신 변수만 유지하고, 업데이트한다. 탐색 속도를 빠르게 하기 위해서 재귀 호출을 하기 전에 값이 선택될 때, 그 알고리즘은 할당되지 않은 영역과 다투지 못하도록 그 값을 제거하는 전방향 체크(forward checking)나 새로이 할당된 값이 어떤 다른 값을 배제하는지 보기 위해 모든 제약조건을 체크하는 제약전파(constraint propagation)를 사용한다. 넓이 우선 탐색의 경우 상대적으로 많은 메모리가 필요하기 때문에 일반적으로 깊이 우선 탐색을 통하여 구현한다. 역추적검색은 프롤로그(Prolog) 같은 프로그램 언어에 사용되며, 텍스트 분석(text parsing)에도 사용된다. 행위자 모델 개발에 쓰이는 인공지능에 적용하려는 움직임도 있었다. 역추적검색으로 해결할 수 있는 문제는 N-Queen 퍼즐, 스도쿠, 십자말풀이 등이 있다.[1][2][3]
특징
상태 공간 트리
상태 공간 트리는 찾는 해를 반드시 포함하는 트리이다. 해가 존재한다면 그것은 이 트리의 어떤 한 노드에 해당하며, 이 트리를 탐색하면 해를 구할 수 있다. 상태 공간 트리의 모든 노드를 탐색해야 하는 것은 아니며, 트리를 그리거나 데이터 구조로 만든다는 뜻이 아니다. 상태 공간 트리는 개념적이고 논리적인 것으로, 이런 트리를 개념적으로 염두하고, 실제로는 이 트리의 노드를 탐색하는 코드를 만들어야 한다.[4]
깊이 우선 탐색
역추적검색은 깊이 우선 탐색을 통해 가능한 노드를 탐색한다. 깊이 우선 검색은 가능한 모든 경로를 탐색하기 때문에, 불필요한 경로를 사전에 차단하지 않으면 경우의 수를 줄이지 못해 처리 시간이 길어진다. 넓이 우선 탐색은 상대적으로 많은 메모리가 필요하기 때문에 깊이 우선 탐색을 통하여 사용한다.[5]
휴리스틱
역추적검색을 빠르게 만들기 위해 몇몇 휴리스틱을 사용했다. 역추적검색은 변수는 어떤 순서로도 처리할 수 있으므로 보통 효율적인 방법은 가장 한정된 조건을 먼저 시도한다. 가지치기는 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 역추적검색은 지금의 경로가 유망성이 없다고 판단하면 그 경로를 더 탐색하지 않고 돌아오는데, 이를 통해 불필요한 경로를 조기에 차단해 경우의 수가 줄어들지만 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능하다.[5] 이런 가지치기는 탐색 트리를 작게 해 최소의 비용으로 최대의 결과를 얻을 수 있다. 또, 어떤 값을 할당할 것인지 선택할 때 어떤 값이 최소 개수의 미래의 값들을 제약하는지 보는 전방향 체크를 사용한다. 전방향 체크는 해를 더 빨리 얻을 것 같은 값을 선택하는 것이다. 해결 방법이 가장 있을 것 같거나 가장 없을 것 같은 것을 찾아 탐색 트리를 작게 만든다. 섬세한 역추적검색은 분기 함수(bounding function)를 사용한다. 분기 함수는 해를 얻는 것이 가능한지 확인하기 위해 검사되는 문제에 만들어 모든 할당 단계에서 작동한다. 그래서 간단한 테스트를 통해 실패할 것 같은 부분적인 해를 찾아내 탐색 대상의 99%까지 제외하기도 한다. 분기 함수는 종종 지수적 탐색공간인 모든 단계에서 작동하기 때문에, 계산하기 쉬워야 한다. 되돌릴 때 복구할 값들을 최소로 유지하기 위해 역추적검색은 변수 이력을 사용한다. 변수 이력은 변수 값이 바뀐 내역을 보관해, 분기점이 없을 때 값 변화에 대한 내역을 제거한다. 이는 분기점이 없는 조건을 하나의 연산으로 간주하고, 이와 관련된 값 변화를 지워서 구현한다. 변수 이력을 대체하는 방법은 변수에 마지막으로 값이 적용됐을 때의 타임 스탬프를 저장해 분기점의 타임 스탬프와 비교하는 것이다. 변수의 타임 스탬프보다 분기점의 타임 스탬프가 최근일 경우, 분기점으로 복귀했을 때 변숫값을 복구하지 않아도 된다.[6]
유사 코드
문제의 특정 클래스에 역추적을 적용하려면 특정 문제 인스턴스에 대한 데이터 P와 root, reject, act, first, next, output 등 6개의 절차 매개 변수를 제공해야 한다.
- root(P)는 검색 트리의 루트에 있는 부분 후보자를 반환한다.
- reject(P, c)는 부분 후보 c가 완료할 가치가 없는 경우에만 true를 반환한다.
- act(P, c)는 c가 P의 해결책이면 true를 반환하고, 그렇지 않으면 false를 반환한다.
- first(P, c)는 후보 c의 첫 번째 확장을 생성한다.
- next(P)는 후보의 다음 대체 확장자를 생성한다.
- output(P, c)은 응용 프로그램에 적합한 P의 c 해결책을 사용한다.
다음은 역추적검색의 작동 방식을 표현한 유사 코드이다.
procedure bt(c) is
if reject(P, c) then return
if accept(P, c) then output(P, c)
s ← first(P, c)
while s ≠ NULL do
bt(s)
s ← next(P, s)[7]
예시
N-Queen 퍼즐은 크기가 N*N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.[8] 퀸은 가로, 세로, 대각선으로 이동할 수 있는 체스 말이다. 그러므로 N-Queen 퍼즐은 하나의 퀸을 기준으로 가로, 세로, 대각선에 다른 퀸이 없어야 한다는 제약조건이 있는 문제가 된다. 모든 경우의 수는 N^N으로 N이 10개라면 경우의 수는 100억 개가 된다. 역추적검색을 사용하면 한 줄에 퀸을 두었으면 다음 줄 가능한 자리에 퀸을 두고, 또 다음 줄 가능한 자리에 퀸을 둔다. 이 과정을 반복해 N개의 퀸을 배치했으면 카운트를 증가시키고, 직전으로 상태를 되돌린다. 그리고 N 번 줄에서 모든 가능성을 시도한다. 만약 해결책을 찾지 못하면 N-1 번 줄에서 다음 가능한 자리에 퀸을 두고 N 번 줄에서 다시 모든 가능성을 시도한다. N-1 번 줄의 모든 경우를 시도했다면 N-2 번 줄에서 퀸을 다음 자리로 옮기고 다시 모든 과정을 반복한다. 이 과정이 역추적검색이다.[2]
각주
- ↑ 오현석, 〈Backtracking〉, 《개인 블로그》
- ↑ 2.0 2.1 Jeong Dowon, 〈(알고리즘) Backtracking 이해하기〉, 《미디엄》, 2018-12-29
- ↑ adcee, 〈(알고리즘) 백트래킹(Backtracking)이란? (feat. DFS, 기준함수, sum of subset)〉, 《티스토리》, 2019-04-21
- ↑ Namjun Kim, 〈(Algorithm) 2-6. Recursion 응용 3 - N Queens Problem(Backtracking)〉, 《티스토리》, 2018-01-14
- ↑ 5.0 5.1 ChanBLOG, 〈알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제〉, 《깃허브》, 2020-02-14
- ↑ 퇴각검색 위키백과 - https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89
- ↑ Backtracking Wikipedia - https://en.wikipedia.org/wiki/Backtracking
- ↑ 만재송, 〈(알고리즘) 백트래킹 (Backtracking) 알고리즘〉, 《티스토리》, 2018-02-25
참고자료
- 퇴각검색 위키백과 - https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89
- Backtracking Wikipedia - https://en.wikipedia.org/wiki/Backtracking
- 오현석, 〈Backtracking〉, 《개인 블로그》
- Jeong Dowon, 〈(알고리즘) Backtracking 이해하기〉, 《미디엄》, 2018-12-29
- adcee, 〈(알고리즘) 백트래킹(Backtracking)이란? (feat. DFS, 기준함수, sum of subset)〉, 《티스토리》, 2019-04-2
같이 보기
| ||||||||||||||||||||||||||||||||||
