알고리즘: 분기한정법(Branch-and-bound)을 이용한 0-1 배낭채우기문제 (0-1 knapsack problem) 공부하기!

 

이번 포스팅은 분기한정법(branch-and-bound)을 이용한 0-1 배낭채우기 문제에 대해서 알아본다. 

 

이전의 포스팅에서는 동적계획법(Dynamic programming)과 되추적(Backtracking)을 이용한

0-1 배낭채우기에 대해서 알아봤었다. 

 

알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem)

 

알고리즘: 되추적(BackTracking)을 이용한 0 - 1 배낭채우기 문제(0- 1 knapsack problem) 공부하기

 

그렇다면 분기한정법이란 무엇일까?

 

분기한정법은 상태공간트리를 사용하여 문제를 푼다는 사실이 되추적과 매우 비슷한 설계방식이다.

다른 점이라고 한다면

 

1) 트리 횡단 방법에 구애받지 않고,

2) 최적화 문제를 푸는데만 쓰인다. 

 

 

 

분기한정법에서는 되추적에서 더 나아가

어떤 마디가 유망한지 결정하기 위해서 한계값(bound)를 계산하고 그 한계값이 여태까지 

찾은 최고 해답 값보다 더 좋으면 유망하다(promising)고 한다. 

 

분기한정 알고리즘은 되추적 알고리즘의 경우와 마찬가지로 최악의 경우 보통 지수시간이지만

실제 사례에서 매우 효율적인 경우가 많이 검증되었다.

 

 

 

이전의 다루었던 되추적알고리즘을 이용한 0-1 배낭채우기문제는 사실 분기한정 알고리즘이다.

 

하지만 되추적 알고리즘은 분기한정을 사용하여 얻을 수 있는 장점을 제대로 살리지 못한다.

 

그래서 이제부터는 마디가 유망한지 결정하기 위해 한계값을 사용하는 것 이외에도

유망한 마디값들의 한계값을 비교하여 그 중에서 가장 좋은 한계값을 가진 마디의 자식마디를 방문할 것이다.

 

이 방법을 분기한정 가지치기 최고우선검색(best-fist serach with branch-and-bound prunning)이라고 한다.

 

이 방법은 너비우선탐색(breadth-fist-search)를 이용해서 구현할 수 있다. 

 

 

 

 

우선 간단하게 너비우선탐색에 대해서 알아보자면 다음과 같다. 

 

 

위와 같은 순서로 검색하는 방법이 너비우선탐색(BFS)

 

void breadth_first_search(tree T) {
	queue_of_node Q;
	node u, v;
	initialize(Q); // Initialize Q to be empty	
	v = root of T; 
	visit v; 
	enqueue(Q,v);
	while(!empty(Q)) {
		dequeue(Q,v);
		for(each child u of v) {
		visit u; 
		enqueue(Q,u);
		}
	}
}

 

대기열(queue)를 사용해서 enqueue라는 프로시저로 대기열의 뒤에 아이템을 붙여 넣고

 

dequeue라는 프로시저로 앞에서 아이템을 제거한다. 

 

 

이제부터 0-1 배낭채우기 문제에 분기한정법을 어떻게 적용하는지 살펴보자 

 

다음과 같은 아이템 내역들이 있다고 가정하자.

 

 

 

분기한정 가지치기 너비우선검색은 깊이우선검색 대신 너비우선검색을 하는 것을 제외하고

되추적 방법과 똑같이 진행된다.

 

weight와 profit은 그 마디에 오기까지 포함되었던 아이템의 총 무게와 총 이익으로 한다.

 

마디가 유망한지 결정하기 위해서 totweight와 bound를 weight와 profit으로 각각 초기화하고,

그 다음 toweight가 W를 초과하게 하는 아이템에 도달할 때까지 탐욕적으로 아이템을 취하여 그 무게와 totweight와 bound에 각각 더한다.

 

배낭에 넣을 수 있는 만큼만 그 아이템의 일부분을 취하여 그 부분의 weight를 toweight에 더한다.

 

이런 식으로 bound는 그 마디에서 확장하여 얻을 수 있는 이익의 상한이 된다.

 

만약 그 수준i에 위치하고 있고, 수준 k에 위치한 마디는 무게의 합이 W가 넘어가는 마디라고 했을 때 

다음과 같은 식을 얻는다. 

 

 

 

아울러 weight >= W 이거나

지금까지 찾은 최고 해답에서의 값인 maxprofit보다 이 한계값이 작거나 같으면

그 마디는 유망하지 않다. 

 

 

위의 예제에 대해 이 방식을 적용하여 가지치기하면 다음과 같은 상태공간트리를 얻을 수 있다. 

 

 

여기서 (3, 1)과 (4, 3)은 한계값이 0인 경우가 되추적 알고리즘과 다르다. 

 

