Branch and Bound   분기 한정, 한정 분기

1. 분기 한정 법 (Branch and Bound)

  ㅇ 조합 최적화 문제를 해결하기 위한 탐색 알고리즘
     - 가능한 해의 집합을 트리 형태로 분기(Branch)시키며, 
     - 각 분기에서 계산한 상하한(Bound)을 이용해, 탐색 범위를 제한
        . 불필요한 가지(해가 최적해가 될 수 없는 부분)는 잘라내어(Prune) 계산량을 줄임

  ㅇ 특징
     - 완전 탐색 대비 탐색 효율을 높이면서도 최적해 보장이 가능

  ㅇ 용도
     - 최적화 문제(예: 외판원 문제, 배낭 문제) 해결에 사용되는 등