# 분지 한정법 (Branch and Bound)

**분지 한정법**(Branch and Bound)은 조합 최적화 문제(Combinatorial Optimization Problem)를 해결하기 위한 체계적인 탐색 알고리즘입니다. 이 방법은 해 공간(Search Space)을 부분 공간으로 분할(분지, Branching)하고, 각 부분 공간에서 최적해의 하한(또는 상한)을 계산하여 탐색 범위를 제한(한정, Bounding)함으로써 불필요한 계산을 줄이고 효율적으로 최적해를 찾는 기법입니다. 주로 정수 계획법(Integer Programming), 여행하는 외판원 문제(TSP), 배낭 문제(Knapsack Problem) 등 NP-난제(NP-hard)로 분류되는 복잡한 문제들을 해결하는 데 널리 사용됩니다.

## 개요 및 기본 원리

분지 한정법은 완전 탐색(Brute-force)의 단점인 지수적 시간 복잡도를 개선하기 위해 고안되었습니다. 완전 탐색이 모든 가능한 해를 탐색하는 것과 달리, 분지 한정법은 **'현재까지 찾은 최선의 해'**를 기준으로 삼아, 그보다 나쁜 결과를 낼 가능성이 있는 부분 공간은 아예 탐색하지 않도록 가지치기(Pruning)합니다.

이 알고리즘은 크게 두 가지 핵심 단계로 구성됩니다:

1.  **분지 (Branching)**: 현재 문제를 더 작은 하위 문제(Sub-problems)들로 재귀적으로 분할합니다. 이는 일반적으로 결정 트리를 형성하며, 각 노드는 부분 문제의 상태를 나타냅니다.
2.  **한정 (Bounding)**: 각 하위 문제의 노드에 대해, 해당 부분 공간에서 얻을 수 있는 최적해의 **하한(Bound)**을 계산합니다. 만약 이 하한이 현재까지 발견된 전역 최적해(Global Optimal Solution)보다 나쁘다면, 그 노드와 그 하위 트리는 탐색에서 제외됩니다.

## 알고리즘 동작 과정

분지 한정법의 구체적인 동작 과정은 다음과 같은 단계를 따릅니다. 일반적으로 우선순위 큐(Priority Queue)를 사용하여 가장 유망한(하한이 가장 좋은) 노드를 먼저 탐색하는 **우선순위 분지 한정법(Priority Branch and Bound)**이 효율적입니다.

### 1. 초기화
*   탐색할 노드들을 저장할 큐(또는 스택)를 초기화합니다.
*   초기 노드(전체 문제)를 큐에 삽입합니다.
*   현재까지 찾은 최선의 해의 값(`best_bound`)을 무한대(최소화 문제의 경우) 또는 음의 무한대(최대화 문제의 경우)로 설정합니다.

### 2. 반복 탐색
큐가 빌 때까지 다음 과정을 반복합니다.

*   **노드 추출**: 큐에서 가장 우선순위가 높은 노드(현재까지 계산된 하한이 가장 좋은 노드)를 꺼냅니다.
*   **한정 조건 확인**:
    *   만약 현재 노드의 하한이 `best_bound`보다 나쁘다면(최소화 문제에서 `lower_bound >= best_bound`), 이 노드는 더 이상 탐색할 가치가 없으므로 버립니다.
    *   만약 현재 노드가 리프 노드(Leaf Node)이고, 그 해가 `best_bound`보다 좋다면, `best_bound`를 업데이트하고 최적해 후보를 기록합니다.
*   **분지 (Branching)**:
    *   현재 노드가 리프 노드가 아니라면, 이를 더 작은 하위 문제들로 분할합니다.
    *   각 하위 문제의 하한을 계산합니다.
    *   계산된 하한이 `best_bound`보다 나은 경우만 해당 하위 노드를 큐에 삽입합니다.

### 3. 종료
*   큐가 비어지면 탐색이 종료되며, 기록된 `best_bound`가 최적해가 됩니다.

## 주요 특징 및 장단점