분기한정 알고리즘은 어떤 마디에서 확장 여부를 결정할 때 지금까지 구한 답 중에서 가장 좋은 값보다 한

계값이 더 좋은 지 검사한다.

 

따라서 이경우에는 가중치가 W보다 크거나 같기 때문에 마디가 유망하지 않게 되면서 한계값을 0으로 둔다. 

 

하지만 이렇게 너비우선검색으로 검색했을 때 검색 마디갯수는 17이다. 이는 되추적 알고리즘보다 좋지 않다. 

 

이는 깊이우선검색과는 달리 너비우선검색에서는 maxprofit의 값이 자식마디를 실제로 방문할 때 

변해버릴 수 있기 때문에 검색시간을 낭비하게 되는 것이다. 

 

 

 

 

 

void breadth_first_branch_and_bound(state_space_tree T, number& best){
	queue_of_node Q;
	node u, v;
	initialize(Q); // Initialize Q to be empty
	v = root of T; // Visit root
	enqueue(Q,v);
	best = value(v);
	while(!empty(Q)) {
		dequeue(Q,v);
		for(each child u of v) { // Visit each child
			if(value(u) is better than best)
				best = value(u);
			if(bound(u) is better than best)
				enqueue(Q,u);
		}
	}
}

 

 

이 알고리즘은 위에서 살펴봤던 너비우선탐색을 수정한 것이다.

 

이 알고리즘에서는 마디의 한계값이 당시 최고 해답의 값보다 좋은 경우에만 그 마디에서 계속 확장한다.

 

당시 최고 해답의 값(best)는 뿌리마디에서의 해답의 값으로 초기화하기 때문에 best를

어떤 해답보다도 나쁜 값으로 초기화하는 낭비를 한다. 

 

 

 

 

 

이제부터는 위 방식을 이용하여 0-1배낭채우기 문제를 푸는 알고리즘을 살펴본다. 

 

재귀를 사용하지 않기 때문에 다음과 같은 노드를 정의한다.

 

Struct node { 
	int level;
	int profit; 
	int weight; 
}

 

 

<아직은  부족한 knapsack problem algorithm1>

void knapsack2(int n, const int p[], cont int w[], int W, int &maxprofit) {
	queue_of_node Q; node u, v; 
	initialize(Q);
	v.level =0; v.profit = 0; v.weight = 0; maxprofit = 0;
	enqueue(Q, v); 
	while (!empty(Q)) {
		dequeue(Q, v); u.level = v.level+1;
		u.profit = v.profit + p[u.level];
		u.weight = v.weight + w[u.level];
		if ((u.weight <= W) && (u.profit > maxprofit)) maxprofit = u.profit;
		if (bound(u)>maxprofit) enqueue(Q, u);
		u.weight = v.weight;
		u.profit = v.profit;
		if (bound(u)>maxprofit) enqueue(Q, u);
	}
} // 문제점 : 경로 출력? include, bestset 출력

 

float bound(node u) {
	index j, k; int totweight; float result;
	if (u.weight >= W) 
		return 0;
	else {
		result = u.profit; j = u.level +1; totweight = u.weight;
		while ((j<=n) && (totweight + w[j] <= W)) {
			totweight = totweight + w[j]; 
			result = result + p[j];
			j++;
		} 
	k = j;
	if (k<= n) 
		result = result + (W - totweight)*p[k]/w[k];
	return result;
	} 
}

 

 

일반적으로 너비우선검색 전략은 깊이우선검색보다 좋은 점이 없다.

 

그러나 마디의 유망성 여부를 결정하는 것 이외에 추가적인 용도로 한계값을 사용하면 검색을 향상시킬 수 있다.

 

주어진 어떤 마디의 모든 자식마디를 방문한 후 유망하면서 확장하지 않은 모든 마디의 모두

살펴보고 그 중에서 한계값이 가장 좋은 마디를 우선적으로 확장한다.

 

지금까지 찾은 최고의 해답보다 그 한계값이 좋다면 그 마디는 유망하다.

 

미리 정해 놓은 순서대로 무작정 검색을 진행하는 것보다 이런식으로 하면 최적해를 더 빨리 찾게 된다. 

 

이렇게 최고우선검색(Best-First-Search)를 하면 일반적으로 너비 우선검색에 비해서 좋아진다.

 

 

 

 

 

그렇다면 이제부터 최고우선검색을 이용한 우리한 필요한 knapsack problem알고리즘을 알아보겠다. 

 

 

검색 절차는 다음과 같다. (볼드체로 표시된 부분을 주의깊게 보자 )

 

 

 

1. 마디(0, 0)을 방문한다.

 

a) 이익과 무게를 0으로 둔다. 

b) 한계값을 계산하면 115가 된다.

c) maxprofit은 0이 된다. 

 

 

 

2. 마디 (1, 1)을 방문한다.

 

a) 이익과 무게를 계산하면, 각각 40과 2가 된다. 

