[Algorithm] 개념2 : 3_Branch &Bound 분기한정법

 

3. Branch&Bound 분기한정법

• State Space Tree활용
• 최적해 구하기에 적용 가능. Backtracking보다는 최적해를 구하기 위해 모든 해의 한계값(직접x)을 계산해 고려함.
• 각 노드에 대한 한계값bound을 계산함. 해당 노드는 bound보다 큰 값을 가질 확률이 없음.
• bound값이 지금까지의 최적해보다 좋은가?로 최적해 값을 업데이트하고 노드의  promising여부를 판단함.
• promising하지 않은 노드의 자식노드는 탐색하지 않음.

 

1. 0-1 Knapsack 문제
   • state space tree : 왼쪽으로 가면 현재 아이템을 담지 않는 걸로, 오른쪽으로 가면 현재 아이템을 담는 걸로 함.
   • 루트에서 리프노드까지의 모든 경로가 해답후보임
   • 최적해를 찾는 문제이므로 전체를 다 탐색하기 전에는 답을 알 수 없음
   • 해당 노드의 최대이윤한계값bound = 직전단계까지의 이윤 + 앞으로 남은 물건들을 무게가 넘치기 직전까지 담을 수 있는 이윤 + 남은 공간도 물건을 잘라서 넣으면(실제론 못 자름) 담을 수 있는 이윤 (진짜 최대로 담은 거라고 생각하기)
   • 탐색 전, 물건을 단위무게당 이윤이 큰 물건 순으로 정렬함
   • Branch and Bound방법으로 Best First Search 최고우선검색함. 노드들을 모두 방문하며
     1. 해당 노드까지의 profit과 weight를 계산하고 bound를 계산
     2. bound값으로 progmising여부를 확인함. 현재 아이템까지 담았을 때 무게가 넘치지 않고 bound>maxprofit(현재까지의 최적이윤) 이면 promising함 -> 큐에 넣음
     3. promising한 노드들 중 가장 bound값이 큰 노드들부터 큐에서 꺼내 직속자식노드들을 탐색함(Best First Search)
     4. 무게가 넘치거나 bound>현재의maxprofit이 아닌 노드의 자식노드들은 탐색하지 않음.(maxprofit이 계속 업데이트 되므로 큐에 있던 노드라도 현재의 maxprofit과 비교해 판단)
     5. 큐가 비면 종료
   • Best First Search : 우선순위 큐Priority Queue를 사용함. 우선순위 큐는 힙(Heap)으로 구현.  (**최대 힙(max heap) : 자식보다 부모가 항상 큰 값인 이진트리)
   • 시간복잡도 최악 O(2^n) (Backtrack과 최악 같음)
   • Dynamic보다 항상 좋다고 확언할 수는 없지만 일반적으로 Dynamic보다 Backtrack이 더 빠르다는 것은 입증됨.
2. 외판원 Traveling Salesman Problem 문제
   • 모든 도시를 방문하고 출발지로 돌아오는 최단경로 구하기 - 최소값을 구하는 문제니까 Max Heap대신 Min Heap을 씀
   • promising : bound < minlength 인 노드
   • 루트에서 리프노드까지 완전한 경로를 한번 계산할 때까지는 항상 bound < minlegth가 됨
   • bound계산 : 노드간 간선의 가중치 표를 활용함. 현재노드로 오기까지의 값 + 현재노드에서 아직 거치지 않은 노드로 가는 값중 최소값(그리고 그 노드 방문 가정) + 아직 거치지 않은 노드들에서 출발(행번호)해 아직 거치지 않은 다른 노드들 및 출발점(열번호)에 도착하는 간선들 중 최솟값의 합 (가중치 표에서는 같은 행 중 min값) -> 표 연습하기
   • 각 노드에서는 bound를 계산하되 리프 노드에서는 bound가 아닌 해당 경로의 value값이 된다.
     1. 맨 처음은 루트노드를 큐에 넣어 시작한다.
     2. 큐에서 bound가 가장 작은 노드를 꺼내 현재 minlegth와 비교한다. 아직도 bound<minlength이면 계산해볼 가치가 있으므로 그 노드의 직속자식 노드들을 돌며 bound를 계산한다. bound>minlength이면 해당 노드의 자식노드들은 더이상 탐색하지 않는다.(가지치기)
     3. 계산 시 계산한 bound가 minlegth보다 작거나 같으면 큐에 넣고 크면 넣지 않는다(그 자식노드는 탐색하지 않겠다는 뜻). 
     4. 직속자식 노드를 모두 돌았다면 큐에서 다시 bound가 가장 작은 노드를 꺼내 반복한다.
     5. 리프노드까지 와서 한 경로가 완성되었을 때 value<minlength이면 minlength값을 업데이트한다.