퇴각검색

퇴각검색(영어: backtracking, 한국어: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다.

설명[편집]

문제가 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다. 이런 문제는 변수 집합으로 이뤄지는데, 한정 조건을 구성하려면 각각의 변수들은 값이 있어야 한다. 퇴각검색은 모든 조합을 시도해서 문제의 해를 찾는다. 이것이 장점이 될 수 있는 이유는 퇴각검색 구현 방법들이 많은 부분 조합들을 배제하기 때문이다. 결국 풀이 시간이 단축된다.

퇴각검색은 조합 탐색과 큰 관계가 있다.

구현[편집]

주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 깊이 우선 탐색을 사용한다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아간다. 시도해보지 않은 다른 해결 방법이 있으면 시도한다. 해결 방법이 더 없으면 더 이전의 분기점으로 돌아간다. 모든 트리의 노드를 검사해도 답을 못 찾을 경우, 이 문제의 해결책은 없는 것이다.

퇴각검색은 보통 재귀 함수로 구현된다. 재귀로 파생된 해결 방법은 하나 이상의 변수가 필요한데 , 이것은 현재 시점에서 적용할 수 있는 변수값들을 알고 있다. 퇴각검색은 깊이 우선 탐색과 대략 같으나 기억 공간은 덜 차지한다. 현재의 상태를 보관하고 바꾸는 동안만 차지한다.

탐색 속도를 높이기 위해, 재귀 호출을 하기 전에 시도할 값을 정하고 조건(전진 탐색의 경우)을 벗어난 값을 지우는 알고리즘을 적용할 수 있다. 아니면 그 값을 제외한 다른 값들을 탐색할 수도 있다.

휴리스틱[편집]

몇몇 휴리스틱은 처리 속도를 높이려고 쓰인다. 변수는 어떤 순서로도 처리할 수 있으므로, 보통 효율적인 방법은 가장 한정된 조건을 먼저 시도하는 것이다(예를 들어 선택 사항이 적은 것). 이런 가지치기는 탐색 트리를 작게 한다(최소의 비용으로 최대의 결과를 얻는다)

조건을 검사하려고 값을 선택할 때, 많은 구현 방법은 조건을 벗어난 값을 빼려고 전진 탐색을 쓴다. 이를 예상하려고 다음 방법을 쓸 수 있다.

해결책이 가장 있을 만하거나,
해결책이 가장 없을 만한 것을 찾는다.

복잡한 퇴각검색을 구현하려고 종종 경계값 검사 함수를 쓴다. 이 검사는 현재의 부분 해결책으로 답을 얻을 수 있는지 확인한다. 부분적인 해결책이 있는지 확인하는 경계값 검사는 나은 탐색 방법이 될 수 없다. 왜냐하면 탐색 중에 때때로, 가능한 모든 조건에 대한 경계 검사의 연산 비용을 최소로 해야 하는데, 그렇지 못하면 알고리즘의 효율성은 그다지 향상되지 않는다. 효율적인 경계 검사 함수는 조건을 점점 느슨하게 하는 휴리스틱 함수처럼 만든다.

퇴각검색이 제한 조건이 많은 프로그래밍 언어에서 사용될 경우, 이런 조건들 때문에 오버헤드가 발생한다. 자체적으로 제한 조건 해결자를 사용하여, 프로그램을 수정할 필요가 있다. 이런 언어일 경우, 간단한 깊이 우선 탐색은 쓸만한 방법이며, 플래너나 프롤로그가 해당한다.

덧붙여서 되돌릴 때 복구할 값들을 최소로 유지하고자, 퇴각검색은 변수 이력(variable trail)을 갖는다. 이것은 변수 값이 바뀐 내역을 보관한다. 효율적인 퇴각검색은 분기점이 없을 때의 값 변화에 대한 내역은 제거하려고 한다. 이는 분기점이 없는 조건을 하나의 연산으로 간주하고 이와 관련된 값 변화를 지워서 구현된다.

변수 이력을 대체하는 다른 방법은 변수에 마지막으로 값이 적용되었을 때의 타임 스탬프를 저장하는 것이다. 타임 스탬프는 분기점의 타임 스탬프와 비교된다. 변수의 타임 스탬프보다 분기점과 연관된 시간이 늦을 경우, 분기점으로 복귀했을 때 변수 값을 복구할 필요가 없다. 분기점에 오기 전에 값이 바뀌었기 때문이다.

적용[편집]

퇴각검색은 플래너나 프롤로그 같은 프로그래밍 언어를 구현하는 데 쓰인다. 혹은 구문 분석 분야에도 적용된다. 행위자 모델 개발에 주로 쓰이는 인공지능에 퇴각검색을 적용하려는 토론이 있었다.