4-10. 탐색 알고리즘: Branch and Bound (분기 한정법)

1. 분기 한정법 (Branch and Bound)의 소개

분기 한정법(Branch and Bound, B&B)은 최적화 문제를 해결하기 위한 강력한 알고리즘입니다. 특히, 조합 최적화(combinatorial optimization) 문제, 즉 가능한 해의 수가 유한하지만, 그 중에서 가장 좋은 해를 찾아야 하는 문제에 효과적입니다. 예를 들어, 외판원 문제(Traveling Salesperson Problem, TSP), 배낭 문제(Knapsack Problem), 정수 선형 계획법(Integer Linear Programming)과 같은 NP-hard 문제의 해를 구하는 데 활용됩니다. B&B는 가능한 해 공간을 체계적으로 탐색하여 불필요한 탐색을 줄이고, 최적해를 효율적으로 찾도록 설계되었습니다.

B&B의 핵심 아이디어는 다음과 같습니다.

1. 분기(Branching): 문제의 해 공간을 더 작은 하위 문제(subproblem)들로 분할합니다. 이는 탐색 트리의 노드를 생성하는 과정과 같습니다. 각 노드는 문제의 특정 부분 집합에 해당합니다.
2. 한정(Bounding): 각 하위 문제에 대해 최적해의 상한(upper bound) 또는 하한(lower bound)을 계산합니다. 이를 통해 해당 하위 문제 내에서 더 이상 탐색할 필요가 없는 경우를 판단합니다.
3. 탐색(Searching): 최적해를 찾기 위해 탐색 트리를 탐색합니다. 탐색 과정에서 상한/하한 정보를 활용하여 불필요한 노드를 제거(pruning)합니다.

B&B는 탐색 트리를 구축하고, 각 노드에서 가능한 해의 범위를 좁혀나가면서 최적해를 찾아가는 탐욕적(greedy) 방식과는 다른 접근 방식을 취합니다. 탐욕적 방식은 각 단계에서 최선의 선택을 하지만, 전체 문제에 대한 최적해를 보장하지 않습니다. 반면, B&B는 모든 가능한 해를 고려하면서도, 한정 과정을 통해 불필요한 탐색을 제거하여 효율성을 높입니다.

2. 분기 한정법의 핵심 원리

B&B 알고리즘은 탐색 트리를 기반으로 작동하며, 각 노드는 부분적인 해를 나타냅니다. 알고리즘의 주요 단계는 다음과 같습니다.

1) 분기(Branching)

분기 단계는 문제의 해 공간을 더 작은 하위 문제로 나누는 과정입니다. 탐색 트리의 각 노드는 분기 과정을 통해 자식 노드들을 생성합니다. 분기 전략은 문제의 특성에 따라 다르게 적용될 수 있습니다.

• 예시 (TSP): 외판원 문제에서 분기는 특정 도시 간의 경로를 포함하거나 제외하는 방식으로 이루어질 수 있습니다. 예를 들어, 노드 A에서 분기를 통해 "도시 1에서 도시 2로 가는 경로를 포함"하는 하위 문제와 "도시 1에서 도시 2로 가는 경로를 제외"하는 하위 문제를 생성할 수 있습니다.
• 예시 (배낭 문제): 배낭 문제에서 분기는 특정 물건을 배낭에 넣거나 넣지 않는 방식으로 이루어질 수 있습니다.

2) 한정(Bounding)

한정 단계는 각 하위 문제에 대해 최적해의 상한 또는 하한을 계산하는 과정입니다. 이 경계 값은 해당 하위 문제 내에서 가능한 최적해의 범위를 제한합니다. 이 경계 값을 계산하는 방법은 문제의 종류에 따라 다릅니다.

• 최소화 문제의 경우: 하한을 계산합니다. 하한보다 더 나쁜 해는 고려할 필요가 없습니다.
• 최대화 문제의 경우: 상한을 계산합니다. 상한보다 더 좋은 해는 고려할 필요가 없습니다.

경계 값 계산은 다음과 같은 다양한 방법을 사용할 수 있습니다.

• 완화(Relaxation): 원래 문제의 제약 조건을 완화하여 얻은 문제를 풉니다. 예를 들어, 정수 선형 계획법에서 정수 제약을 제거하여 선형 계획법으로 문제를 풀 수 있습니다.
• 휴리스틱(Heuristics): 빠른 계산을 위해 근사적인 해를 구하는 방법입니다.
• 문제 특정적인 방법: 문제의 특성을 활용하여 경계 값을 계산합니다.

