[Advanced] 5. 백트래킹 - 이론편

백트래킹

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

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 문제

• nxn의 체스판에 n개의 퀸들이 놓여 있다.
• 이들이 서로를 위협하지 않도록 배치하라.
  • 퀸은 상하좌우의 직선방향, 대각선 방향으로 움직일 수 있다.

 

8-Queen 문제

후보 해의 수 : 64C8 = 4,426,165,368
실제 해의 수 : 92개

4-Queen 문제로 축소

퀸들은 같은 행에 위치할 수 없음
→ 모든 경우의 수 : 4x4x4x4 = 256

 

 

트리의 루트로부터 당첨이라는 단말 노드까지 가는 경로 찾기

1.  루트에서 갈 수 있는 노드 선택
2. 꽝 노드까지 도달하면 최근의 선택으로 되돌아와서 다시 시작
3. 더 이상의 선택지가 없다면 이전의 선택지로 돌아가서 다른 선택
4. 루트까지 돌아갔을 경우 더 이상 선택지가 없다면 찾는 답이 없음

 

부분 집합

어떤 원소 집합의 원소 개수가 n인 경우, 부분 집합의 개수는 2^n이다.
n개의 리스트를 만들어 각각의 원소가 부분 집합에 포함되는 경우 1, 그렇지 않은 경우를 0으로 둘 수 있다.

부분 집합 상태 공간 트리

 

깊이 우선 탐색으로 모든 부분 집합 생성하는 알고리즘

def subset(a, k, n): # a : 집합에 대한 비트 표현, k : 선택한 횟수, n : 모든 선택수
    if k==n:
    	process_solution(a,n)
    else:
    	a[k] = 0 # 선택안함
        subset(a, k+1, n)
        a[k] = 1 # 선택함
        subset(a, k+1, n)

 

 

순열

순열 상태 공간 트리

노드 방문 시마다 저장 내용은 원소를 가리키는 인덱스를 저장 → 순서가 됨
높이가 증가하면서 선택지의 수 하나씩 감소

순열 생성 알고리즘

def permutation(order, k, n): # order : 순열의 순서를 저장,  k : 선택한 횟수, n : 모든 선택수
    if k == n:
        print_order_array(order, n)
    else:
        check = [False]*n  # [F, F, F, F]
        for i in range(k):
            check[order[i]] = True
            
        for i in range(n):
            if check[i] == False:
                order[k] = i
                permutation(order, k+1, n)

 

 

동전 거스름돈 문제

상태 공간 트리

거스름돈 문제 알고리즘

def CoinChange(choice, N, money):
    global best
    if best <= N:
        return
    elif money == 0:
        best = N
    else:
        for i in range(len(coin)):
            if money - coin[i] >= 0:
                choice[N] = coin[i]
                CoinChange(choice, N+1, money-coin[i])