🧩 알고리즘 개요
| 항목 | Backtracking | Branch and Bound (B\&B) |
|---|---|---|
| 탐색 방식 | DFS (깊이 우선 탐색) | BFS (너비 우선 탐색) |
| 기본 구성 | DFS + bound function | BFS + bound function |
| 주로 푸는 문제 | N-Queens, Subset Sum (Y/N 문제) | 0/1 Knapsack, TSP (최적화 문제) |
| 적용 대상 | 순열, 조합 등 | 최단경로, 최소비용 등 조합최적화 문제 |
| 효율성 | 단순하지만 느릴 수 있음 | 실전에서 더 신뢰성 있고 빠름 |
📐 핵심 용어 정리
| 용어 | 의미 설명 |
|---|---|
| Bound Function | 가지치기를 위한 조건 함수 (f = g + h) |
g | 지금까지 얻은 이익/비용 (정확한 값) |
h | 남은 이익/비용에 대한 최대 기대치 또는 최소 예상치 (추정값, 휴리스틱) |
| f = g + h | 전체 평가 함수. f < 현재 Best이면 비유망(non-promising) |
| Upper Bound | 최대 기대 이익 (Maximization 문제에서 사용) |
| Lower Bound | 최소 필요한 비용 (Minimization 문제에서 사용, 예: TSP) |
🔍 탐색 방법 비교
| 항목 | DFS 기반 (Backtracking) | BFS 기반 (B\&B) |
|---|---|---|
| 초기 pruning 효과 | 약함 (g만 빠르게 정확해지고, h는 불확실) | 강함 (정확한 h-value가 있으면 초반 가지치기 우수) |
| 탐색 트리의 성격 | 빠르게 깊이 파고듦 | 전체적인 넓이 기준으로 탐색 |
| 가지치기 시점 | 탐색이 진행될수록 g가 정교해지면서 일어남 | 초반에 f 계산으로 비유망 노드를 제거 |
| 적절한 경우 | 휴리스틱이 약할 때, 예/아니오 문제일 때 | 휴리스틱이 강하고, 최적화 문제일 때 |
📌 실제 설계 시 고려 사항
✅ Backtracking이 적합할 때:
- h-value를 설계/추정하기 어렵고, 휴리스틱에 대한 확신이 없을 때
- 탐색이 깊어질수록 실제 해에 가까워지는 g-value가 점점 유효해질 때
- 단순한 구조, 구현이 쉬움
✅ Branch and Bound이 적합할 때:
- h-value를 잘 추정할 수 있고, 경험적으로도 효과적인 경우
- root 근처에서 효과적인 pruning이 가능한 경우
- 실전 문제, 큰 탐색 공간에서 우수한 실행 성능을 요구할 때
🔑 교수님의 핵심 요점:
“h-value설계에 익숙하고 신뢰도가 높다면 **B\&B(BFS)**가 유리하며,
아니라면 **Backtracking(DFS)**이 더 안정적이다.”
📊 최적화 문제 유형 예시
| 문제 종류 | Bound 유형 | 예시 문제 |
|---|---|---|
| Maximization | Upper Bound | 0/1 Knapsack |
| Minimization | Lower Bound | TSP (외판원 문제) |
💡 정리된 핵심 비교 포인트
| 조건 | 추천 기법 |
|---|---|
h-value를 잘 설계할 수 있고, 예측이 잘 맞을 경우 | 🔥 B\&B (Branch and Bound) |
h-value 설계에 자신 없고 DFS가 익숙할 경우 | ✅ Backtracking (깊이 우선 탐색 기반) |
🎃 h-value 설계하는 방법
이 슬라이드는 Branch and Bound 알고리즘에서의 h-value(추정값) 설정 및 활용 방법에 대해 설명합니다. 핵심 요점을 정리해 드릴게요.
📌 주제: Branch and Bound: H-value
🔍 1. h-value란?
f = g + h(g: 정확한 값, h: 추정값)h는 앞으로 기대되는 값(예측값)을 수학적으로 표현한 것- 예시: 0/1 Knapsack 문제에서 h는 fractional knapsack 값을 이용함
🧠 2. h-value의 종류 및 활용
| 문제 유형 | h-value의 특성 | 의미 |
|---|---|---|
| 최대화 문제 (e.g. 0/1 KS) | overestimate (과대 추정) | 상한값(Upper Bound) |
| 최소화 문제 (e.g. TSP) | underestimate (과소 추정) | 하한값(Lower Bound) |
📋 3. h-value 설계 가이드라인
-
h의 범위는
0 < h < ∞로 설정 (음수 X) -
실제로 최적값을 h*라 할 때, h와의 관계성 고려
h > h*→ overestimate (보수적인 pruning)h < h*→ underestimate
-
Overestimate일 때 장점
- 최적해로 갈 수 있는 가지는 pruning되지 않음 → 안전함
- 하지만 pruning power는 떨어질 수 있음
-
좋은 h는?
0 < h* < h < ∞중 가장 작은 h가 pruning 효과가 좋음- 따라서
h = h* + α(α는 작은 값)를 추천
✅ 요약 핵심
| 항목 | 설명 |
|---|---|
h-value 설계 목적 | 앞으로 남은 최적 이익(또는 비용)을 예측하여 pruning 기준 제공 |
| 최대화 문제 | 과대 추정(overestimate) → upper bound 사용 |
| 최소화 문제 | 과소 추정(underestimate) → lower bound 사용 |
| 좋은 h-value 조건 | h = h* + α 형태처럼 작지만 안전한 추정값 선호 |
| 과제 포인트 | pruning power가 더 높은 h-value 수식 고안해보기 |
📌 h-value 추정 (Bound function)
-
h ≈ h* ± α형태로 추정h*: 실제 최적 해α: 오차 또는 여유 범위
-
정확한 h-value는 없지만, 좋은 휴리스틱 추정이 탐색의 성패를 좌우함
✨ 예: 인공지능에서는 Relaxation Technique 사용
- 제약을 완화하여 더 단순한 문제로 바꾸고 그 해를 추정치로 사용
- 예) 0/1 Knapsack → fractional KS로 relax → 추정치를
h로 사용
- 0/1 KS의
h는 fractional knapsack 문제를 기반으로 추정한 값
→ 이것은 Relaxation 기반 추정치 (h = h*)로 사용 가능
🪅 핵심 주제: Lower Bound 찾기
1 ZB(Zettabyte) 아이템을 정렬해야 하는 문제가 주어짐
정렬 문제는 이미 Lower Bound = Ω(nlogn) 이고, 그에 맞는 알고리즘도 존재하니, 무식하게 1ZB 데이터 정렬하려는 시도는 비효율적이다
근본적인 계산 복잡도의 한계를 이해하고, 현실적인 접근을 택하자
