분단탐색법

1. 분단탐색법(Brnach and Bound)

분단탐색법(Branch and Bound)은 최적화 문제를 해결하기 위한 알고리즘적 접근 방식으로, 특히 조합 최적화 문제에 효과적으로 적용된다. 이 방법은 전체 해 탐색 공간을 트리 구조로 표현하고, 각각의 노드를 탐색하면서 가능한 최적 해를 찾는데 중점을 둔다. 분단탐색법은 일반적으로 문제의 최적 해를 구하는 데 있어 비효율적인 전수 탐색 방법에 비해 훨씬 더 효율적인 해결책을 제공한다. 분단탐색법은 크게 두 가지 과정, 즉 `분할`(Branching)과 `경계`(Bounding)로 구성된다. 분할 과정은 해 탐색 공간을 부분 문제로 나누는 것을 의미한다. 문제를 해결하기 위해서는 먼저 초기 문제를 기반으로 몇 가지 선택지를 고려하고, 그 선택지에 따라 새로운 서브 문제를 생성하게 된다. 이 과정에서 문제의 상태를 구분할 수 있는 다양한 경로를 트리 형태로 만들며, 각 노드는 특정한 변수의 값이 결정된 상태를 나타낸다. 경계 과정은 각 서브 문제의 우선순위를 정하고, 해당 문제에서 얻을 수 있는 최소 또는 최대 값을 추정하는 단계이다. 이 단계에서는 각 서브 문제의 `최선`의 해를 계산할 수 있는 상한이나 하한을 설정함으…