Backtracking

잃어버린 목도리를 찾기위해 방금전에 있었던 커피숍을 찾아간다. 그곳에서 찾지 못하면 다시 그전에 있었던 식당을 찾아간다. ..... 미로에서 탈출하기 위해 하나의 통로가 막히면 다시 되돌아가서 다른 통로를 시도하여 보고 또다시 막히면 다시 되돌아가서 ...... 이와같이 일상사에서 역추적 (Backtracking) 은 다반사로 일어나다.

Backtracking 은 제약조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기위한 전략이다. 그 문제는 완전한 (complete) 해를 가진 문제이기때문에, 요소들의 순서는 문제되지 않는다. 그 문제는 값이 할당되어야 하는 일련의 변수들로 구성되며, 특별한 제약조건에 민감하다. Backtracking 은 해를 얻기위한 모든 조합을 시도해본다. 그것의 강점은 많은 부분적인 조합을 시도해보지 않아도 된다는 것이며, 그럼으로써 실행시간을 빠르게 할 수 있다. Backtracking 은 combinatorial search 와 밀접하게 관련되어 있다.

구현

기본적으로, Backtracking 의 사상은 올바른 답을 구할 때까지 각각의 가능성을 시도한다는 것이다. 즉 해를 찾기위한 깊이우선 탐색 (Depth First Search) 이다. 탐색도중에, 새로운 탐색이 제대로 작동하지 않게되면, 다른 새로운 탐색이 가능한 선택 포인트 (choice point) 로 backtrack 하여 다음의 새로운 탐색을 시도하게 된다. 새로운 탐색 영역이 고갈되면, 이전의 선택 포인트로 되돌아와서 다음의 새로운 탐색을 시도하게 된다. 더 이상의 선택 포인트가 존재하지 않게되면, 탐색은 실패로 끝난다.

Backtracking 은 보통 각각의 instance 가 하나이상의 변수를 가지고 모든 이용가능한 값을 그 변수에 새롭게 할당하는 재귀함수 (recursive function) 형태를 가지며, 계속되는 재귀호출과 일치하는 (consistent) 값을 유지한다.

Backtracking 은 깊이우선 탐색 (Depth First Search) 와 유사하지만 공간을 덜 사용하며, 딱 한 개의 최신의 해 (solution)를 유지하며, 업데이트한다.

탐색속도를 빠르게 하기위해서, 재귀호출 (recursive call) 하기전에 값이 선택될 때, 그 알고리즘은 할당되지 않은 영역과 다투지 못하도록 그 값을 제거하든가 (전방향 체크 (forward checking)), 이 새로이 할당된 값이 어떤 다른 값들을 배제하는지를 보기위해 모든 제약조건을 체크한다 (제약조건 전파 (constraint propagation)).  

휴리스틱

흔히 휴리스틱 (Heuristic) 은 어떤 과정을 빠르게 만든다. 변수들은 어떤 순서로도 처리될 수 있기 때문에, 휴리스틱은 일반적으로, 가장 제약적인 것 (예를들면 값에 대해 가장 적은 옵션을 가진 것) 을 탐색트리에서는 일찍 가지치기 (prune) 하기 때문에, 그러한 것을 먼저 처리하는 것이 이치에 맞다 (알파베타 가지치기 (Alpha-Beta Pruning)). 어떤 값을 할당할 것인가를 선택할 때, 대부분의 경우 어떤 값이 최소 갯수의 미래의 값들을 제약하는 지를 보기위해 forward checking 의 형태를 사용한다. 이것에 깔려있는 철학은, 해를 더빨리 얻을것 같은 값을 선택한다는 것이다.

섬세한 backtracking 은 가끔 bounding function 을 사용한다. 해를 얻는것이 가능한지를 체크하기 위해, 검사되는 문제에 특별하게 만들어, 모든 할당 단계에서 작동한다. 그래서 간단한 테스트를 통해 확실히 실패할 것 같은 많은 부분적인 해를 즉시 찾아내어 탐색대상의 99 % 까지 잘라낼수 있다. 그것은 가끔 지수적 탐색공간 (exponential search space) 인 모든 단계에서 작동하기 때문에, bounding function 은 계산하기가 아주 쉬워야할 필요가 있다. 그렇지 않으면 그 알고리즘은 더 순탄하지 않을 것이다. 훌륭한 bounding function 은 문제의 규칙들을 다소 유연하게 하여 얻어지는 다른 휴리스틱 함수 (heuristic function) 과 유사한 방법으로 만들어진다.

Backtracking 이 constraint programming language 에 사용될 때, 제약조건에 대한 정보가 업데이트 될 필요가 있는 부가적인 어려움이 있다. 이러한 언어에서는, Prolog 에서 처럼, 간단한 깊이우선 탐색 (Depth First Search) 은 적당한 구현 기술이다. Backtracking을 구현할 때, 특별한 변수의 값의 변화를 기록하기 위해 변수의 궤적 (variable trail)을 유지하는 것이 보통이다. 스마트한 프로그래머라면 선택 포인트 (choice point) 가 없을 때는 두개의 연속적인 변화들 사이의 variable trail 을 만드는 것은 피할것이다. 왜냐하면 backtracking 은 하나의 동작으로서 모든 변화를 지울것이기 때문이다.  

또다른 변형은 변수에 마지막 변화가 있을때 time stamp 를 유지하는 것이다. time stamp 는 선택포인트의 time stamp 와 비교된다. 만일 선택포인트가 변수의 time stamp 보다 늦은 시간을 가지고 있으면, 변수는 선택포인트가 발생하기 전에 변화되었기 때문에, 선택포인트로 backtrack 될때 그것은 불필요한 복귀 (revert) 이다.  

Backtracking 은 Prolog 같은 프로그램 언어의 구현에 사용되며 text parsing 같은 영역에도 사용된다. ...... (Wikipedia : Backtracking)

깊이우선 탐색 (Depth First Search)   Prolog   제약조건 만족 문제 (Constraint Satisfaction Problem)   휴리스틱 (Heuristic)   알고리즘 (Algorithm)

Backtracking Algorithm : 전북대 박순철 교수님 동영상 (★★★)

Backtracking : Visual Prolog 문법

백트랭킹법 (backtracking) : 박정호