4. 백트래킹

백트래킹

해를 찾는 도중에 막히면 되돌아가서 해를 다시 찾는 기법

1. 상태 공간 트리에 대한 깊이 우선 탐색 실시
2. 방문하는 노드가 유망한지 여부 점검
3. 만일 선택한 노드가 유망하지 않을 경우, 해당 노드의 부모 노드로 돌아가서 검색 계속 진행

최적화 문제와 결정 문제를 해결할 수 있음

결정 문제	문제의 조건을 만족하는 해가 존재하는지를 yes/no로 답하는 문제	미로찾기, n-Queen, Map coloring, 부분 집합의 합 문제 등
최적화 문제	문제의 조건을 만족하는 최대/최소 해를 찾는 문제	미로찾기에서 최단경로 문제, 원소의 개수가 최대인 부분 집합을 찾는 문제

 

상태 공간 트리

• 해를 찾기 위한 선택의 과정을 트리로 표현
• 트리의 내부 노드는 최종 상태로 가는 중간 상태를 나타냄
• 트리의 단말 노드는 하나의 후보해에 대한 최종 상태가 됨
• 상태 공간 트리를 탐색하는 것은 모든 후보해들을 탐색하는 것
• 트리를 깊이 우선 탐색하는 방법이 백트래킹 알고리즘의 기본 형태

 

백트래킹과 깊이 우선 탐색과의 차이

백트래킹 기법	깊이 우선 탐색
- 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 가지 않음 - 가지치기로 불필요한 경로 조기에 차단 - 일반적으로 경우의 수가 줄어들지만, 최악의 경우 지수함수 시간을 필요로 함	- 모든 경로 추적 - 경우의 수가 너무 많은 경우 처리 불가능 - N! 가지의 경우의 수 문제는 처리 불가능

 

일반적인 백트래킹 알고리즘 절차(수도 코드)

def checknode(v):
    if promising(v):
        if there is a solution at v:
          write the solution
        else:
          for u in each child of x:
              checknode(u) # 재귀호출

 

 

백트래킹 문제 예시

n-Queen 문제

 

동전 거스름돈 문제