역추적검색

역추적검색(Backtracking)은 제약조건 만족 문제(Constraint Satisfaction Problem)를 해결하기 위한 알고리즘이다. 역추적검색은 문제를 해결하기 위해 모든 해를 나열한다.

개요

역추적검색은 제약조건 만족 문제를 해결하기 위해 조합 알고리즘 문제에 대해 가능한 모든 해를 나열하는 것이다. 제약조건 만족 문제는 완전한 해를 가진 문제이고, 요소들의 순서는 문제 되지 않는다. 그 문제는 값이 할당되어야 하는 일련의 변수들로 구성되며, 특별한 제약조건에 민감하다. 부분적인 조합을 시도해 보지 않아도 된다는 장점이 있으며, 조건을 만족할 경우 모든 경우의 수를 찾는 것보다 빠를 수 있다. 역추적검색이라는 용어는 1950년 미국의 수학자 데릭 레머(Derrick Lehmer)에 의해 만들어졌다. 역추적검색은 맞는 답을 구할 때까지 모든 가능성을 시도하는 깊이 우선 탐색이다. 탐색 도중 새로운 탐색이 제대로 작동하지 않으면 다른 새로운 탐색이 가능한 선택 포인트로 역추적해서 다음의 새로운 탐색을 시도한다. 새로운 탐색 영역이 고갈되면 이전의 선택 포인트로 돌아와 다음의 새로운 탐색을 시도한다. 더 이상의 선택 포인트가 존재하지 않으면 탐색은 실패로 끝난다.

참고자료

• 오현석, 〈Backtracking〉, 《개인 블로그》
• Jeong Dowon, 〈(알고리즘) Backtracking 이해하기〉, 《미디엄》

같이 보기

• 알고리즘