3) 탐색(Searching) 및 가지치기(Pruning)

탐색 단계는 탐색 트리를 탐색하면서 최적해를 찾는 과정입니다. 탐색은 다음과 같은 방식으로 이루어집니다.

• 노드 선택: 탐색할 노드를 선택합니다. 보통, 가장 좋은 경계 값을 가진 노드를 선택합니다 (최적해 가능성이 높은 노드).
• 가지치기(Pruning): 한정 단계에서 계산된 경계 값을 사용하여 더 이상 탐색할 필요가 없는 노드를 제거합니다. 가지치기는 B&B 알고리즘의 핵심적인 효율성 향상 방법입니다. 가지치기는 다음과 같은 경우에 수행됩니다.
  • 하한(최소화 문제) / 상한(최대화 문제) 초과: 노드의 하한/상한이 현재까지 찾은 최적해보다 나쁜 경우, 해당 노드를 더 이상 탐색할 필요가 없습니다.
  • 불가능성(Infeasibility): 노드가 나타내는 하위 문제가 실행 불가능한 경우, 해당 노드를 탐색할 필요가 없습니다.
  • 정수해: 노드가 정수해를 가지는 경우, 해당 해가 최적해인지 확인하고, 만약 최적해라면 다른 노드를 탐색할 필요가 없습니다.

가지치기의 종류

• Bound Pruning (경계 기반 가지치기): 현재까지 찾은 최적해의 값과 노드의 경계 값을 비교하여 가지를 잘라냅니다.
• Infeasibility Pruning (불가능성 기반 가지치기): 해당 노드에서 더 이상 해를 찾을 수 없는 경우, 해당 노드를 잘라냅니다.
• Optimality Pruning (최적성 기반 가지치기): 노드가 이미 최적해를 포함하고 있는 경우, 해당 노드를 잘라냅니다.

4) 종료 조건

탐색은 다음과 같은 조건 중 하나가 충족되면 종료됩니다.

• 모든 노드가 탐색: 모든 노드를 탐색했거나, 가지치기 되었을 때
• 최적해 발견: 최적해를 찾았을 때

3. 분기 한정법의 예시: 배낭 문제 (Knapsack Problem)

배낭 문제(Knapsack Problem)는 B&B 알고리즘의 동작 방식을 이해하기에 좋은 예시입니다. 배낭 문제는 다음과 같이 정의됩니다.

• n개의 물건이 있습니다. 각 물건 i는 가치(value) vᵢ와 무게(weight) wᵢ를 가집니다.
• 배낭은 최대 무게 용량 W를 가지고 있습니다.
• 목표는 배낭의 용량을 초과하지 않으면서, 배낭에 담긴 물건들의 총 가치를 최대화하는 것입니다.

수식 표현

$$ \text{maximize} \sum_{i=1}^{n} v_i x_i \\ \text{subject to} \sum_{i=1}^{n} w_i x_i \le W \\ x_i \in \{0, 1\} \text{ for } i = 1, 2, ..., n $$

여기서 xᵢ는 물건 i를 배낭에 넣으면 1, 넣지 않으면 0입니다.

1) 분기(Branching)

분기는 각 물건을 배낭에 넣거나 넣지 않는 방식으로 수행됩니다. 탐색 트리는 이진 트리 형태를 가지며, 각 레벨은 하나의 물건에 해당합니다.

• 레벨 0: 루트 노드 (아무것도 선택하지 않음)
• 레벨 1: 물건 1을 넣는 경우, 넣지 않는 경우
• 레벨 2: 물건 2를 넣는 경우, 넣지 않는 경우
• ...

2) 한정(Bounding)

배낭 문제의 경우, 완화를 통해 상한을 계산할 수 있습니다. 완화는 다음과 같이 수행됩니다.

• 0-1 제약 조건 완화: xᵢ를 0과 1 사이의 실수로 간주합니다. 즉, 0 <= xᵢ <= 1
• 그리디 알고리즘 활용: 각 물건의 가치/무게 비율(vᵢ / wᵢ)을 계산하고, 이 비율이 높은 순서대로 물건을 배낭에 넣습니다.