b) maxprofit은 40이 된다.

c) 한계값을 계산하면 115가 된다.

 

 

 

3. 마디(1, 2)을 방문한다.

 

a) 이익과 무게를 0으로 둔다. 

b) 한계값을 계산하면 82가 된다.

c) maxprofit은 0이 된다. 

 

 

 

4. 아직 확장되지 않은 마디 중에서 가장 큰 한계값을 가진 유망한 마디를 구한다.

 

a) 마디(1, 1)은 한계값이 115이고, 마디(1, 2)는 82이므로 마디(1,1)이 한계값이 

가장 크면서 유망하고, 확장하지 않은 마디이다. 그 마디의 자식마디를 다음에 방문한다.

 

 

 

5. 마디 (2, 1)을 방문한다.

 

a) 이익과 무게를 계산하면, 각각 70과 7이 된다. 

b) maxprofit은 70이 된다.

c) 한계값을 계산하면 115가 된다.

 

 

 

6. 마디(2, 2)을 방문한다.

 

a) 이익과 무게가 40, 2가 된다. 

b) 한계값을 계산하면 98이 된다.

 

 

 

7. 아직 확장하지 않은 마디 중에서 가장 큰 한계값을 가진 유망한 마디를 구한다.

 

a) (2, 1)이 가장 유망므로 그 마디의 자식마디를 다음에 방문한다. 

 

 

 

8. 마디 (3,1)을 방문한다.

 

a) 이익과 무게를 계산하면 120, 17이 된다.

b) weight가 w보다 크므로 이 마디는 유망하지 않다. 한계값을 0으로 둔다.

 

 

 

9. 마디 (3, 2)을 방문한다.

 

a) 이익과 무게를 계산하면 70, 70 이 된다.

b) 한계값을 계산하면 80이 된다.

 

 

 

10. 아직 확장하지 않은 마디 중에서 가장 큰 한계값을 가진 유망한 마디를 구한다.

 

a) (2, 2)가 가장 한계 값이 크므로 유망하다. 다음에 그 마디의 자식마디를 방문한다.

 

 

 

11. 마디 (3,3)을 방문한다. 

 

a) 이익과 무게를 계산하면 90과 12가 된다.

b) 12 < W이므로 maxprofit이 90으로 갱신하고 한계값 82, 80 보다 크므로 (3, 1)과 (3,2)는 유망하지 않게 된다. 

c) 한계값을 계산하면 98이 된다. 

 

 

 

 

위와 같은 방식으로 검색하다가 유망하고 확장하는 마디가 없으면 작업이 완료된다.

 

최고우선검색으로 11개의 마디만 검색했는데, 일반 너비우선검색보다 검색한 마디의 수가

6개 적고, 깊이우선검색보다 2개 적다. 

 

최고우선검색은 너비우선검색을 조금 변형시켜서 구현하면 된다.

 

queue 대신 우선순위 대기열(priority queue)를 사용한다.

 

우선순위 대기열은 우선순위가 높은 구성요소를 항상 먼저 제거한다.

 

우선순위 대기열은 heap을 이용해서 구현할 수 있다.

 

 

void best_first_branch_and_bound (state_space_tree T,number best) {
	priority_queue_of_node PQ;
	node u,v;
	initialize(PQ); // initialize PQ to empty
	v = root of T;
	best = value(v);
	insert(PQ,v);
	while(!empty(PQ)) { // Remove node with best bound
		remove(PQ,v);
		if(bound(v) is better than best) // Check if node is still promising
			for(each child u of v) {
				if(value(u) is better than best)
					best = value(u);
				if(bound(u) is better than best)
					insert(PQ,u);
			}
	}
}

 

 

 

 

< 최고우선검색 알고리즘을 이용한 0-1 knapsack problem> 

void knapsack3(int n, const int p[], cont int w[], int W, int &maxprofit){
	queue_of_node PQ; node u, v;
	initialize(PQ);
	v.level =0; v.profit = 0; v.weight = 0; v.bound = bound(v);
	maxprofit = 0;
	insert (PQ, v);

	while (!empty(Q)) {
		remove(PQ, v);
		if(v.bound > maxprofit) {
			u.level = v.level+1;
			u.profit = v.profit + p[u.level];
			u.weight = v.weight + w[u.level];
		if ((u.weight <= W) && (u.profit > maxprofit)) 
			maxprofit = u.profit;
		u.bound = bound(u);
		if (bound(u) > maxprofit) insert (PQ, u);
		u.weight = v.weight; // Set u to the child 
		u.profit = v.profit; // that does not include
		u.bound = bound(u); // the next item.
		if (u.bound > maxprofit) insert (PQ, u);
		} 
	}
}

(bound는 이전에 사용했던 것을 이용)

 

 

 

출처 : Foundations of Algorithms, Using C++ Pseudocode