결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'no'가 답하는 문제
미로 찾기
n-Queen 문제
Map coloring
부분 집합의 합(Subset Sum) 문제 등
백트래킹과 깊이우선탐색과의 차이
어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄임. (Prunning 가지치기)
깊이우선탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단
깊이우선탐색을 가하기에는 경우의 수가 너무 많음
즉 N! 가지의 경우의 수를 가진 문제에 대해 깊이우선탐색을 가하면 당연히 처리 불가능한 문제
백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어듦, 하지만 최악의 경우에는 지수함수 시간을 요하므로 처리 불가능
모든 후보를 검사하는 것이 아님!!!!!
백트래킹 기법
어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 감
어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 함
가지치기 : 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않음
백트래킹을 이용한 알고리즘은 다음과 같은 절차로 진행
상태 공간 트리의 깊이 우선 검색을 실시
각 노드가 유망한지 점검
만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 진행
미로 찾기
아래 그림과 같이 입구와 출구가 주어진 미로에서 입구부터 출구까지의 경로를 찾는 문제
이동할 수 있는 방향은 4방향으로 제한
미로 찾기 알고리즘
n-Queen
상태 공간 트리
부분집합 구하기
n개의 원소가 들어있는 집합의 2^n개의 부분집합을 만들 때는, true 또는 false 값을 가지는 항목들로 구성된 n개의 배열을 만드는 방법을 이용
여기서 배열의 i번째 항복은 i번째의 원소가 부분집합의 값인지 아닌지를 나타내는 값
powerset을 구하는 백트래킹 알고리즘
N = 3
arr = [1, 2, 3] # 우리가 활용할 데이터
sel = [0] * N # a리스트 (내가 해당 원소를 뽑았는지 체크)
def powerset(idx):
if idx == N:
print(sel, ":", end = ' ')
for i in range(N):
if sel[i]:
print(arr[i], end=' ')
print()
return
# idx 자리의 원소를 뽑고 간다.
sel[idx] = 1
powerset(idx+1)
# idx 자리를 안뽑고 간다.
sel[idx] = 0
powerset(idx + 1)
powerset(0)
# =>
# [1, 1, 1] : 1 2 3
# [1, 1, 0] : 1 2
# [1, 0, 1] : 1 3
# [1, 0, 0] : 1
# [0, 1, 1] : 2 3
# [0, 1, 0] : 2
# [0, 0, 1] : 3
# [0, 0, 0] :
순열 구하기
접근 방법은 앞의 부분집합 구하는 방법과 유사
arr = [1, 2, 3]
n = 3
sel = [0] * n
check = [0] * n
# 재귀방식
def perm(idx):
# 다 뽑아서 정리했다면
if idx == n:
print(sel)
else:
for i in range(n):
if check[i] == 0:
sel[idx] = arr[i] # 값을 사용해라
check[i] = 1 # 사용을 했다는 표시
perm(idx+1)
check[i] = 0 # 다음 반복문을 위한 원상복구
perm(0)
# =>
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]
# --------- #
# 비트연산 방식
# check 10진수 정수
def perm(idx, check):
if idx == n:
print(sel)
return
for i in range(n):
# i 번째 원소를 활용했군, 그럼 안쓰고 넘어가지
if check & (1<<i): continue
sel[idx] = arr[i]
perm(idx+1, check | (1<<i)) # 원상복구가 필요없다...
perm(0,0)
# => 결과는 위와 동
# ---------------- #
# 스왑 방식
def perm(idx):
if idx == n:
print(arr)
else:
for i in range(idx, n):
# 순서를 바꾸고
arr[idx], arr[i] = arr[i], arr[idx]
perm(idx + 1)
# 원상복구
arr[idx], arr[i] = arr[i], arr[idx]
perm(0)
# => 결과는 위와 동
