ch 5. backtracking (되추적법)

• Backtracking (되추적법)
  
  
• (사전 설명) Depth-First Search (깊이우선 탐색)
• Root 노드 선 방문 후, 그 후 자식 노드를 차례대로 방문 (Pre-order tree traversal)
  
  
• n-Queen problem
• (n=4)
  
  4-Queens Problem : 4개의 Queen을 서로 상대방을 위협하지 않도록 4x4 체스판에 두는 문제.
  
  
• 4-queen 문제에 대한 상태 공간 트리 (모든 경우를 표시)
  
  
  
• 서로 상대방을 위협하지 않기 위해서, 같은 행/열/대각선 상에 위치하지 않아야 함.
• Brute-force Approach : 각 Queen을 각각 다른 행에 할당한 후, 차례로 점검.
• State Space Tree (상태공간트리) 를 이용
• root 노드에서 leaf 노드까지의 경로를 candidate solution으로 두고 DFS를 통해 candidate 중에서 해답을 찾음
• 그러나 이 방법은, 해답의 가능성이 없는 노드의 자식 노드들도 모두 검색해야하므로 비효율적
  
  
• Backtracking Approach
• 정의 : Promising (유망성)
• 해답이 나올 가능성이 없는 노드 --> non-promising 
• 해답이 나올 가능성이 있는 노드 --> promising
  
  
• Backtracking 이란?
• 어떤 노드의 유망성(promising)을  점검한 뒤, 유망하지 않다면 (non-promising) 그 노드의 부모 노드로 돌아가서("Backtracking"), 다음 자식 노드에 대한 검색을 계속 진행하는 과정의 방법
• 상태 공간 트리에서 깊이우선탐색 (DFS)를 실시하면서,  
  --> 유망하지 않은(non-promising) 노드는 가지쳐서(pruning) 검색을 하지 않으며
  --> 유망한(promising) 노드에 대해서만 그 노드의 자식노드를 검색함.
  
  
• 진행 순서
• 1. 상태 공간 트리의 깊이 우선 검색을 실시
• 2. 각 노드가 유망한 지 점검
• 3. 노드가 유망하지 않다면, 부모노드로 돌아가서 검색을 이어감
  
  
• Backtracking 을 이용한 4-queen problem
• 일반적인 backtracking 알고리즘

void checknode(node v){         node u;                  if (promising(v))                 if (there is a solution at v)                         write the solution;         else                 for (each child u of v)                         checknode(u); }

• 개선된 backtracking 알고리즘
• 노드를 방문하기 전에 유망성(promising) 여부를 점검하면, 방문할 노드의 수가 적어짐

void expand (node v) {         node u;                  for (each child u of v)                 if (promising(u))                         if(there is a solution at u)                                 write the solution;                         else                                 expand(u); }

• Monte Carlo Algorithm
• 어떤 입력이 주어졌을 때, 점검하게 되는 상태 공간 트리의 전형적인 경로를 무작위로 생성하여 그 경로 상에 있는 노드의 수를 센다. 이 과정을 반복하여 나오는 결과의 평균치를 추정치로 한다.
• 확률적 (probabilistic) 알고리즘 - 표본 공간의 무작위 표본의 추정치를 가지고 무작위 변수의 기대치를 추정
• 이 기법을 적용하기 위한 선행 조건
• (1) 상태 공간 트리에서 같은 수준(레벨)에 있는 모든 노드에서는 같은 유망 함수 사용
• (2) 상태 공간 트리에서 같은 수준(레벨)에 있는 모든 노드에서는 같은 수의 자식 노드를 가져야함
  
  
• monte carlo 기법을 사용한 backtracking 알고리즘의 수행시간 추정 방법
• (1) Root 노드의 유망한 (Promising) 자식의 개수를 m(0) 라고 함
• (2) 상태 공간 트리의 수준(레벨) 1에서 유망한 노드를 무작위로 하나 정하고, 그 노드의 유망한 자식 노드의 개수를 m(1)이라고 함.
• (3) 위에서 정한 노드의 유망한 노드를 무작위로 하나 정하고, 그 노드의 유망한 자식 노드의 개수를 m(2)이라고 함.
• (4) 더이상 유망한 자식 노드가 없을때가지 이 과정을 반복한다.
  
  

• backtracking에서 점검한 노드 개수 추정치 구하기
• m(i)는 수준 i에 있는 노드의 유망한 자식노드의 개수의 평균의 추정치
• t(i)는 수준 i에 있는 한 노드의 자식노드의 총 개수
• 따라서 노드의 총 개수의 추정치는, 
  1 + t(0) + m(0)t(1) + m(0)m(1)t(2) + ... m(0)m(1)...m(i-1)t(i) + ... 

