[알고리즘] 6장. Branch and Bound

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 6-1

* Backtracking은 상태공간을 이동, Branch-and-Bound는 bound함수를 통해 가장 좋은 해를 찾음

* 최소화 문제
- 최소 거리의 트래킹코스를 찾는다.

* 최대화 문제
- 최대 가치의 보물을 찾는다.

* 분기한정법 특징
- 되추적 기법과 같이 상태공간트리를 구축해서 문제를 해결한다.
- 최적의 해를 구하는 문제(optimization problem)에 적용할 수 있다.
- 최적의 해를 구하기 위해서는 모든 해를 다 고려해 봐야하므로 트리의 마디를 순회(traverse)하는 방법에 구애 받지 않는다.

* 분기한정법 원리
1. 각 마디를 검색할 때 마다, 그 마디가 유망(promising)한지의 여부를 결정하기 위해서 한계값(bound)을 계산한다.
2. 그 한계치는 그 마디로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답값의 한계를 나타낸다.
3. 따라서 만약 그 한계값이 지금까지 찾은 최적의 해답값보다 좋지 않은 경우는 더 이상 가지를 뻗어서 검색을 계속할 필요가 없으므로 그 마디는 유망하지 않다(nonpromising)고 할 수 있다.

---

📌 6-2

* 0-1 Knapsack Problem (되추적)
- 이 문제는 최적의 해를 찾는 문제(optimization problem)이므로 검색이 완전히 끝나기 전에는 해답을 알 수가 없다. 따라서 검색을 하는 과정 동안 항상 그 때까지 찾은 최적의 해를 기억해 두어야 한다.

* <A> 최적화 문제를 풀기 위한 일반적인 되추적 알고리즘

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);
}

* <A> 0-1 Knapsack Problem (분기한정법)
- 아이템은 무게당 가치가 감소하는 순서로 정렬을 가정한다.
profit : 그 마디에 오기까지 넣었던 아이템의 값어치의 합.
weight : 그마디에 오기까지 넣었던 아이템의 무게의 합.
bound : 마디가 수준 i에 있다고 하고, 수준 k에 있는 마디에서 총무게가 W를 넘는다고 하자. 그러면
bound = (profit + sigma(p)) + (W - totweight) x pk/wk
maxprofit : 지금까지 찾은 최선의 해답이 주는 값어치
bound <= maxprofit이면 수준 i에 있는 마디는 유망하지 않다.
- 수행 절차 : 깊이우선순위로 각 마디를 방문하여 다음을 수행한다.
1. 그 마디의 profit과 weight을 계산한다.
2. 그 마디의 bound를 계산한다.
3. weight < W and bound > maxprofit이면, 검색을 계속한다. 그렇지 않으면, 되추적.

- 입력 : n 개의 아이템, 양의 정수 W. 배열 w와 p, 인덱스는 1부터 n.
		각 배열은 p[i]/w[i] 값의 내림차순으로 정렬.
- 출력 : 배열 bestset, 1부터 n. bestset[i]의 값은 i번째 아이템이 최적의 해에 포함되어 있으면 Y, 아니면 N.
- 마디의 수 : 2^(n+1) - 1 => Θ(n^2)

void knapsack(index i, int profit, int weight) {
	if (weight <= W && profit > maxprofit) {
		maxprofit = profit;
		numbest = i;
		bestset = include;
	}
	if (promising(i)) {
		include[i + 1] = "yes";
		knapsack(i + 1, profit + p[i + 1], weight + w[i + 1]);
		include[i + 1] = "no";
		knapsack(i + 1, profit, weight);
	}
}

bool promising(index i) {
	index i, k;
	int totweight;
	float bound;
	if (weight >= W)
		return false;
	else {
		j = i + 1;
		bound = profit;
		totweight = weight;
		while (j <= n && totweight + w[j] <= W) {
			totweight = totweight + w[j];
			bound = bound + p[j];
			j++;
		}
		k = j;
		if (k <= n) bound = bound + (W-totweight) * p[k]/w[k];
		return bound > maxprofit;
	}
}

