# [06-06] 분기 한정 (Branch & Bound)
분기 한정은 백트래킹에 "한계값" 개념을 추가하여 최적화 문제를 효율적으로 해결하는 알고리즘 설계 기법입니다.
🎯 분기 한정 (Branch & Bound) 이란 무엇인가
분기 한정의 기본 개념
분기 한정은 백트래킹의 확장된 버전으로, 최적해를 찾는 문제에 특화되어 있습니다.
실생활 비유:
여행 경로 찾기:
백트래킹:
- 모든 경로를 시도
- 불가능한 경로는 포기
- "갈 수 있는가?"만 확인
분기 한정:
- 모든 경로를 시도
- 불가능한 경로는 포기
- "갈 수 있는가?" + "지금까지 최선보다 나은가?" 확인
- "이 경로로 가면 아무리 잘해도 100km인데,
이미 80km 경로를 찾았네? 포기!"핵심 아이디어:
현재까지 찾은 최선의 해: 100
새로운 경로 탐색 중:
현재까지 비용: 70
남은 최소 비용(낙관적 추정): 40
예상 총 비용: 70 + 40 = 110
110 > 100 → 이 경로는 절대 최선이 될 수 없음!
→ 포기하고 다른 경로 시도백트래킹 vs 분기 한정
두 기법의 차이를 명확히 이해하는 것이 중요합니다.
백트래킹:
목표: 조건을 만족하는 해 찾기
예: N-Queen, 스도쿠
특징:
- "가능한가?"만 판단
- 모든 가능한 해를 찾을 수 있음
- 최적화 문제에는 비효율적
예: 경로 찾기
- A → B → C 경로 발견 (100km)
- A → D → C 경로도 발견 (80km)
- 둘 다 "가능"하므로 둘 다 탐색분기 한정:
목표: 최적해 찾기 (최소/최대)
예: 최단 경로, 최소 비용, 최대 가치
특징:
- "가능한가?" + "최적인가?" 판단
- 현재까지의 최선을 기억
- 최선보다 나쁜 경로는 조기 포기
예: 최단 경로 찾기
- A → B → C 경로 발견 (100km) - 현재 최선
- A → D 까지 왔는데 이미 90km
→ 남은 거리 최소 20km
→ 총 110km 이상 확정
→ 100km보다 나쁨! 포기!비교 표:
특징 백트래킹 분기 한정
----------------------------------------------
목표 해 찾기 최적해 찾기
판단 기준 가능성 가능성 + 최적성
사용하는 값 없음 한계값(bound)
탐색 방식 DFS DFS 또는 BFS
적합한 문제 제약 만족 최적화분기 한정의 핵심 요소
분기 한정은 다음 요소들로 구성됩니다:
1. 분기 (Branch)
문제를 더 작은 부분 문제로 나눕니다.
for choice in choices:
explore(choice)2. 한계 (Bound)
현재 경로로 얻을 수 있는 최선의 결과를 추정합니다.
estimated_best = current_cost + optimistic_remaining_cost3. 가지치기 (Prune)
추정값이 현재 최선보다 나쁘면 포기합니다.
if estimated_best > current_best:
return # 포기!4. 최선 추적
지금까지 찾은 최선의 해를 계속 업데이트합니다.
if solution_cost < best_cost:
best_cost = solution_cost
best_solution = solution한계 함수 (Bounding Function)의 중요성
분기 한정에서 가장 중요한 것은 한계 함수입니다.
한계 함수란?
현재 상태에서 앞으로 얻을 수 있는 최선의 결과를 추정하는 함수입니다.
현재 상태: 3개 도시 방문, 거리 50km
남은 도시: 2개
한계 함수 계산:
"남은 2개 도시 사이의 최단 거리는?"
→ 최소 20km
한계값: 50 + 20 = 70km
의미: "이 경로로 가면 아무리 잘해도 70km 이상"좋은 한계 함수의 조건:
1. 낙관적 추정 (Optimistic Estimate):
- 실제보다 낮게 추정 (최소화 문제)
- 실제보다 높게 추정 (최대화 문제)
- 왜? 진짜 최적해를 놓치지 않기 위해
2. 빠른 계산:
- 한계 함수 계산이 너무 느리면 의미 없음
- 간단한 근사값 사용
3. 정확할수록 좋음:
- 더 많은 가지치기 가능
- 하지만 계산 비용과 트레이드오프예시:
0-1 배낭 문제:
나쁜 한계 함수:
"남은 물건의 가치를 모두 더함"
→ 무게 제한 무시 → 너무 낙관적 → 가지치기 적음
좋은 한계 함수:
"남은 물건을 쪼갤 수 있다고 가정"
→ 무게 고려 → 적절히 낙관적 → 가지치기 많음이제 구체적인 문제로 분기 한정을 이해해 봅시다.
🎒 0-1 배낭 문제
0-1 배낭 문제란?
0-1 배낭 문제는 분기 한정을 설명하는 대표적인 예제입니다. 앞서 동적 계획법에서도 다뤘지만, 분기 한정으로도 풀 수 있습니다.
문제 복습:
배낭 용량: 10kg
물건 (무게, 가치):
A: 2kg, $40
B: 3kg, $50
C: 5kg, $60
D: 4kg, $70
목표: 최대 가치
제약: 각 물건은 0개 또는 1개만 (쪼갤 수 없음)왜 분기 한정으로 푸는가?
- 최적화 문제: 최대 가치를 찾아야 함
- 탐색 공간이 큼: 2^4 = 16가지 조합
- 한계 계산 가능: 남은 물건으로 얻을 수 있는 최대 가치 추정
분기 한정 접근
전략:
1. 각 물건마다 "담기" 또는 "안 담기" 선택
2. 한계값 계산:
"현재 가치 + 남은 물건으로 얻을 수 있는 최대 가치"
3. 한계값이 현재 최선보다 낮으면 포기
4. 가능한 모든 경로 탐색하여 최적해 찾기한계 함수 설계:
현재 상태:
- 현재 가치: $90
- 현재 무게: 5kg
- 남은 용량: 5kg
남은 물건:
C: 5kg, $60
D: 4kg, $70
한계 계산 (낙관적 추정):
"물건을 쪼갤 수 있다고 가정"
D를 4kg 담음: $70
C를 1kg만 담음: $60 × (1/5) = $12
(실제로는 못 쪼개지만 추정용)
한계값: $90 + $70 + $12 = $172
의미: "이 경로로 가면 최대 $172까지 가능"구현
def knapsack_branch_bound(weights, values, capacity):
"""
0-1 배낭 문제 - 분기 한정
weights: 물건들의 무게 리스트
values: 물건들의 가치 리스트
capacity: 배낭 용량
Returns: (최대 가치, 선택한 물건 리스트)
"""
n = len(weights)
# 가치/무게 비율로 정렬 (한계 계산에 사용)
# [(비율, 인덱스), ...]
items = [(values[i] / weights[i], i) for i in range(n)]
items.sort(reverse=True) # 비율 높은 순
# 전역 변수: 최선의 해
best_value = 0
best_items = []
def calculate_bound(index, current_weight, current_value):
"""
한계 함수: 현재 상태에서 얻을 수 있는 최대 가치 추정
index: 다음으로 고려할 물건 인덱스
current_weight: 현재까지 담은 무게
current_value: 현재까지 담은 가치
Returns: 한계값 (낙관적 추정)
방법:
1. 현재 가치에서 시작
2. 남은 물건을 가치/무게 비율 순으로
3. 들어가는 것은 전부 담기
4. 들어가지 않는 것은 쪼개서 담기 (추정용)
"""
# 남은 용량
remaining_capacity = capacity - current_weight
# 현재 가치에서 시작
bound = current_value
# 남은 물건들을 순회
for i in range(index, n):
_, item_idx = items[i]
weight = weights[item_idx]
value = values[item_idx]
# 물건 전체를 담을 수 있으면
if remaining_capacity >= weight:
# 전체를 담기
remaining_capacity -= weight
bound += value
else:
# 일부만 담기 (쪼개기, 추정용!)
# 비율만큼의 가치 추가
bound += value * (remaining_capacity / weight)
break # 용량 가득 참
return bound
def branch_and_bound(index, current_weight, current_value, selected):
"""
분기 한정 재귀 함수
index: 현재 고려 중인 물건 인덱스
current_weight: 현재까지 담은 무게
current_value: 현재까지 담은 가치
selected: 현재까지 선택한 물건들
"""
nonlocal best_value, best_items
# ===== 기저 조건 =====
# 모든 물건을 고려했으면
if index == n:
# 현재 해가 최선이면 업데이트
if current_value > best_value:
best_value = current_value
best_items = selected[:]
return
# ===== 현재 물건 정보 =====
_, item_idx = items[index]
weight = weights[item_idx]
value = values[item_idx]
# ===== 선택 1: 현재 물건을 담기 =====
if current_weight + weight <= capacity:
# 1. 선택
selected.append(item_idx)
# 2. 탐색
branch_and_bound(
index + 1,
current_weight + weight,
current_value + value,
selected
)
# 3. 되돌리기
selected.pop()
# ===== 선택 2: 현재 물건을 담지 않기 =====
# 하지만 그 전에 한계 확인!
# 한계값 계산
bound = calculate_bound(index + 1, current_weight, current_value)
# 가지치기: 한계값이 현재 최선보다 낮으면
if bound <= best_value:
# 이 경로는 최선이 될 수 없음!
return # 포기
# 한계값이 유망하면 계속 탐색
branch_and_bound(
index + 1,
current_weight,
current_value,
selected
)
# 초기 호출
branch_and_bound(0, 0, 0, [])
return best_value, best_items
# 사용 예시
weights = [2, 3, 5, 4]
values = [40, 50, 60, 70]
capacity = 10
max_value, selected_items = knapsack_branch_bound(weights, values, capacity)
print(f"최대 가치: ${max_value}")
print(f"선택한 물건 인덱스: {selected_items}")
# 선택한 물건 상세
total_weight = 0
total_value = 0
for idx in selected_items:
print(f" 물건 {idx}: {weights[idx]}kg, ${values[idx]}")
total_weight += weights[idx]
total_value += values[idx]
print(f"총 무게: {total_weight}kg")
print(f"총 가치: ${total_value}")실행 과정 추적:
초기: best_value = 0
branch_and_bound(0, 0kg, $0, [])
├─ 물건 0 담기 (2kg, $40)
│ branch_and_bound(1, 2kg, $40, [0])
│
│ ├─ 물건 1 담기 (3kg, $50)
│ │ branch_and_bound(2, 5kg, $90, [0,1])
│ │
│ │ ├─ 물건 2 담기 (5kg, $60)
│ │ │ branch_and_bound(3, 10kg, $150, [0,1,2])
│ │ │
│ │ │ └─ 물건 3 담기? 불가 (용량 초과)
│ │ │ bound 계산: $150 (변화 없음)
│ │ │ best_value 업데이트: $150 ✓
│ │ │
│ │ └─ 물건 2 안 담기
│ │ bound = $90 + $70 + ($60×1/5) = $172
│ │ $172 > $150 → 유망, 계속
│ │
│ │ branch_and_bound(3, 5kg, $90, [0,1])
│ │ └─ 물건 3 담기 (4kg, $70)
│ │ branch_and_bound(4, 9kg, $160, [0,1,3])
│ │ best_value 업데이트: $160 ✓
│ │
│ └─ 물건 1 안 담기
│ bound = $40 + $70 + $60 + ($50×1/5) = $180
│ $180 > $160 → 유망, 계속
│ ... (계속)
│
└─ 물건 0 안 담기
bound = $70 + $60 + $50 + ($40×2/2) = $220
$220 > $160 → 유망, 계속
... (계속)
최종: best_value = $160, best_items = [0, 1, 3]🗺️ 외판원 문제 (TSP, Traveling Salesman Problem)
외판원 문제란?
외판원 문제는 컴퓨터 과학에서 가장 유명한 최적화 문제 중 하나입니다.
문제 설명:
N개의 도시를 모두 방문하고 출발점으로 돌아오는 최단 경로를 찾아라.
조건:
- 각 도시는 정확히 한 번씩만 방문
- 모든 도시를 방문해야 함
- 출발점으로 돌아와야 함
예: 4개 도시
A → B → C → D → A
총 거리 = AB + BC + CD + DA왜 어려운가?
도시 수에 따른 경우의 수:
4개 도시: 3! = 6가지
5개 도시: 4! = 24가지
10개 도시: 9! = 362,880가지
20개 도시: 19! = 121,645,100,408,832,000가지
→ 완전 탐색은 불가능!
→ 분기 한정으로 많은 경로를 조기 포기분기 한정 접근
전략:
1. 부분 경로를 순차적으로 구성
2. 각 단계에서 한계값 계산:
"현재 경로 + 남은 도시들의 최소 비용"
3. 한계값이 현재 최단 경로보다 길면 포기
4. 모든 도시를 방문하면 경로 완성한계 함수 설계:
현재 경로: A → B → C (거리: 50km)
방문한 도시: {A, B, C}
남은 도시: {D, E}
한계 계산:
1. 현재 거리: 50km
2. C에서 나가는 최소 비용:
C → D: 20km
C → E: 15km
최소: 15km
3. D의 최소 비용 (들어오기 + 나가기):
들어오기 최소: 10km (B → D)
나가기 최소: 15km (D → E)
합: 25km / 2 = 12.5km (평균)
4. E의 최소 비용:
들어오기 최소: 10km
나가기 최소: 20km
합: 30km / 2 = 15km
5. E에서 A로 돌아오기: 25km
한계값: 50 + 15 + 12.5 + 15 + 25 = 117.5km
의미: "이 경로로 가면 최소 117.5km"간단한 구현
def tsp_branch_bound(dist_matrix):
"""
외판원 문제 - 분기 한정
dist_matrix: 거리 행렬 * dist_matrix[i][j] = 도시 i에서 j로의 거리
Returns: (최단 거리, 최단 경로)
"""
n = len(dist_matrix)
# 전역 변수: 최선의 해
best_cost = float('inf')
best_path = []
def calculate_bound(path, visited):
"""
한계 함수: 현재 경로의 최소 가능 비용 추정
path: 현재까지의 경로 [0, 2, 1, ...]
visited: 방문한 도시 집합 {0, 2, 1}
Returns: 한계값 (낙관적 추정)
계산 방법:
1. 현재 경로의 비용
2. 현재 도시에서 나가는 최소 비용
3. 방문 안 한 도시들의 최소 비용 (들어오기+나가기)
4. 마지막 도시에서 시작점으로 최소 비용
"""
bound = 0
# 1. 현재 경로 비용
for i in range(len(path) - 1):
bound += dist_matrix[path[i]][path[i + 1]]
# 2. 현재 도시에서 나가는 최소 비용
if len(path) < n:
current = path[-1]
min_out = float('inf')
for j in range(n):
if j not in visited:
min_out = min(min_out, dist_matrix[current][j])
if min_out != float('inf'):
bound += min_out
# 3. 방문 안 한 도시들의 최소 비용
for city in range(n):
if city not in visited and city != 0:
# 들어오는 최소 비용
min_in = min(dist_matrix[i][city]
for i in range(n) if i != city)
# 나가는 최소 비용
min_out = min(dist_matrix[city][j]
for j in range(n) if j != city)
# 평균 (낙관적 추정)
bound += (min_in + min_out) / 2
# 4. 마지막에서 시작점으로
if len(path) == n:
bound += dist_matrix[path[-1]][path[0]]
return bound
def branch_and_bound(path, visited, current_cost):
"""
분기 한정 재귀 함수
path: 현재 경로
visited: 방문한 도시 집합
current_cost: 현재까지의 비용
"""
nonlocal best_cost, best_path
# ===== 기저 조건 =====
# 모든 도시를 방문했으면
if len(path) == n:
# 시작점으로 돌아가는 비용 추가
total_cost = current_cost + dist_matrix[path[-1]][path[0]]
# 최선이면 업데이트
if total_cost < best_cost:
best_cost = total_cost
best_path = path + [path[0]]
return
# ===== 다음 도시 선택 =====
current_city = path[-1]
for next_city in range(n):
# 이미 방문한 도시는 건너뛰기
if next_city in visited:
continue
# 다음 도시로 가는 비용
edge_cost = dist_matrix[current_city][next_city]
new_cost = current_cost + edge_cost
# 한계값 계산
new_path = path + [next_city]
new_visited = visited | {next_city} # 이미 방문한 도시 집합(visited)과
# 새로운 도시({next_city})의 합집합(|)을 구함
# 리스트보다 집합(set)을 사용하면 특정 도시를 방문했는지 확인하는 속도가 훨씬 빠릅
bound = calculate_bound(new_path, new_visited)
# 가지치기: 한계값이 현재 최선보다 크면
if bound >= best_cost:
continue # 포기!
# 유망하면 계속 탐색
branch_and_bound(new_path, new_visited, new_cost)
# 도시 0에서 시작
branch_and_bound([0], {0}, 0)
return best_cost, best_path
# 사용 예시
# 거리 행렬 (4개 도시)
dist_matrix = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
min_cost, min_path = tsp_branch_bound(dist_matrix)
print(f"최단 거리: {min_cost}km")
print(f"최단 경로: {' → '.join(map(str, min_path))}")
# 경로 상세
print("\n경로 상세:")
for i in range(len(min_path) - 1):
from_city = min_path[i]
to_city = min_path[i + 1]
distance = dist_matrix[from_city][to_city]
print(f" {from_city} → {to_city}: {distance}km")💡 실무 팁
분기 한정을 사용할 때
-
최적화 문제
- 최소/최대 값을 찾는 문제
- 단순히 "가능한 해"가 아닌 "최선의 해"
-
한계 계산이 가능한 문제
- 남은 부분의 최선을 추정할 수 있어야 함
- 추정이 불가능하면 분기 한정 사용 어려움
-
탐색 공간이 큰 문제
- 완전 탐색은 불가능하지만
- 많은 경로를 조기에 포기할 수 있는 경우
좋은 한계 함수 만들기
# 나쁜 한계 함수: 너무 낙관적
def bad_bound(state):
return 0 # 항상 0 → 가지치기 안 됨
# 나쁜 한계 함수: 계산 비용이 큼
def slow_bound(state):
# 복잡한 최적화 문제 풀기...
return expensive_calculation()
# 좋은 한계 함수: 적절히 낙관적 + 빠른 계산
def good_bound(state):
# 간단한 휴리스틱으로 빠르게 추정
return simple_optimistic_estimate(state)BFS vs DFS
분기 한정은 DFS와 BFS 둘 다 사용 가능:
# DFS 스타일 (재귀)
def dfs_branch_bound(state):
for choice in choices:
if bound(choice) < best:
dfs_branch_bound(choice)
# BFS 스타일 (우선순위 큐)
import heapq
def bfs_branch_bound():
queue = [(0, initial_state)] # (bound, state)
while queue:
bound, state = heapq.heappop(queue)
if bound >= best:
continue # 가지치기
for choice in get_choices(state):
new_bound = calculate_bound(choice)
heapq.heappush(queue, (new_bound, choice))BFS는 더 좋은 경로를 먼저 탐색하므로 효율적일 수 있습니다.
🎯 핵심 정리
분기 한정의 본질
- 백트래킹 + 한계값
- 최적화 문제에 특화
- 현재 최선을 추적하며 탐색
주요 구성 요소
1. 분기 (Branch): 문제를 부분 문제로 나누기
2. 한계 (Bound): 최선의 결과 추정
3. 가지치기 (Prune): 나쁜 경로 조기 포기
4. 최선 추적: 지금까지의 최선 기억한계 함수
특성 설명
----------------------------------------
낙관적 추정 실제보다 좋게 추정 (안전)
빠른 계산 너무 복잡하면 역효과
정확할수록 좋음 더 많은 가지치기 가능백트래킹 vs 분기 한정
특징 백트래킹 분기 한정
---------------------------------------------
목표 해 찾기 최적해 찾기
추가 정보 없음 한계값
적용 문제 제약 만족 최적화
효율성 보통 더 효율적 (최적화 문제)시간복잡도
최악의 경우: 백트래킹과 동일 (O(2^n), O(n!) 등)
평균적으로: 훨씬 빠름 (많은 가지치기)
예: TSP
완전 탐색: O(n!)
분기 한정: O(n!) 하지만 실제로는 훨씬 적은 경로 탐색🔗 다음 글에서는
[06-07] 무작위 알고리즘 (Randomized Algorithms)
- 무작위 알고리즘의 개념: 확률을 이용하여 문제를 해결하는 기법
- 라스베이거스 알고리즘: 항상 정확하지만 실행 시간이 확률적
- 몬테카를로 알고리즘: 빠르지만 일정 확률로 오류 가능
- 퀵 정렬의 랜덤 피벗: 최악의 경우를 회피하는 실용적 기법
이전 글: [06-05] 백트래킹
다음 글: [06-07] 무작위 알고리즘
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자