• Sum-Of-Subsets Problem
• n개의 정수(w(1)...w(n))랑 정수 W가 있다고 할때, 
  n개의 정수들의 부분합이 W값이 되도록 모든 부분 집합 찾기.
• (예) n=5 => {5, 6, 10, 11, 16} , W=21
• {5, 6, 10}, {5, 16}, {10, 11}
• 상태 공간 트리 (n=3 경우)
  
  
  
  
  
• Backtracking 을 이용하여 sum-of-subset problem 풀기
  
• weight를 오름차순으로 정렬했다면, non-promising에 대한 명백한 표시가 있음.
  (정렬을 하는 이유? 정렬하지 않으면 답을 찾을 수 없는 경우가 발생함)
• (1) weight - 수준(레벨) i까지 포함된 노드들의 weight의 합
• if   weight + w(i+1)  > W  ==> node가 유망하지 않음
• (2) total - 남은 weight의 총 weight
• if  weight + total < W ==> node가 유망하지 않음
• 시작 : sum_of_subsets(0, 0, total)
  
• 코드 예시
  
  
  
  
• Graph Coloring Problem
  
• m-coloring : 지도에 m가지 색으로 색칠하는 문제
  (정점(노드)의 개수 - n, 색깔의 개수 - m)
• 지도를 그래프로 표현 --> 상태 공간 트리로 표현
  
   < 그래프로 표현 >
  
  
  
  
  <상태 공간 트리로 표현>
  
  
  
  
  
• 코드 예시 
  

• The Hamiltonian Circuits Problem
• cf. Traveling Salesperson Problem (Dynamic programming)
  
  
• Hamiltonian circuits problem (--> TSP without Weight)
• 모든 도시가 길로 연결되어 있는 것은 아님.
• 주어진 노드에서 시작하여, 모든 노드를 한번씩 방문한 뒤 시작노드에서 끝나는 경로
  

• Backtracking을 적용하기 위해 고려할 사항
• 경로 상 i번째 노드는 그 경로 상의 (i-1)번째 노드와 반드시 이웃(연결)이어야 한다
• (n-1)번째 정점은 반드시 출발점과 이웃해야 한다
• i 번째 정점은 처음 i-1개의 정점이 될 수 없다.
  
  
• 코드 예시
  
  
  
  
  
• 0-1 Knapsack Problem with backtracking
  
• 상태 공간 트리를 구축하여 되추적 기법 사용
• 노드의 왼쪽 자식 노드 - 해당 레벨 순서의 (예, 1번째, 2번째) 아이템을 배낭에 넣은 경우
• 노드의 오른쪽 자식 노드 - 해당 레벨 순서의 아이템을 배낭에 넣지 않은 경우
• 상태 공간 트리를 구축하여 루트노드에서 리프노드 까지의 경로를 만들어 해답 후보를 생성
• * 이 문제에서는 최적의 해를 찾아야 하므로, 검색이 완전히 끝나기 전에는 해답을 알 수 없음. 따라서, 검색 과정동안 그때까지 찾은 최적의 해를 저장하여 기억해두어야 함.

• 일반적인 알고리즘 방법
  
  ** 검색하는 동안 최적의 해를 찾아 'best' 변수에 저장
  * best : 지금까지 찾은 최적의 해답
  * value(v) : v 마디에서의 해답치
  
  
• 알고리즘을 위한 고려사항
• 자료구조
• w (i) - i 번째 아이템의 weight (가치)
• p (i) - i 번째 아이템의 profit (무게)
• item을 p/w 값으로 오름차순으로 정렬 (무게당 가치를 기준으로 하여)
  
  
• profit  - 현재 노드까지 포함된 가치의 합
• weight - 현재 노드까지 포함된 무게의 합
• totweight - 해당 노드까지 얻었을 때 구할 수 있는 무게의 합 (W를 넘을 수 없음)
• bound - 해당 노드까지 얻었을 때 구할 수 있는 가치의 상한선
• maxprofit - 지금까지 찾은 최선의 해답이 주는 가치
  
  
• 순서
• (1) bound와 totweight를 profit과 weight 값으로 초기화
• (2) totweight이 W를 초과하는 아이템을 구할 때까지,  탐욕적 방법으로 아이템 선택 하는 것을 반복
• (3) 남은 공간이 허용되는 무게만큼, 마지막 아이템의 일부분을 취하고, 그 일부분에 해당하는 가치를 bound에 더함
  
  
• DFS로 각 레벨을 방문하여 다음 과정 수행
• 해당 레벨의 profit과 weight 계산 --> 또한 bound 계산 
• weight < W 이고 bound > maxprofit 이면 검색을 계속 진행
• 그렇지 않을 경우 backtracking
   
  
• 코드 예제