분기 한정법

분기 한정법 branch and bound

- 분기 한정법은 여러 최적화 문제, 특히 이산 discrete와 조합 최적화 combinational optimization에서 최적해를 찾기위한 일반적인 방법

- 인수 x(가능영역 feasible region)에 대해 함수 f(x)의 최소 값을 찾는 것

 

분기 한정 과정

1. 분기 branching

- 여러개 작은 하부 가능영역feasible subregion들이 가능 영역 feasible region을 구성하는 방법

- 하부영역 각각에 대해 재귀 반복을 거치고, 만들어진 하부영역들이 자연스럽게 탐색 트리나 분기 한정 트리 branch-and-bound-tree 구조를 형성함 -> 노드가 각자 subregion이 됨

 

2. 한정 bounding

- 가능 하부공간 내에 최적해를 찾기 위한 상승 한정 하강한정 upper and low bound를 빠르게 차즌ㄴ 방법

 

 

분기 한정법의 핵심

- 탐색 트리에서 subregion A의 lower bound가 이미 검사된 다른 subregion B의 upper bound보다 크다면 A를 탐색에서 폐가함 -> 절단 pruning이라 함.

- 분기한정법은 탐색 노드의 모든 노드가 절단 되거나 해결되면 종료됨.