[Algorithm] 개념2 : 2_BackTracking 백트래킹(되추적)

2. BackTracking 백트래킹(되추적)

• 막히면 왔던 길을 되돌아가서 다시 찾는다
• 최적화 문제와 결정 문제(yes/no) 해결
• 우리가 해줄 것은 해가 만족해야 하는 조건bound정하기!
• State Space Tree 활용으로 promising여부 확인(bound)

 

1.  n-Queens문제
   • n개의 Queen을 한 체스판에 가로세로대각선 방향으로 위치가 겹치지 않도록 배치하는 문제.
     
     • State Space Tree 상태공간트리 : 문제해결의 중간 사태를 각 노드로 나타낸 트리
       • 루트에서 리프노드까지의 모든 경로가 해답의 후보이며 그 중 답이 되는 경로를 Answer States라 함
       • 답이 나올 가능성이 전혀 없는 노드를 유망하지 않은non-promising 노드, 그렇지 않은 노드를 유망한promising 노드라 함
       • 백트래킹과 분기한정법으로 탐색 가능함
       • DFS로도 탐색이 가능하지만 답이 될 가능성이 전혀 없는(유망하지 않은) 노드의 자식노드까지 모두 탐색해 비효율적.
     
     
     • backtracking으로 state space tree를 탐색할 때 조건bound은 해당 노드가 promising한가?임. dfs방식으로 검색하다가 해당 노드가 promising하지 않으면 해당 노드의 자식노드는 더 탐색하지 않고 그냥 backtrack함(왔던 길, 즉 부모노드로 되돌아옴). 그리고 다음 노드를 탐색함. promising한 노드들에 대해서만 그 자식들을 탐색함.
     
     
     • n-Queens문제를 backtracking으로 풀기
       • n-Queens문제를 backtracking으로 풀 때에는 현재 노드 위치에 현재 Queen을 두었을 때 다른 Queen과 가로세로대각선 길이 겹치지 않는가?를 확인해서 현재 노드의 promising여부를 결정하면 됨.
       • ** 각 노드가 나타내는 위치를 (r,c)라 하면 같은 /에 있는 위치는 r-c값이 같음. 같은 \에 있는 위치는 r+c값이 같음. -> 이를 한 식으로 정리하면 (a,b)와 (c,d)가 같은 대각선상에 있으면 |a-c| = |b-d| 임.
       • Monte Carlo기법으로 수행시간 측정 : 다음 조건을 만족해야 측정 가능(n-Queens, Graph Coloring은 가능)  
         1. 같은 level의 각 노드들에 대해서는 promising여부를 확인하는 방법이 같아야 한다.
         2. 같은 level의 각 노드들은 같은 수의 자식노드를 가져야 한다.
2. Graph Coloring 그래프 색칠하기 문제
   • m개의 색으로 노드 n개를 인접한 노드끼리 색이 같지 않게 칠하는 문제
     • 상태공간트리state space tree와 backtracking 사용
     • 여기서 상태공간트리의 노드 총 수는 m^n개이고 이는 이 문제의 시간복잡도 최악과 같다.
     • 수행시간 측정 가능
3. 외판원 문제 TSP 
   • 모든 노드를 방문하고 출발노드로 돌아오는 최단경로 찾기
     • 상태공간트리state space tree와 backtracking 사용
     • 최단거리를 찾는 문제이므로 처음에는 루트노드에서 리프노드까지 dfs로 쭉 내려가서 완전한 한 경로의 시간을 구해 bestSolution 으로 기억해둠.
     • 그 다음 노드부터는 해당 노드까지의 값이 bestSolution보다 좋아질 확률이 없으면 그 자식노드를 더 탐색하지 않고 backtrack함. 더 좋은 값이 나오면 bestSolution으로 업데이트함.