### 장점
*   **완전 탐색보다 효율적**: 불필요한 탐색 경로를 조기에 차단함으로써 계산 시간을 크게 줄일 수 있습니다.
*   **최적해 보장**: 모든 유망한 경로를 탐색하므로, 반드시 전역 최적해(Global Optimum)를 찾을 수 있습니다. (휴리스틱 방법과 달리 최적해를 보장한다는 점이 중요합니다.)
*   **유연성**: 다양한 조합 최적화 문제에 적용 가능한 일반적인 프레임워크를 제공합니다.

### 단점
*   **최악의 경우 성능**: 한정(Bounding) 함수가 매우 약하거나 문제의 구조상 가지치기가 거의 일어나지 않는 경우, 사실상 완전 탐색과 동일한 성능을 보일 수 있습니다.
*   **메모리 사용량**: 우선순위 큐를 사용하므로, 탐색 중인 노드 수가 많을 경우 메모리 소비가 클 수 있습니다.
*   **한정 함수 설계의 어려움**: 알고리즘의 효율성은 한정 함수(Bounding Function)의 품질에 크게 의존합니다.tight한 하한을 계산하는 함수를 설계하는 것이 핵심 과제입니다.

## 적용 예시: 배낭 문제 (Knapsack Problem)

배낭 문제는 주어진 무게 제한 내에서 최대 가치의 물건을 선택하는 문제입니다. 분지 한정법을 적용할 때의 구체적인 전략은 다음과 같습니다.

1.  **분지**: 각 물건을 '포함'하거나 '포함하지 않음'으로 나누어 트리를 구성합니다.
2.  **한정 (하한 계산)**:
    *   현재 노드까지 선택된 물건의 가치 합을 `current_value`라고 합니다.
    *   남은 무게에 대해, 물건을 무게 대비 가치 밀도(Value/Weight)가 높은 순서로 가상의 '분할 배낭 문제(Fractional Knapsack Problem)'를 풀어 최대 추가 가치를 계산합니다.
    *   `lower_bound = current_value + fractional_knapsack_value`
    *   이 `lower_bound`가 현재까지 찾은 최적해(`best_value`)보다 작으면 해당 경로를 가지치기합니다.

이러한 접근법은 정수 제약 조건을 완화하여 쉽게 하한을 계산할 수 있게 해주며, 탐색 효율을 극대화합니다.

## 관련 알고리즘 및 비교

| 알고리즘 | 특징 | 분지 한정법과의 비교 |
| :--- | :--- | :--- |
| **완전 탐색 (Brute Force)** | 모든 경우의 수 탐색 | 분지 한정법은 완전 탐색의 가지치기 버전으로, 효율성이 훨씬 높음 |
| **동적 계획법 (DP)** | 부분 문제의 해를 저장하여 재사용 | DP는 특정 구조(중복 부분 문제, 최적 부분 구조)가 있을 때만 적용 가능. 분지 한정법은 더 일반적인 문제에 적용 가능 |
| **유전 알고리즘 (GA)** | 확률적 탐색, 휴리스틱 | GA는 근사해를 빠르게 찾으나 최적해 보장이 없음. 분지 한정법은 최적해를 찾으나 계산 비용이 큼 |
| **A* 알고리즘** | 휴리스틱 함수를 이용한 경로 탐색 | A*는 그래프 탐색에 특화됨. 분지 한정법은 조합 최적화 문제에 더 널리 사용됨 |

## 결론

분지 한정법은 조합 최적화 문제를 해결하는 데 있어 이론적으로 타당하고 실용적인 강력한 도구입니다. 특히 한정 함수를 어떻게 설계하느냐에 따라 알고리즘의 성능이 결정적으로 달라지므로, 문제의 특성에 맞는tight한 하한을 계산하는 전략이 중요합니다. 현대의 최적화 솔버(Solver)들은 분지 한정법을 기반으로 하며, 선형 계획법(LP Relaxation) 등을 통해 한정 값을 정교하게 계산하여 복잡한 실세계 문제를 해결하고 있습니다.

## 참고 문헌 및 관련 문서

*   [조합 최적화](Combination_Optimization)
*   [정수 계획법](Integer_Programming)
*   [여행하는 외판원 문제](Traveling_Salesman_Problem)
*   [가지치기 (가지치기 기법)](Pruning)
*   Cormen, T. H., et al. *Introduction to Algorithms*. MIT Press. (분지 한정법의 이론적 배경 설명)