(알고리즘) 6장. Branch-and-Bound (분기 한정법)

박지예·2023년 12월 13일

알고리즘

목록 보기

4/5

Branch-and-Bound(분기한정법)

특징
- Backtracking 기법과 같이 State Space Tree를 구축하여 문제를 해결한다.
- 최적의 해를 구하는 optimization problem에 적용할 수 있다.
- 최적의 해를 구하기 위해서 모든 해를 다 고려해 보아야 하므로 트리르 traverse하는 방법에 구애받지 않는다.
Branch-and-Bound 알고리즘의 원리
- 각 노드를 검색할 때마다, 그 노드가 promising한 지의 여부를 결정하기 위해서 한계값(bound)을 계산한다.
- 그 bound는 그 노드로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계를 나타낸다.
- 따라서 만약 그 bound가 지금까지 찾은 최적의 해답치보다 좋지 않은 경우는 더 이상 가지를 뻗어서 검색을 계속할 필요가 없으므로, 그 노드는 non-promising하다.

<복습> Optimization 문제를 풀기 위한 일반적인 Backtracking 알고리즘

void checknode (node v) {
	node u;
    if (value(v) is better than best)
    	best = value(v);
    if (promising(v))
    	for (each child u of v)
        	checknode(u);

문제 1) 0-1 Knapsack Problem

State Space Tree 구축

레벨 k에 있는 (현재) 노드에서 왼쪽가지로 가면 k번째 item을 배낭에 넣는 경우이고, 오른쪽 가지로 가면 그 item을 배낭에 넣지 않는 경우이다.
-> 루트에서 leaf까지의 모든 경로는 해답 후보이다.
최적의 해를 찾는 optimization problem이므로 검색이 완전히 끝나기 전에는 해답을 알 수가 없다. 따라서 검색 과정에서 항상 그 때까지 찾은 최적의 해를 기억해야 한다.

profit: 루트에서 현재노드까지 선택한 item들의 총 이윤
weight: 그 노드에 오기까지 넣었던 item의 총 무게
bound: profit의 최대이윤

현재 노드가 레벨 i에 있고, 레벨 k 노드에서 총 무게가 W를 넘는다고 하자. 그러면,

bound = (루트에서 노드 x까지의 cost) + (노드 x에서 해답노드까지의 가장 좋은 cost)

maxprofit: 지금까지 찾은 최선의 해답의 총 이윤값
maxprofit = 현재까지 찾은 최적의 해답 값

최소값 구하는 문제의 경우, maxprofit >= bound
최대값 구하는 문제의 경우, maxprofit <= bound

wi와 pi를 각각 i번째 item의 무게와 이윤이라고 하면, pi/wi의 값이 큰 것부터 내림차순으로 item을 정렬한다.
(일종의 탐욕적인 방법이 되는 셈이지만, 알고리즘 자체는 탐욕적인 알고리즘은 아니다.)

Branch and Bound 가지치기로 Best-First Search (최고우선검색)

최적의 해답에 더 빨리 도달하기 위한 전략
1. 주어진 노드의 모든 자식노드를 방문하여 다음을 수행한다.
1) 그 노드의 profit와 weight를 계산한다.
2) 그 노드의 bound를 계산한다.
2. promising 하면서 확장되지 않은 (unexpanded) 노드 살펴보고
promising: weight < W and bound > maxprofit
3. 그 중 가장 좋은(최고의) bound를 가진 노드를 확장함

Best-First Search가 너비우선검색에 비해 좋음

Branch-and-Bound 최고우선검색 알고리즘

void best_first_BranchBound (state_space_tree T, number best) {
	priority_queue_of_node PQ;
    node u,v;
    initialize(PQ);								//PQ를 빈 대기열로 초기화
    v = root of T;
    maxprofit = profit(v);
    insert(PQ, v);
    while(!empty(PQ)) {							//최고 bound를 가진 노드를 제거
    	remove(PQ,v);
        if (bound(v) > maxprofit)				// 노드의 promising 점검
        	for (each child u of v) {
            	if (profit(u) > maxprofit)
               		maxprofit = profit(u);		//profit이 현재까지의 max보다 높으면 갱신
                if (bound(u) > maxprofit)
                	insert(PQ,u);
            }
   	}
}

Branch-and-bound 알고리즘 풀이

풀이 참고) branch-and-bound : knapsack 문제 풀이

Knapsack Problem 알고리즘 분석
점검하는 노드의 수: O(2^n)

Dynamic programming 기법으로 설계한 알고리즘보다 좋은가? -> 확실하게 대답하기 불가능하지만, 일반적으로는 backtracking 알고리즘이 dynamic programming 알고리즘보다 더 빠르다.

문제 2) Traveling Salesman Problem (외판원 문제)

problem:
외판원의 고향 도시에서 출발하여 다른 도시들을 각각 한번씩만 방문하고, 다시 고향으로 돌아오는 일주여행경로(tour, Hamiltonian circuits) 중 가장 짧은 경로(optimal tour)를 구하는 문제
-> 음이 아닌 가중치 있는 방향성 그래프로 표현할 수 있다.

방법 1) 무작정 알고리즘

가능한 모든 일주여행경로를 다 고려한 후, 그 중에서 가장 짧은 일주여행경로를 선택한다.

방법 2) Branch-and-Bound 기법

State space tree 구축방법
각 노드: 출발노드로부터의 일주여행경로를 나타냄
최적일주여행경로를 구하기 위해서는 leaf 노드까지의 경로를 모두 검사하여 그 중에서 가장 길이가 짧은 경로를 찾음

Bound: 최소여행경로 길이의 한계값(lower bound)
A = V-([1,...,k] 경로에 속한 모든 노드의 집합)이라 두자

promising node: 최소여행경로를 minlength라고 두자.
Bound(v) < minlength인 노드를 유망한 노드라 한다.
최소여행경로의 초기값: (무한대)로 둔다.
완전한 여행경로를 처음 얻을 때 까지는 bound가 무조건 최소여행경로값보다 작으므로 모든 노드는 promising함