Branch and Bound Algorithms – Principles and Examples
[cite]10.1.1.5.7475[/cite]
오래 전 글의 백업입니다.
2012년 1월 5일
Branch and Bound algorithm에 대한 논문입니다.
Branch and Bound 알고리즘은, non linear function에서 최소값을 구하는 문제에 적용할 수 잇습니다.
전체 가능한 구간을 조금씩 잘라가면서, 구간에서 나올 수 있는 최소 값을 구합니다.
그리고 자르기 전에 구했던 최소 값과 비교하여 그보다 높으면, 해당 구간에서 답이 없다고 판단하고 구간을 탐색 범위에서 제거할 수 있습니다.
다음 그림을 보면 쉽게 이해가 가능합니다. 좌우 구간에서의 가능한 최소 값은 전체 구간에서 가능한 최소 값보다 크므로 이 안에는 해(=값이 최소가 되는 지점)이 없다고 판단하고 탐색 범위에서 제거할 수 있습니다.
문제의 핵심은, 구간에서의 최소 값을 구하는 함수를 주어진 문제의 함수를 그대로 이용하지 않고 다른 함수를 이용하게 되는데,
원래 문제에서 주어진 함수(non-linear function)보다 가벼운 cost로 최소 값을 구할 수 있느냐가 관건이 됩니다.