5장 Backtracking Algorithm

chap5 Backtracking Algorithm design approach

• 해가 될 가능성이 있는지 promising을 확인한 수 필요없으면 가지치기 prune을 한다.

DFS = 깊이 우선 탐색

• DFS는 스택 자료구조 또는 재귀 함수를 이용한다.

1. DFS backtracking 푸는법

2. Tree 형태로 visualize한다

3. branch를 제거하는 메커니즘을 설계한다.

4. 조건에 따라 단일 leaf node에 도달하거나 여러개의 leaf node에 도달할 것이다. 이후 조건에 따라 이중에서 하나를 선택한다.

5. DFS 동작 과정

   1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
   2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
   3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

Queens problem = nxn 체스판에 n개의 퀸을 겹치지 않게 올리는 방법

• n^4 경우의 수가 있으며 유망하지 않은 node와 그 자식은 거르기 = non optimization
• n=4일때 예제

• 4x4 queens 문제를 backtracking depth first search로 풀면 27번 걸리지면 그냥 depth first search로 풀면 가지치기를 안하기 떄문에 155번 걸린다.

1. 그냥 dfs time complexity = n^n+n^n-1 + n^n-2+…+n^1+1
2. 좌우 앞뒤에 퀸이 없다는 제약조건에서의 dfs = 1+n+n(n-1)+..n!
3. back tracking timecomplexity = 비약적 감소

• 이렇게 같은 문제임에도 각각 인스턴스별로 다른 복잡도를 가지면 NP문제임

0-1 Knapsack -optimization problem = T(n) = 2^n

• optimization problem don’t know the solution until the search is over
• Greedy는 구하지못했으니 배제하고 , DP의 knapsack과 비교했을때 time complexity는 같기에 theoritical 분석은 안된다. backtracking knapsack문제풀이는 input data에 따라 버려지는 가지수가 정해지기에 많이 다를것이다. 즉, Greedy 보다는 kanpsack문제에서 효율적이며, optimization이 가능하긴 하겠지만 큰 차이 없다.