예를 들어, 물건 1, 2, 3이 있고, 각 물건의 정보가 다음과 같다고 가정합니다.

1. 루트 노드: 아무것도 선택하지 않음. 상한은 그리디 알고리즘으로 계산합니다.
   • 물건 1을 넣음 (무게 10, 가치 60)
   • 물건 2를 넣음 (무게 20, 가치 100)
   • 남은 용량 20으로 물건 3을 20/30만큼 넣음 (가치 80)
   • 상한: 60 + 100 + 80 = 240
2. 물건 1을 넣는 경우:
   • 물건 1을 넣음 (무게 10, 가치 60). 남은 용량 40.
   • 물건 2를 넣음 (무게 20, 가치 100)
   • 남은 용량 20으로 물건 3을 20/30만큼 넣음 (가치 80)
   • 상한: 60 + 100 + 80 = 240
3. 물건 1을 넣지 않는 경우:
   • 물건 2를 넣음 (무게 20, 가치 100)
   • 물건 3을 넣음 (무게 30, 가치 120)
   • 상한: 100 + 120 = 220

3) 탐색(Searching) 및 가지치기(Pruning)

탐색은 상한을 기준으로 이루어집니다.

1. 루트 노드에서 시작: 상한은 240입니다. 현재까지 찾은 최적해는 없습니다.
2. 물건 1을 넣는 경우: 상한은 240입니다.
3. 물건 1을 넣지 않는 경우: 상한은 220입니다.
4. 가지치기: 만약 어떤 노드의 상한이 현재까지 찾은 최적해보다 작다면, 해당 노드를 가지치기할 수 있습니다.

4) 종료

모든 노드를 탐색하거나 가지치기 되면 종료됩니다. 최적해를 찾은 경우, 해당 해를 반환합니다.

4. 분기 한정법의 장단점 및 고려 사항

1) 장점

• 최적해 보장: B&B는 모든 가능한 해를 체계적으로 탐색하므로, 최적해를 보장합니다.
• 다양한 문제 적용: 조합 최적화 문제의 다양한 유형에 적용 가능합니다.
• 효율적인 탐색: 가지치기 과정을 통해 불필요한 탐색을 줄여 효율성을 높입니다.

2) 단점

• 시간 복잡도: 최악의 경우, 모든 해를 탐색해야 할 수 있으므로, 지수 시간 복잡도를 가질 수 있습니다.
• 구현 복잡성: 문제의 특성에 맞는 분기 및 한정 전략을 설계해야 하므로, 구현이 복잡할 수 있습니다.
• 메모리 사용량: 탐색 트리를 저장하기 위해 메모리가 많이 필요할 수 있습니다.

3) 고려 사항

• 분기 전략 선택: 효율적인 분기 전략은 탐색 트리의 크기를 줄이는 데 중요한 역할을 합니다.
• 한정 전략 선택: 좋은 경계 값 계산 방법은 가지치기의 효율성을 높입니다.
• 탐색 순서: 어떤 노드를 먼저 탐색할 것인지에 대한 전략(예: best-bound search, depth-first search)은 탐색 효율에 영향을 미칩니다.
• 문제 규모: 문제의 규모가 커질수록 B&B의 실행 시간도 증가하므로, 문제 규모에 따라 적절한 전략을 선택해야 합니다.

5. 분기 한정법의 응용 분야

B&B는 다양한 분야에서 활용됩니다.

• 운송 문제: 외판원 문제 (TSP), 차량 경로 문제 (VRP) 등
• 스케줄링 문제: 작업 스케줄링, 프로젝트 스케줄링 등
• 자원 할당 문제: 배낭 문제, 예산 할당 문제 등
• 통신 네트워크: 네트워크 설계, 라우팅 문제 등
• 인공지능: 게임 탐색 (예: 체스, 바둑)

6. 결론

분기 한정법은 조합 최적화 문제를 해결하기 위한 강력하고 일반적인 알고리즘입니다. B&B는 해 공간을 체계적으로 탐색하고, 가지치기를 통해 불필요한 탐색을 줄여 최적해를 효율적으로 찾을 수 있습니다. B&B의 성공적인 적용은 문제의 특성을 잘 이해하고, 적절한 분기, 한정, 탐색 전략을 선택하는 데 달려 있습니다.