1. 백트래킹과 한계점
•
백트래킹(backtracking)은 상태공간트리를 DFS로 탐색, 유망(promising)하지 않은 노드는 pruning하여 효율화.
•
그러나 bound(한계치) 계산은 오직 탐색 진행 여부만 판단하며, bound의 크고 작음 자체는 탐색 순서에 활용하지 않음.
•
깊이우선탐색(DFS)이므로, 해답까지의 경로가 길거나 pruning이 늦게 이루어지는 경우 불필요한 탐색이 많아질 수 있음.
2. 분기한정법(Branch-and-Bound) 개요
•
분기(branching): 문제의 해 공간을 분할하여 상태공간트리 구축
•
한정(bounding): 각 노드에서 해답 가능성의 상한/하한(bound)을 계산
•
전략: bound가 기존 최적해보다 나쁘면 해당 서브트리 전체를 prune
•
핵심 차이: 유망한 노드 중에서 bound가 가장 좋은 것(최고 bound)을 가진 노드를 먼저 확장(탐색 순서에 bound를 적극적으로 활용)
3. 탐색 전략
•
깊이우선검색(DFS): 백트래킹에서 사용
•
너비우선검색(BFS): 모든 레벨을 차례로 확장
•
최고우선검색(Best-First Search, BestFS):
◦
확장되지 않은 노드 중에서 bound가 가장 좋은 노드부터 확장
◦
일반적으로 우선순위 큐(priority queue, heap)를 사용하여 구현
4. 최적화 문제에서의 분기한정법
4.1 최소화 문제
•
각 노드에서 bound는 최소값에 대한 하한을 의미
•
이미 찾은 해답보다 bound가 크면(더 나쁜 경로), 해당 노드는 prune
4.2 최대화 문제
•
bound는 최대값에 대한 상한을 의미
•
이미 찾은 해답보다 bound가 작으면 해당 노드 prune
5. 0–1 배낭문제에서의 분기한정법
5.1 알고리즘 구조 (Best-First Search 예시)
•
우선순위 큐(PQ)에 root node 삽입
•
PQ에서 bound가 가장 큰 노드를 remove
•
그 노드의 자식(아이템 포함/비포함) 노드들을 생성
•
각 자식의 bound 계산, bound가 현재 maxprofit보다 크면 PQ에 삽입
•
profit(이익) 값이 maxprofit보다 크면 maxprofit 갱신
void knapsack3(int n, const int p[], const int w[], int W, int& maxprofit){
priority_queue_of_node PQ;
node u, v;
initialize(PQ);
v.level = 0; v.profit = 0; v.weight = 0;
maxprofit = 0;
v.bound = bound(v);
insert(PQ, v);
while(!empty(PQ)){
remove(PQ, v); // bound가 가장 큰 노드
if(v.bound > maxprofit){
// 포함하는 경우
u.level = v.level + 1;
u.weight = v.weight + w[u.level];
u.profit = v.profit + p[u.level];
if(u.weight <= W && u.profit > maxprofit)
maxprofit = u.profit;
u.bound = bound(u);
if(u.bound > maxprofit)
insert(PQ, u);
// 포함하지 않는 경우
u.weight = v.weight;
u.profit = v.profit;
u.bound = bound(u);
if(u.bound > maxprofit)
insert(PQ, u);
}
}
}
C++
복사
•
bound 계산은 남은 용량에 대해 다음 아이템을 쪼개 넣을 수 있다고 가정해(무게당 가치로) 최대로 얻을 수 있는 이익의 상한선을 산출.
6. 분기한정법의 효율
•
백트래킹(DFS) 대비, 분기한정 BestFS가 더 적은 노드로 최적해에 도달 가능(탐색 노드 수 감소)
•
분기한정 BFS는 pruning을 하지만, 항상 최적 bound부터 확장하지는 않으므로 탐색 노드 수가 더 많을 수 있음
•
BestFS는 PQ에 bound가 높은 노드가 많아질수록(해공간이 크고 가지치기가 늦게 일어날수록) 실제 성능 차이가 커짐
7. 외판원 문제(Traveling Salesman Problem, TSP)와 분기한정법
•
n개 도시를 순회하여 모든 도시를 정확히 한 번씩 방문하고 출발점으로 돌아오는 최단 경로를 찾는 문제.
•
모든 경로의 개수는 (n–1)!로, 완전탐색은 매우 비효율적임.
•
분기한정법을 통해 유망하지 않은 부분공간을 가지치기(pruning).
•
상태공간트리에서 노드는 현재까지 방문한 도시 경로와, 남은 도시들에서 갈 수 있는 최저비용의 합(bound)을 저장.
Bound 계산 예시
•
이미 방문한 경로의 비용 + 남은 각 도시에서 방문 가능한 가장 짧은 간선의 비용(minimum) 합산
•
bound < 현재까지의 최단경로이면 PQ에 삽입(확장), 아니면 prune
8. Best-First Search로 푸는 TSP 알고리즘 구조
1.
PQ에 root node(경로 [1], bound=초기 하한) 삽입
2.
PQ에서 bound가 가장 작은 노드를 remove
3.
그 노드의 경로를 한 단계 더 확장(아직 방문하지 않은 도시를 추가)
4.
bound 계산, bound < minlength이면 PQ에 삽입
5.
경로가 완성되면 실제 경로 길이와 minlength를 비교, 더 짧으면 갱신
void travel(int n, const number W[][], ordered-set& opttour, number& minlength){
priority_queue_of_node PQ;
node u, v;
initialize(PQ);
v.level = 0; v.path=[1];
v.bound = bound(v, n, W);
minlength = ∞;
insert(PQ, v);
while(!empty(PQ)){
remove(PQ, v);
if(v.bound < minlength){
u.level = v.level + 1;
// u의 경로를 v.path에 아직 방문하지 않은 도시로 확장
for(all i such that 2≤i≤n && i not in v.path){
u.path = v.path; u.path.append(i);
if(u.level == n-2){
u.path.append(남은 유일한 도시); u.path.append(1);
if(length(u.path, W) < minlength){
minlength = length(u.path, W);
opttour = u.path;
}
}
else{
u.bound = bound(u, n, W);
if(u.bound < minlength)
insert(PQ, u);
}
}
}
}
}
C++
복사
•
bound 함수: 아직 경로에 없는 도시에서 나갈 수 있는 최소비용의 합을 더해 하한을 계산.
9. 결론
•
분기한정법은 해공간의 pruning과 탐색순서 최적화를 결합, 최적화 조합문제(0–1 배낭, TSP 등)에서 핵심적
•
Best-First Search는 우선순위 큐를 이용해 가장 유망한 노드(최고 bound)를 우선적으로 탐색
•
bound의 품질(타이트함)에 따라 pruning 효과와 성능이 달라진다
