1. 백트래킹과 한계점

• 백트래킹(backtracking)은 상태공간트리를 DFS로 탐색, 유망(promising)하지 않은 노드는 pruning하여 효율화.
• 그러나 bound(한계치) 계산은 오직 탐색 진행 여부만 판단하며, bound의 크고 작음 자체는 탐색 순서에 활용하지 않음.
• 깊이우선탐색(DFS)이므로, 해답까지의 경로가 길거나 pruning이 늦게 이루어지는 경우 불필요한 탐색이 많아질 수 있음.

2. 분기한정법(Branch-and-Bound) 개요

• 분기(branching): 문제의 해 공간을 분할하여 상태공간트리 구축
• 한정(bounding): 각 노드에서 해답 가능성의 상한/하한(bound)을 계산
• 전략: bound가 기존 최적해보다 나쁘면 해당 서브트리 전체를 prune
• 핵심 차이: 유망한 노드 중에서 bound가 가장 좋은 것(최고 bound)을 가진 노드를 먼저 확장(탐색 순서에 bound를 적극적으로 활용)

3. 탐색 전략

• 깊이우선검색(DFS): 백트래킹에서 사용
• 너비우선검색(BFS): 모든 레벨을 차례로 확장
• 최고우선검색(Best-First Search, BestFS):
  • 확장되지 않은 노드 중에서 bound가 가장 좋은 노드부터 확장
  • 일반적으로 우선순위 큐(priority queue, heap)를 사용하여 구현

4. 최적화 문제에서의 분기한정법

4.1 최소화 문제

• 각 노드에서 bound는 최소값에 대한 하한을 의미
• 이미 찾은 해답보다 bound가 크면(더 나쁜 경로), 해당 노드는 prune