위키원
역추적검색
역추적검색(Backtracking)은 제약조건 만족 문제(Constraint Satisfaction Problem)를 해결하기 위한 알고리즘이다. 역추적검색은 문제를 해결하기 위해 모든 해를 나열한다.
개요
역추적검색은 제약조건 만족 문제를 해결하기 위해 조합 알고리즘 문제에 대해 가능한 모든 해를 나열하는 것이다. 제약조건 만족 문제는 완전한 해를 가진 문제이고, 요소들의 순서는 문제 되지 않는다. 그 문제는 값이 할당되어야 하는 일련의 변수들로 구성되며, 특별한 제약조건에 민감하다. 부분적인 조합을 시도해 보지 않아도 된다는 장점이 있으며, 조건을 만족할 경우 모든 경우의 수를 찾는 것보다 빠를 수 있다. 역추적검색이라는 용어는 1950년 미국의 수학자 데릭 레머(Derrick Lehmer)에 의해 만들어졌다. 역추적검색은 맞는 답을 구할 때까지 모든 가능성을 시도하는 깊이 우선 탐색이다. 탐색 도중 새로운 탐색이 제대로 작동하지 않으면 다른 새로운 탐색이 가능한 선택 포인트로 역추적해서 다음의 새로운 탐색을 시도한다. 새로운 탐색 영역이 고갈되면 이전의 선택 포인트로 돌아와 다음의 새로운 탐색을 시도한다. 더 이상의 선택 포인트가 존재하지 않으면 탐색은 실패로 끝난다. 역추적검색은 보통 각각의 인스턴스가 하나 이상의 변수를 가지고 모든 이용 가능한 값을 그 변수에 할당하는 재귀 함수 형태를 가지고, 계속되는 재귀 호출과 일치하는 값을 유지한다. 역추적검색은 깊이 우선 탐색과 유사하지만 공간 사용이 덜하며 딱 한 개의 최신 해만 유지하고, 업데이트한다. 탐색 속도를 빠르게 하기 위해서 재귀 호출을 하기 전에 값이 선택될 때, 그 알고리즘은 할당되지 않은 영역과 다투지 못하도록 그 값을 제거하는 전방향 체크(forward checking)나 새로이 할당된 값이 어떤 다른 값을 배제하는지 보기 위해 모든 제약조건을 체크하는 제약전파(constraint propagation)를 사용한다. 넓이 우선 탐색의 경우 상대적으로 많은 메모리가 필요하기 때문에 일반적으로 깊이 우선 탐색을 통하여 구현한다. 역추적검색은 프롤로그(Prolog) 같은 프로그램 언어에 사용되며, 텍스트 파싱(text parsing)에도 사용된다. 역추적검색으로 해결할 수 있는 문제는 여덟 개의 퀸 퍼즐, 스도쿠, 십자말풀이 등이 있다.
휴리스틱
역추적검색을 빠르게 만드는 휴리스틱은 어떤 값을 할당할 것인지 선택할 때 어떤 값이 최소 개수의 미래의 값들을 제약하는지 보는 전방향 체크를 사용한다. 전방향 체크는 해를 더 빨리 얻을 것 같은 값을 선택하는 것이다. 섬세한 역추적검색은 분기 함수(bounding function)를 사용한다. 분기 함수는 해를 얻는 것이 가능한지 확인하기 위해 검사되는 문제에 만들어 모든 할당 단계에서 작동한다. 그래서 간단한 테스트를 통해 실패할 것 같은 부분적인 해를 찾아내 탐색 대상의 99%까지 제외하기도 한다. 분기 함수는 종종 지수적 탁샘공간인 모든 단계에서 작동하기 때문에, 계산하기 쉬워야 한다.
프로그램 코드
다음은 모든 경우 탐색을 위해 깊이 우선 탐색을 사용하고 특정 조건을 isValid()로 처리한 프로그램 코드이다.
package main
import (
"fmt"
)
func main() {
var N int
fmt.Scanf("%d", &N)
grid := make([][]bool, N)
for i := 0; i < N; i++ {
grid[i] = make([]bool, N)
}
fmt.Println(dfs(grid, 0))
}
func dfs(grid [][]bool, x int) int {
if x == len(grid) {
return 1
}
var cnt = 0
for i := 0; i < len(grid); i++ {
if isValid(grid, x, i) {
grid[i][x] = true
cnt += dfs(grid, x+1)
grid[i][x] = false
}
}
return cnt
}
func isValid(grid [][]bool, x, y int) bool {
var diff int
for j := x-1; j >= 0; j-- {
diff++
if grid[y][j] || (y-diff >= 0 && grid[y-diff][j]) || (y+diff < len(grid) && grid[y+diff][j]) {
return false
}
}
return true
}
각주
참고자료
- 오현석, 〈Backtracking〉, 《개인 블로그》
- Jeong Dowon, 〈(알고리즘) Backtracking 이해하기〉, 《미디엄》
같이 보기
| ||||||||||||||||||||||||||||||||||
