📖 백트래킹
📌 백트래킹
✅ 백트래킹(BackTracking) 개념
-
여러 선택지 (옵션)들이 존재하는 상황에서 한 가지를 선택한다.
-
선택이 이루어지면 새로운 선택지들의 집합이 생성된다.
-
이러한 선택을 반복하며 최종 상태에 도달한다.
- 올바른 선택을 계속하면 목표 상태(goal state)에 도달한다.
✅ 백트래킹과 깊이 우선 탐색의 차이
-
어떤 노드에서 출발하는 경로가 해결책으로 이어지지 않을 것 같으면 더 이상 그 경로를 따라가지 않음으로써 시도의 회수를 줄임. (Prunning, 가지치기)
-
깊이 우선 탐색이 모든 경로를 추적하는 데 비해, 백트래킹은 불필요한 경로를 조기에 차단한다.
-
깊이 우선 탐색을 가하기에 경우의 수가 너무나 많다. 즉, N!가지의 경우의 수를 가진 문제(순열)에 대해 깊이 우선 탐색을 가하면 당연히 처리 불가능한 문제가 된다.
-
백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만, 이 역시 최악의 경우에는 여전히 지수합수 시간(Exponential Time)을 요하므로 처리 불가능하다.
-
모든 후보를 검사?
- No!
-
백트래킹 기법
- 어떤 노드의 유망성을 점검한 후 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 감
- 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다.
- 가지치기(pruning) : 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다.
✅ 백트래킹을 이용한 알고리즘의 절차
-
상태 공간 트리의 깊이 우선 탐색을 실시
-
각 노드가 유망한지 점검
-
만일 유망하지 않으면 그 노드의 부모 노드로 돌아가서 검색을 계속
✅ 일반 백트래킹 알고리즘
checknode(node v)
IF promising(v)
IF there is a solution at v
write the solution
ELSE
FOR each child u of v
checknode(u)📌 순열 (Permutation)
✅ 순열
-
서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
-
서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현한다.
-
nPr은 다음과 같은 식이 성립한다
nPr = n x (n-1) x (n-2) x ... x (n-r+1)
-
nPn = n!이라고 표기하며, Factorial이라고 부른다.
-
다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련되어 있다.
ex> TSP (Traveling Salesperson Problem, 외판원 순회)
-
N개의 요소들에 대해서 n!개의 순열들이 존재한다.
- n > 12인 경우, 시간 복잡도 폭발적으로 증가
✅ 단순하게 순열을 생성하는 방법
- {1, 2, 3}을 포함하는 모든 순열을 생성하는 함수
- 동일한 숫자가 포함되지 않았을 때, 각 자리 수 별로 loop을 이용해 아래와 같이 구현할 수 있다.
FOR i1 in 1 -> 3
FOR i2 in 1 -> 3
IF i2 != i1
FOR i3 in 1 -> 3
IF i3 != i1 AND i3 != i2
print(i1, i2, i3)✅ 사전적 순서 (Lexicographic-Order)
-
{1,2,3}의 경우
-
{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}
✅ 최소 변경을 통한 방법 (Minimum-exchange requirement)
- 각 순열들은 이전의 상태에서 단지 두개의 요소만 교환하고 생성
✅ swap을 통한 순열 생성
// arr[] : 데이터가 저장된 배열
// swap(i, j) : arr[i]와 arr[j] 교환
// n : 원소의 개수, k : 현재까지 교환된 원소의 개수
perm(n, k)
IF n == k
print array // 원하는 작업 수행
ELSE
FOR i in k -> n-1
SWAP(k, i);
perm(n, k+1);
swap(k, i);✅ 방문체크를 통한 순열 생성
// nums : 데이터
// result : 결과 저장 배열
// check : 해당 원소를 사용했는지 체크하기 위한 배열
permutation(idx) {
if idx == N
(순열 생성 완료)
return
for i from 0 to N-1
if check[i]
continue;
result[idx] = nums[i]
check[i] = true
permutation(idx+1)
check[i] = false
}