책 정리

분기한정법이란?

다양한 최적화 문제를 출기 위한 범용 알고리즘. 분기한정법은 모든 후보해를 체계적으로 늘어놓으면서 최적화할 수치의 상한과 하한을 추정, 가망 없다는 판정이 나는 해를 제거함. 제거하는 해에서 파생되는 해는 살펴보지 않기에 불필요한 시간 소모를 줄이게 됨

→ 가능성을 판단해 가망이 없으면 더 이상 진행하지 않고 돌아감

되추적과의 차이점

• 역추적은 깊이 우선 탐색 트리 순회라고 하는 미리 결정된 순서로 트리를 탐색함
  • 최적화 및 비최적화 문제에 사용
• 분기한정법은 트리에서 방문하는 다음 노드는 많은 유망 노드 중 가장 좋은 유망 노드를 선택하여 런타임 동안 결정됨. 이는 너비 우선 탐색이 수정된 최상 우선 탐색이 사용됨
  • 최적화 문제에만 사용

실행방법

각 노드를 방문할 때 마다, 그 노드가 유망한지의 여부를 결정하기 위해서 **한계치(bound)**를 계산함

• 한계치는 그 노드로부터 가지를 뻗어나가서 얻을 수 있는 해답치의 한게
• 한계치가 이전까지 찾은 최고 해답값보다 더 좋으면 그 마디는 유망하다라고 함

만약 한계치가 지금까지 찾은 최적의 해답치 보다 좋지 않은 경우 더 이상 가지를 뻗어서 검색을 계속할 필요가 없기에 그 노드는 유망하지 않다고 할 수 있음.