백트래킹 (backtracking)

백트래킹 (backtracking)

퇴각 검색

모든 조합을 시도해서 문제의 해를 찾는다. -> 완전 탐색

해를 얻을 때까지 모든 가능성을 시도한다.

모든 가능성은 하나의 트리(상태 공간 트리)6처럼 구성할 수 있으며, 가지(선택지) 중에 해결책이 있다.

여러 가지(선택지)들이 존재한는 상황에서 하나의 가지를 선택한다.

선택이 이루어지면 새로운 선택지들의 집합이 생성된다.

이런 선택을 반복하면서 최종 상태에 도달한다.

보통 재귀 함수로 구현된다.

N - Queen 문제

완전 탐색할 경우 수 많은 후보 해 중에서 유망하지 않은 해는 방문하지 않는다.

당첨 리프 노드 찾기

루트에서 갈 수 있는 노드를 선택한다.

꽝 노드까지 도달하면 최그늬 선택으로 되돌아와서 다시 시작한다.

더 이상 선택지가 없다면 이전의 선택지로 돌아가서 다른 선택을 한다.

루트까지 돌아갔을 경우 더 이상 선택지가 없다면 찾는 답이 없다.

백트래킹 기법

어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식도드로 간다.

유망(promising)하다

• 어떤 노드를 방문하였을 떄 그 노드를 포함한 경로가 해답이 될 수 있으면 유망하다고 한다.

가지치기(prunung)

• 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다.

1. 상태 공간 트리의 깊이 우선 검색을 실시한다
2. 각 노드가 유망한지를 점검한다.
3. 만일 그 노드가 유망하지 않다면, 그 노드의 부모 노드로 돌아가서 다른 노드로의 검색을 계속한다.

백트래킹과 완전탐색(DFS) 차이

어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄임(Pruning, 가지치기)

완전 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단한다.

완전 탐색을 가하기에는 경우의 수가 너무 많다. (ex, N! 가지 경우의 수)

백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만, 최악의 경우 여전히 지수함수시간(Exponential)을 요하므로 처리 불가능할 수 있다.

가지치기가 만능은 아니다!

가지치면 안되는 가지치기 -> 해를 잃어버림

가지치기의 상황이 상태공간트리의 리프노드에서 일어날 경우 -> 가지치기 효과 없음.

백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것

답이 될만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가치지기

주로 문제풀이에서 DFS로 모든 경우의 수를 탐색하는 과정에서, 조건으로 답이 절대 될 수 없는 상황을 정의하여 체크

그러한 상황일 경우 탐색을 중지, 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현