[알고리즘] Backtracking / 백트래킹

📕Backtracking이란?

---

영어 사전에서 backtrack이란 단어를 검색하면 나오는 결과이다.

'(방금 왔던 길을) 되짚어 가다'

 

미로찾기를 한다고 생각해보자, 두갈래 갈림길이 나왔을때 왼쪽으로 가다가 막히면 어떻게 하는가?

다시 갈림길이 있는 곳으로 돌아와서 오른쪽으로 가지 않겠는가?

 

이것이 바로 백트래킹의 핵심이다. 

길이 막혔을 경우 다시 돌아가는 것을 원하는 결과가 나올때까지 반복하는 것이 바로 백트래킹이다.

 

간간단한 예제를 살펴보자.

 

S = {W1 = 5, W2 = 6, W3 = 10, W4 = 11, W5 = 16} and W = 21

S에 있는 수를 뽑아 W를 만드려고 한다.

 

이때 생기는 조합은 여러가지가 있다. 

{W1, W2, W3} , {W1, W5}, {W3, W4} = 21

 

이러한 문제를 어떻게 풀까?

 

📕Backtracking by tree

---

위의 문제와 비슷하게, W = 6, S = {W1 = 2, W2 = 4, W3 = 5} 라고 설정하자.

트리의 왼쪽으로 갈 경우 각 트리의 높이에 해당하는 wi를 더하고, 왼쪽으로 갈 경우 더하지 않는다.

이렇게 모든 경우의 수를 탐색할 경우, 6이 되는 부분집합은

{W1, W2} 하나임을 알 수 있다.

 

하지만 이렇게 모든 경우의 수를 탐색하는 것은 비효율적이다.

더 나은 방법이 존재할 것 같지 않은가?

 

이때 우리는 가지치기, Prune the tree를 진행한다.

 

1. 먼저 weights를 non-decreasing order로 정렬한다.
2. Let 'weight' be the sum of weights that have been included up to a node at level i. A node at level i is                 non-priomising if weight + w(i+1) > W
3. Let 'total' be the total weight of the reamining weights at a given node. A node is non-promising if                     weight + total < W
4. if 'weight' == W, we found the solution

2번의 경우를 보면 앞으로 더하려는 W(i+1)과 현재 노드의 합이 구하려는 W보다 클 경우 조건을 만족하지 않는다.

그렇기 때문에 W보다 큰 경우는 더이상 탐색하지 않는다.

 

3번의 경우, 앞으로 더할 모든 Wi 와 현재 노드를 더해도 W에 미치지 못한다면 더이상 탐색하지 않는다.

 

📕Backtracking의 효율성

---

백트래킹은 최악의 경우 2^(n+1) -1 만큼의 효율성을 가진다.

(모든 노드를 탐색하는 경우이다.)

 

이렇게 최악의 경우가 존재함에도 불구하고 백트래킹 알고리즘을 사용하는 이유는 

효율성이 좋은 경우가 훨씬 많기 때문이다.

 

백트래킹은 일부 부분 집합이 생성될 필요가 없음을 결정하는 기법이다.

그렇기 때문에 불필요한 작업들을 피할 수 있다. 

 

또한 NP-complete 알고리즘을 풀때 사용될 수 있다. 하지만 여전히 실행시간은 지수이거나, 그 이상이다.