---

📌 6-3

* <A> 일반적인 너비우선검색 알고리즘

void breadth_first_search(tree T) {
	queue_of_node Q;
	node u, v;
	initialize(Q);
	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);
		}
	}
}

* <A> 분기한정 가지치기로 너비우선검색(breadth-first search)
- 순서
1. 뿌리마디를 먼저 검색한다.
2. 다음에 수준 1에 있는 모든 마디를 검색한다. (왼->오)
3. 다음에 수준 2에 있는 모든 마디를 검색한다. (왼->오)
4. ...

void breadth_first_branch_and_bound(state_space_tree T, number& best) {
	queue_of_node Q;
	node u, v;
	initialize(Q);			// Q는 빈 대기열로 초기화
	v = root of T;			// 뿌리마디를 방문
	enqueue(Q, v);
	best = value(v);
	while(!empty(Q)) {
		dequeue(Q, v);
		for(each child u of v) { // 각 자식마디를 방문
			if(value(u) is better than best)
				best = value(u);
			if(bound(u) is better than best)
				enqueue(Q, u);
		}
	}
}

* <A> 0-1 Knapsack Problem (분기한정법 너비우선검색)

void knapsack(int n, const int p[], const 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.weight = v.weight + w[u.level];
		u.profit = v.profit + p[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);
	}
}

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;
	}
}

* <A> 분기한정 가지치기로 최고우선검색(best-first search)
- 전략
1. 주어진 마디의 모든 자식마디를 검색한 후
2. 유망하면서 확장되지 않은(unexpanded) 마디를 살펴보고
3. 그 중에서 가장 좋은(최고의) 한계치(bound)를 가진 마디를 확장한다.
- 너비우선검색보다 좋다.
- 최고의 한계를 가진 마디를 우선적으로 선택하기 위해서 우선순위 대기열 (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);
	v = root of T;
	best = value(v);
	insert(PQ, v);
	while(!empty(PQ) {
		remove(PQ, v);
		if(bound(v) is better than best)
			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);
			}
	}
}

* <A> 0-1 Knapsack Problem (분기한정법 최고우선검색)

void knapsack(int n, const int p[], const int w[], int W, int& maxprofit) {
	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);
		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);
		}
	}
}

float bound(node u) {
	same as before
}

---

📌 6-4

* 외판원 문제 (Traveling Salesman(person) Problem)
- 하나의 노드에서 출발해서 다른 노드들을 각각 한 번씩만 방문하고 다시 출발 노드로 돌아오는 가장 짧은 일주여행경로(tour)를 결정하는 문제
- 동적계획법을 사용하면 Θ(n^2 * 2^n), 아주 오래걸린다.
- 해밀토니안 회로 : 연결된 비방향성 그래프에서, 해밀토니안 회로(Hamiltonian circuits, cycle)/ 일주여행경로(tour)는 어떤 한 마디에서 출발해서 그래프 상의 각 정점을 한 번씩만 경유해서 다시 출발한 정점으로 돌아오는 경로다.
- 한계값(bound) 구하기

* <A> 외판원 문제 알고리즘 (분기한정법 최고우선검색)

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);
	minlength = infinite;
	insert(PQ, v);
	while (!empty(PQ)) {
		remove(PQ, v);
		if (v.bound < minlength) {
			u.level = v.level + 1;
			for (all i such that 2<=i<=n && i is not in v.path) {
				u.path = v.path;
				put i at the end of u.path;
				if (u.level == n-2) {
					put index of only vertex not in u.path at the end of u.path;
					put 1 at the end of u.path;
					if (length(u) <= minlength) {
						minlength = length(u);
						opttour = u.path;
					}
				}
				else {
					u.bounc = bound(u);
					if (u.bound < minlength)
						insert(PQ, u);
				}
			}
		}
	}
}

---