분기 한정법 (Branch-and-bound 기법)
| 분기 한정법(分岐限定法, Branch and bound)은 다양한 최적화 문제를 풀기 위한 범용 알고리즘이다. 주로 이산 최적화나 조합 최적화 문제를 풀 때 사용한다. 분기 한정법은 모든 후보의 해를 체계적으로 늘어놓으면서 최적화할 수치의 상한과 하한을 추정, 가망 없다고 판정이 나는 해를 제거해 나가며 제거하는 해에서 파생되는 해는 살펴보지 않기 때문에 불필요한 시간 소모와 노력을 줄이게 된다. 이 방법은 A. H. 랜드와 A. G. 도이그가 1960년에 선형 계획법을 풀기 위해서 제안하였다. |
⦁ 다양한 최적화 문제를 풀기 위한 범용 알고리즘으로써 최소한 이 정도는 되어야 답이 될 가능성이 있다“라는 한계치(Bound)를 정해두고 범위를 벗어나는 값들은 가지치기(Branch)를 해가며 결과 값을 추적함으로써 시간과 노력을 아낄 수 있다.
1) 특징
⦁ 분기한정법은 최적의 해를 구하는 문제(optimization problem)를 해결하기 위해 되추적 기술을 향상시킨 기법
⦁ 되 추적 기법과 같이 상태공간 트리를 구축하여 문제를 해결
⦁ 최적의 해를 구하기 위해서는 모든 해를 다 고려해 보아야 하므로 트리의 마디를 순회(traverse) 하는 법에 구애받지 않음.
※ 분기한정법이 되추적 기법과 다른 점
- 최적의 해를 구하는 문제(optimization problem)에만 적용
- 트리를 순회(traverse) 하는 방법을 좀 더 효율적으로 택함.
2) 분기한정 알고리즘의 원리
⦁ 각 마디를 검색할 때마다 그 마디가 유망한지를 결정하기 위해 그 마디로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계치(bound)를 구함.
⦁ 한계치가 지금까지 찾은 최적의 해답치 보다 좋지 않은 경우는 더 이상 가지를 뻗어서 검색을 계속할 필요가 없으므로 그 마디는 분석에서 제외를 하고 해당 서브 트리를 잘라냄.
즉, 분기한정법의 핵심은 작업을 최소화하기 위해 탐색 트리에서 가능성이 없다고 판단한 해에 대해선 더 이상 검토를 안 하고 제외해 불필요한 시간과 노력을 줄일 수 있다는 점으로 이러한 단계를 절단이라고 부름.
⦁ 분기한정법의 효율성은 사용되는 branching and bounding algorithm의 효과에 전적으로 의존함.
잘못 선택하면 하위 분류가 매우 작아질 때까지 어떤 절단도 없이 반복된 branching만 할 수도 있는데, 그러한 경우에 분기한정법은 비현실적으로 큰 소모적인 열거 (exhaustive enumeration of the domain)로 끝나게 됨.
⦁ 분기한정법은 다양한 휴리스틱의 기초가 될 수 있음.
잡스9급 PDF 교재
✽ 책 구매 없이 PDF 제공 가능
✽ adipoman@gmail.com 문의
✽ 유튜브 강의