분기한정법 Branch-and-Bound

• 백트래킹과 같이 상태공간트리를 구축해서 해결
• 최적의 해를 구하는데 사용
• 어차피 다 확인해봐야해서 dfs 든 bfs든 상관없음(백트래킹은 dfs)

분기한정 알고리즘 원리

 

현재 있는 마디가 유망한지(promising)한지의 여부를 bound를 통해 결정한다.

bound는 그 가지의 해답값의 한계를 나타낸다.

 

간단한 그림으로 분기한정법의 예시를 나타낸다.

A와 B의 코스의 최소거리가 팻말에 나타나 있다.

이런 경우 당연히 A와 B는 고려하지 않는다(not-promising)

 

이런 경우에는 A를 먼저 탐색하는게 효율적이다. A에서의 최적의 해가 200이하면 B는 갈 필요 없기 때문

 

 

---

그렇다면 이 방법을 배낭채우기 문제에 적용해보자.

 

배낭에 채울 수 있는 최대 무게가 W 라고하자

n개의 아이템의 가격이 p 무게가 w라고 할 때 가격이 최대가 되는 방법을 찾아보자

 

분기한정법을 적용하기 위해서 가장 먼저해야할 일은 bound를 정의하는 것이다

여기서 쓰이는 bound는 최대 bound로 얻을수있는 최대값이 bound가 된다.

즉, 트리를 돌면서 현재 가치가 bound보다 크다면 그 마디는 더 이상 탐색할 필요가 없다.

 

현재 i번째 아이템까지 배낭에 담았고 k-1번째까지 담을 수 있다고 생각해보자. (k번째 아이템을 담는순간 무게가 초과된다).

bound 는 실제 지금까지의 무게 weight와 앞으로의 무게 (i+1,k-1) 그리고 k번째의 fractional한 무게를 담는다.

실제로는 아이템을 쪼개서 넣지 못하지만 이론적인 상황으로 계산한다. 

 

아래와 같이 p,w,W가 제시되어있는 상황이다.

 

여기서 (x,y)는 x번째의 아이템을 y(넣었을 경우 1 아니면 0) 한다는 뜻이다.

dfs 방식으로 최대 얻을 수 있는 값 maxprofit을 갱신하며 maxprofit < bound인 경우만 탐색한다.

따라서 (1,2) 인 경우 bound < maxprofit 이므로 탐색하지 않는다.

 

코드

import sys

def kp(i, profit, weight):
    global bestset
    global maxp
    
    #자신이 유효한지 그리고 그전 단계보다 profit이 큰지 확인.
    if( weight <= W and profit >maxp):
        maxp = profit
        bestset = include[:]
    if promising(i,weight,profit):
        include[i+1] = "yes"
        kp(i+1,profit+p[i+1],weight+w[i+1])
        include[i+1] = "no"
        kp(i+1,profit,weight)

   
def promising(i,weight,profit):
    global maxp
 
    if weight >= W :
        return False

    else:
        j = i+1
        bound = profit
        totweight = weight


        ##최대로 담았을때
        while j< n and (totweight + w[j]) <= W:
            totweight = totweight + w[j]
            bound = bound + p[j]
            j += 1

        k = j
        if k<n:
            bound = bound + (W-totweight) * p[k]/w[k]
        ##

        if bound > maxp:
            return True
        else:
            return False
        
    

n=4
W=16
p=[40,30,50,10]
w=[2,5,10,5]
maxp=0
include =[0,0,0,0]
bestset = [0,0,0,0]
kp(-1,0,0)
print(maxp)
print(bestset)