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

Branch and Bound(분기 한정법)

최적화 문제를 해결하는 알고리즘 기법이다. 주어진 문제의 해를 찾는 대신, 가능한 해의 공간을 분기하고, 각 분기에서 더 이상 최적해가 될 수 없는 경우에는 해당 분기를 탐색하지 않고 가지치기(한정)하는 방식을 사용한다.
Branch and Bound는 일반적으로 다음과 같은 단계로 수행된다.

• 1. 초기화
     최적해를 저장하는 변수를 초기화하고, 문제 공간의 초기 상태를 설정한다.
• 2. 분기
     문제 공간에서 가능한 해의 후보를 생성하는 분기 작업을 수행한다. 이는 변수의 값을 변경하거나 다른 결정 변수를 선택하여 가능한 해의 공간을 분할하는 것을 의미한다. 이로써 여러 하위 문제가 생성된다.
• 3. 한정
     각 분기에서는 해당 분기의 해의 가능성을 평가하는 한정 조건을 적용한다. 이는 최적화 문제에서 목적 함수의 상한선(upper bound)이나 하한선(lower bound)을 계산하거나, 해당 분기의 해의 특성을 이용하여 가능한 해의 공간을 축소시키는 것을 의미한다.
• 4. 가지치기
     한정 조건에 따라 탐색해야 할 필요가 없는 분기를 가지치기 하여 탐색 공간을 축소한다. 가지치기를 통해 현재까지 찾은 최적해보다 좋지 않은 해를 가진 분기는 더 이상 탐색하지 않게 된다.
• 5. 반복
     분기 및 한정 과정을 반복하여 최적해를 찾을 때까지 탐색을 진행한다.

Branch and Bound는 여러 최적화 문제에 적용될 수 있으며, 여행자 문제, 배안 문제, 그래프 색칠 문제 등 다양한 분야에서 활용된다.

Knapsack Problem(0-1 배낭채우기 문제)

주어진 가방의 용량 한계 내에서 가치가 최대가 되는 물건의 조합을 찾는 최적화 문제이다. Branch and Bound 알고리즘은 이러한 배낭 문제를 해결하는 데에 사용될 수 있다. 배낭 문제에서는 일정한 가방 용량과 각 물건의 가치와 무게가 주어진다. 가방에 담을 수 있는 최대 가치를 구하기 위해서는 어떤 물건을 선택해야 할지 결정해야 한다.

분기한정 가지치기로 깊이우선검색하는 방법

• profit: 그 마디에 오기까지 넣었던 아이템의 값어치의 합
• weight: 그 마디에 오기까지 넣었던 아이템의 무게의 합
• bound: 이론적으로 현 상태에서 얻을 수 있는 최대 이익
• maxprofit: 지금까지 찾은 최선의 해답이 주는 값어치
• bound <= maxprofit이면 수준 i에 있는 마디는 유망하지 않다.

아이템은 무게당 가치가 감소하는 순서로 정렬한다고 가정한다. n개의 아이템이 주어지고, 최대무게는 W이다. 배열 w에는 각 아이템의 무게가 저장되어 있고, 인덱스는 1부터 n이다. 각 배열은 p[i]/w[i] 값의 내림차순으로 정렬한다.

깊이우선 순위로 각 마디를 방문하여 다음을 수행한다:

• 1. 그 마디의 profit과 weight를 계산한다.
• 2. 그 마디의 bound를 계산한다.
• 3. weight maxprofit이면, 검색을 계속하고, 그렇지 않으면 되추적한다.

의사코드

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 j,k;
  	int totweight;
  	float bound;
  
  	if(weight>=W) 
  		return false;
  	else {
  		j = j+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;