분기 한정법

위키백과, 우리 모두의 백과사전.

분기 한정법(分岐限定法, Branch and bound)은 다양한 최적화 문제를 풀기 위한 범용 알고리즘이다. 주로 이산 최적화조합 최적화 문제를 풀 때 쓴다. 분기 한정법은 모든 후보해를 체계적으로 늘어놓으면서 최적화할 수치의 상한과 하한을 추정, 가망 없다는 판정이 나는 해를 제거해 나간다. 제거하는 해에서 파생되는 해는 살펴보지 않기 때문에 불필요한 시간 소모를 줄이게 된다.

이 방법은 A. H. 랜드와 A. G. 도이그가 1960년선형 계획법을 풀기 위해서 제안하였다.

더 보기[편집]