• 해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 기법
  • 최적화(optimization)문제와 결정(decision) 문제를 해결할 수 있다.
  • 결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' or 'no'로 답하는 문제
  • 미로 찾기 / N-Queen / Map coloring / 부분집합의 합(Subset Sum) 문제 등

  • 최적해를 찾는 문제 : 가능한 모든 경우, 즉 모든 후보해를 조사해야 한다.

  • 일반적으로 모든 경우의 수를 체계적으로 따지는 방법으로 백트래킹을 사용

  • 상태공간 트리(그래프)로 모델링 : DFS, BFS

  • 모든 가능한 경우는 조합적 문제와 연관 : 부분집합, 순열, 조합, 2^n, n!

  • 완전탐색은 시간이 느리다.

  • 시간을 줄이려는 노력

    • Backtracking(pruning) : 상태공간 트리 탐색 + 가지치기
    • Dynamic programmming(memoization) : 부분 문제간의 관계 → 점화식을 구해 중복 계산 제거

  • 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않는 상황

  • 이를 유망(promising)하지 않다고 하며 이 경로를 더 이상 고려하지 않는 것을 가지치기(Pruning)라고 한다.

  • 이를 통해 시도의 횟수를 줄인다.

  • 깊이우선탐색은 모든 경로 추적, 백트래킹은 불필요한 경로를 조기에 차단

  • N이 커지면 커질수록 깊이우선탐색은 처리 불가

  • 백트래킹도 최악의 경우에는 지수함수 시간(Exponential Time)을 필요로 한다는 한계


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)

  • powerset : 어떤 집합의 공집합과 자기자신을 포함한 모든 부분집합
  • 집합의 원소가 n일 경우 부분집합의 개수는 2**n개

  • 각 원소가 부분집합에 포함되었는지를 loop을 이용하여 확인 후 부분집합 생성
def backtrak(a, k, input):
    global MAXCANDIDATES
    c = [0] * MAXCANDIDATES
 
    if k == input:
        process_solution(a, k)
    else:
        k += 1
        ncandidates = construct_candidates(a, k, input, c)
        for i in range(ncandidates):
            a[k] = c[i]
            backtrack(a, k, input)
 
def construct_candidaates(a, k, input, c):
    c[0] = True
    c[1] = False
    return 2
 
MAXCANDIDATES = 2
NMAX = 4
a = [0] * NMAX
backtrack(a, 0, 3)

부분집합의 항목 합계를 구하는데, 아직 항목을 다 확인하지 않았음에도 원하는 합계에 도달하거나 넘겼을 경우, 이후 항목의 여부는 확인할 필요가 없기 때문에 실행을 진행하지 않고 탈출한다. 백트래킹이 경제적일 수 있는 이유이다. 그 구현을 밑에서 살펴보자.

# i-1 원소까지 고려한 합 s, 찾으려는 합 t
def f(i, N, s, t):
    cnt += 1
    if s == t:                 # i-1 원소까지의 합이 찾는 값인 경우
        for j in range(N):
            if bit[j]:
                print(a[j], end=' ')
        print()
    elif i == N:               # 합이 덜 됐는데 모든 원소에 대한 고려가 끝난 경우
        return
    elif s > t:                # 남은 원소를 고려할 필요가 없는 경우
        return
    else:                      # 남은 원소가 있고 s < t인 경우
        bit[i] = 1
        f(i+1, N, s+a[i], t)   # i 인덱스의 값을 합에 포함
        bit[i] = 0
        f(i+1, N, s, t)        # i 인덱스의 값을 합에 미포함
 
N = 10
t = 10
a = [x for x in range(1, N+1)]
bit = [0]*N
f(0, N, 0, t)

# i-1 원소까지 고려한 합 s, 찾으려는 합 t
def f(i, N, s, t, rs):
    cnt += 1
    if s == t:                          # i-1 원소까지의 합이 찾는 값인 경우
        for j in range(N):
            if bit[j]:
                print(a[j], end=' ')
        print()
    elif i == N:                        # 합이 덜 됐는데 모든 원소에 대한 고려가 끝난 경우
        return
    elif s > t:                         # 이미 합계를 넘어 남은 원소를 고려할 필요가 없는 경우
        return
    elif s+rs < t:                      # 남은 원소를 다 더해도 합계에 도달하지 못하는 경우
        return
    else:                               # 남은 원소가 있고 s < t인 경우
        bit[i] = 1
        f(i+1, N, s+a[i], t, rs-a[i])   # i 인덱스의 값을 합에 포함
        bit[i] = 0
        f(i+1, N, s, t, rs-a[i])        # i 인덱스의 값을 합에 미포함
 
N = 10
t = 40
a = [x for x in range(1, N+1)]
bit = [0]*N
f(0, N, 0, t, sum(a))

def backtrack(a, k, input):
    global MAXCANDIDATES
    c = [0] * MAXCANDIDATES
 
    if k == input:
        for i in range(1, k+1):
            print(a[i], end=' ')
        print()
    else:
        k += 1
        ncandidates = construct_candidates(a, k, input, c)
        for i in range(ncandidates):
            a[k] = c[i]
            backtrack(a, k, input)
 
def construct_candidates(a, k, input, c):
    in_perm = [False] * NMAX
 
    for i in range(1, k):
        in_perm[a[i]] = True
 
    ncandidates = 0
    for i in range(1, input+1):
        if in_perm[i] == False:
            c[ncandidates] = i
            ncandidates += 1
    return ncandidates

교환을 통해서 순열을 생성해보자.

자리를 다시 바꿔주는 이유는, 이전 코드의 기준 배열 상태로 되돌려주기 위해서이다.


그런데 재귀를 이용하면 아래처럼 코드를 축소할 수 있다.

def f(i, N):
    if i==N:
        print(p)
    else:
        for j in range(i, N): # j는 i부터 시작해야 다시 바꾸지 않는다!!⭐
            p[i], p[j] = p[j], p[i]
            f(i+1, N)
            p[i], p[j] = p[j], p[i]  # 다시 이전 상태로 바꿔주기 위해 다시 바꾸는 것!
 
 
p = [1,2,3]
N = 3
f(0, N)

N의 수가 크거나 값의 변동이 있는 경우 아래처럼 사용하면 된다.


def f(i, N):
    if i==N:
        print(p)
    else:
        for j in range(i, N): # j는 i부터 시작해야 앞부분을 다시 바꾸지 않는다!!⭐
            p[i], p[j] = p[j], p[i]
            f(i+1, N)
            p[i], p[j] = p[j], p[i]  # 다시 이전 상태로 바꿔주기 위해 다시 바꾸는 것!
 
N = 5
p = [x for x in range(1, N+1)]
f(0, N)