해시넷
역추적검색
역추적검색(Backtracking)은 제약조건 만족 문제(Constraint Satisfaction Problem)를 해결하기 위한 알고리즘이다. 역추적검색은 문제를 해결하기 위해 모든 해를 나열한다.
개요
역추적검색은 제약조건 만족 문제를 해결하기 위해 조합 알고리즘 문제에 대해 가능한 모든 해를 나열하는 것이다. 제약조건 만족 문제는 완전한 해를 가진 문제이고, 요소들의 순서는 문제 되지 않는다. 그 문제는 값이 할당되어야 하는 일련의 변수들로 구성되며, 특별한 제약조건에 민감하다. 부분적인 조합을 시도해 보지 않아도 된다는 장점이 있으며, 조건을 만족할 경우 모든 경우의 수를 찾는 것보다 빠를 수 있다. 역추적검색이라는 용어는 1950년 미국의 수학자 데릭 레머(Derrick Lehmer)에 의해 만들어졌다. 역추적검색은 맞는 답을 구할 때까지 모든 가능성을 시도하는 깊이 우선 탐색이다. 탐색 도중 새로운 탐색이 제대로 작동하지 않으면 다른 새로운 탐색이 가능한 선택 포인트로 역추적해서 다음의 새로운 탐색을 시도한다. 새로운 탐색 영역이 고갈되면 이전의 선택 포인트로 돌아와 다음의 새로운 탐색을 시도한다. 더 이상의 선택 포인트가 존재하지 않으면 탐색은 실패로 끝난다. 역추적검색은 보통 각각의 인스턴스가 하나 이상의 변수를 가지고 모든 이용 가능한 값을 그 변수에 할당하는 재귀함수 형태를 가지고, 계속되는 재귀호출과 일치하는 값을 유지한다. 역추적검색은 깊이 우선 탐색과 유사하지만 공간 사용이 덜하며 딱 한 개의 최신 해만 유지하고, 업데이트한다. 탐색 속도를 빠르게 하기 위해서 재귀호출을 하기 전에 값이 선택될 때, 그 알고리즘은 할당되지 않은 영역과 다투지 못하도록 그 값을 제거하는 전방향 체크나 새로이 할당된 값이 어떤 다른 값을 배제하는지 보기 위해 모든 제약조건을 체크하는 제약전파를 사용한다.
각주
참고자료
- 오현석, 〈Backtracking〉, 《개인 블로그》
- Jeong Dowon, 〈(알고리즘) Backtracking 이해하기〉, 《미디엄》
