[Python] 백트래킹 (Backtracking) 기법

• 백트래킹 기법
  • 해를 찾는 도중에 '막히면' (즉, 해가 아니면) 되돌아가서 다시 해를 찾아가는 기법
  • 최적화(optimization) 문제와 결정(dicision) 문제를 해결
    • 결정문제 : 문제의 조건을 만족하는 해가 존재하는지 여부 Y/N 답하기
  • 어떤 노드에서 출발하는 경로가 해결책으로 이어지지 않을 것 같다고 결정되면 그 노드의 부모로 되돌아가(Backtracking) 다음 자식 노드로 가기 (Prunning 가지치기)
  • 예 - 미로 찾기, n-Queen 문제, Map coloring, 부분 집합의 합(Subset Sum) 문제 등

def checknode(v): # node
    # 유망하면(어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답의 가능성이 있다면)
    if promising(v):
        if there is a solution at v:
            write the solution
        else:
            for u in each child of v:
                checknode(u)

 

• 백트래킹과 깊이우선탐색과의 차이
  • 깊이우선탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단
  • 어떤 노드에서 출발하는 경로가 해결책으로 이어지지 않을 것 같으면 더 이상 그 경로 따라가지 않음. (Prunning 가지치기)
  • 백트래킹 적용하면 일반적으로 경우의 수가 줄어들지만 최악의 경우 지수함수 시간(Exponential Time)을 요하므로 처리 불가능

•