Branch and Bound: 분기 한정
Branch and Bound, 분기 한정, B&B
정의
Branch and Bound (B&B) 는 완전 탐색을 하되, 상한/하한을 계산해 유망하지 않은 서브트리를 가지치기 하는 기법. 최적화 문제에 적용.
구성 요소
- Branching: 해 공간을 서브문제로 나누기
- Bounding: 각 서브문제의 최선 가능한 답 상한/하한 추정
- Pruning: 현재 best 보다 나쁠 수 밖에 없는 가지 제거
예시: TSP
Bound: 지금까지 비용 + 남은 도시의 MST 하한 + 남은 도시의 최소 간선 두 개.
이 bound 가 현재 best solution 보다 크면 그 가지 버림.
예시: 0-1 Knapsack
Bound: 남은 아이템을 fractional 로 채운 최대 가치.
Best-first vs DFS
- DFS: 스택 작음, 메모리 유리
- Best-first (priority queue): 유망한 것부터, 더 빠르지만 큰 큐
참고
이 글의 용어 (6개)
- 배낭 문제 (Knapsack)algorithm
- 정의 배낭 문제 (Knapsack Problem) 은 무게 제한 W 인 배낭에 가치 vi, 무게 wi 인 물건 N 개 중 일부를 담아 총 가치 최대화하는 조합 최적화 문제. NP…
- 비트마스크 DP (Bitmask DP)algorithm
- 정의 비트마스크 DP (Bitmask DP) 는 상태 공간이 부분집합 으로 표현될 때, 각 부분집합을 정수의 비트로 인코딩해 DP 상태로 삼는 기법. N ≤ 20 범위에서 O(2…
- A* (A-star) 알고리즘algorithm
- 정의 A\ 알고리즘 은 휴리스틱 기반 최단 경로 탐색 알고리즘. f(n)=g(n)+h(n) 을 평가 함수로 사용해 시작점에서 목표까지의 최단 경로를 찾는다. 1968년 Hart,…
- Brute Force: 완전 탐색algorithm
- 정의 Brute Force 는 문제의 모든 후보 해를 하나씩 검증하는 접근. 최적은 아니지만 정확 하고 명확 하며, 큰 문제에도 부분 검증 도구로 사용. 패턴 - 모든 부분집합:…
- Priority Queue / Heap: 우선순위 큐algorithm
- 정의 Priority Queue 는 우선순위가 가장 높은 원소를 O(log N) 에 pop 할 수 있는 자료구조입니다. Binary Heap 이 표준 구현. Max-heap: 부…
- TSP (Traveling Salesman Problem): 외판원 순회algorithm
- 정의 N 개 도시를 정확히 한 번씩 방문 후 시작점으로 돌아오는 최소 비용 경로. NP-hard. Bitmask DP (N ≤ 20) 상태: = "방문 집합 = mask, 현재 …
💬 댓글