![[Algorithm] 백트래킹(Backtracking)과 순열](/_next/image?url=https%3A%2F%2Fblog.huns.site%2Fimgs%2Fthumbnails%2Fblog%2Fposts%2Fcomputer-science%2Falgorithm.png&w=1200&q=75)
TOC
백트래킹(Backtracking)
- 해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 기법
- 최적화(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개
powerset을 구하는 백트래킹 알고리즘
- 각 원소가 부분집합에 포함되었는지를 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)
가지치기(Pruning)
부분집합의 항목 합계를 구하는데, 아직 항목을 다 확인하지 않았음에도 원하는 합계에 도달하거나 넘겼을 경우, 이후 항목의 여부는 확인할 필요가 없기 때문에 실행을 진행하지 않고 탈출한다. 백트래킹이 경제적일 수 있는 이유이다. 그 구현을 밑에서 살펴보자.
# 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)
가지치기 2
# 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)
