분기 한정법 Branch and Bound

☁️ 분기 한정법

• 최적화 문제를 해결하기 위해 되추적 기법을 향상시킨 기법
  • 되추적 기버보가 마찬가지로 상태 공간 트리 사용
  • 상태 공간 트리를 순회하는 방법이 제한되어 있지 않음!
    • 되추적 기법은 항상 깊이 우선 탐색
  • 최적화 문제를 해결하기 위해서만! 사용

• 원리
  • 노드를 방문할 때마다 어떤 수 (한계치: bound)를 계산하여 노드의 유망성 여부 검사
    • 되추적: promising 여부
  • 이 한계치(bound)는 그 노드 이상을 검색하여 얻을 수 있는 한계를 나타냄
    • 실제 값이 아닌 최대 값 (계산을 통한 극한의 값)
  • 이 한계치를 통해 지금까지 찾은 최적의 해답보다 좋지 않으면 더 이상 그 노드의 후손들을 검색할 것인지의 여부 판단
• 상태 공간 트리 순회 -> 최악의 경우는 지수 시간 알고리즘
• 최적의 경우 보장 x. 최악의 경우를 피하는 것

☁️ 0-1 배낭채우기 문제

• 한계치를 계산하여 노드의 유망 여부를 검사할 수 있을 뿐 아니라,
• 유망 노드의 한계치를 비교하여 가장 유망한 노드를 찾아 이 노드부터 검사할 수 있음
• 이와 같은 알고리즘을 최고 우선 검색 분기한정 가지치기라고 함
  • 너비 우선 검색을 수정하여 구현

깊이 우선 탐색

• $w_i, p_i$를 각각 i번째 아이템의 무게와 가치라고 하면, $p_i / w_i$의 값이 큰 것부터 내림차순으로 아이템 정렬
• 다음 값들을 각 노드에 대해 계산
  • profit: 그 노드에 오기까지 넣었던 아이템의 가치의 합
  • weight: 그 노드에 오기까지 넣었던 아이템의 무게의 합
  • bound (최대 이익): 노드가 수준 i에 있다고 하고, 수준 k에 있는 노드에서 총 무게가 W를 넘는다고 하자. 그러면 다음과 같이 bound를 구할 수 있음
• maxprofit: 지금까지 찾은 최선의 해답이 주는 가치

• $totweight = weight + \sum_{j=i+1}^{k-1} w_j$
• $bound = (profit + \sum_{j=i+1}^{k-1} p_j) + (W - totweight) \times \frac{p_k}{w_k}$
  • 아이템 k-1까지의 이익 + 아이템 k를 부분적으로나마 넣을 수 있다고 했을 때의 이익
  • 각 노드에서 bound 값 계산 -> 더 내려갈지 결정

• 초기값 (루트 노드) : maxprofit := $0; profit := $0; weight := 0
• 깊이 우선 탐색으로 각 노드를 방문하여 다음 수행
  • 그 노드의 profit과 weight 계산
  • 그 노드이 bound 계산
  • weight < W && bound > maxprofit이면 검색 계속
    • 무게 초과 x, 향후 가치가 최대 가치보다 크다면
    • 그렇지 않다면 되추적
• 위의 과정을 모든 노드를 방문할 때까지 수행
  • 실제로는 가지치기가 이뤄지므로 모든 노드를 방문하지는 않음

• ex)

의사코드

• backtracking과 동일

void knapsack(index i, int profit, int weight) {
    if(weight <= W && profit > maxprofit) {     // maxprofit update
        maxprofit = profit;
        numbest = i;
        bestset = include;
    }

    if(promising(i)) {
        include[i+1] = 1;    // 다음 레벨 포함 -> profit, weight 추가
        knapsack(i+1, profit+p[i+1], weight+w[i+1]);
        include[i+1] = 0;    // 다음 레벨 포함x -> profit, weight 그대로
        knapsack(i+1, profit, weight);
    }
}

bool promising(index i) {    // bound 계산 과정
    index j, 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)   // w[j] > W -> 쪼개서 넣음
        bound = bound + (W-totweight)*p[k]/w[k];
    return bound > maxprofit;
}

너비 우선 탐색

• 루트 노드 먼저 검색
• 다음 수준 1에 있는 모든 노드 검색 (왼 -> 오)
• 그 다음 수준 2에 있는 모든 노드 검색 (왼 -> 오)
• …

알고리즘

• queue 활용

void BreadthFirstTreeSearch(tree T) {
    queue_of_node Q;
    node u, v;
    Q.initialize();
    v = root of T;
    visit v;   
    Q.enqueue(v);   // 루트 -> 큐 
    while(!empty(Q)) {    // 큐가 빌 때까지
        v = Q.dequeue();   // 루트 꺼냄
        for(each child u of v) {    // 루트의 자식 노드에 대해 실행 -> 레벨 별
            visit.u;
            Q.enqueue(u);
        }
    }
}

일반적인 너비우선 검색 분기 한정 알고리즘

number breadth_first_branch_and_bound(state_space_tree T) {
    Queue_of_node Q;
    number best;
    node u, v;
    Q.initialize();
    v = root of T;
    Q.enqueue(v);
    Best = vaule(v);      // 최적값
    while(!empty(Q)) {
        v = Q.dequeue();
        for(each child u of v) {
            if(value(u) is better than best) best = value(v);
            if(bound(u) is better than best) Q.enqueue(u);   // 더 확장할건지 -> 큐에 추가
        }
    }
    return best;
}

• maxprofit: 지금까지 찾은 가장 최적의 이익
• weight: 지금까지 배낭에 포함된 아이템들의 총 무게
• profit: 지금까지 배낭에 포함된 아이템들의 총 이익
• bound: profit의 상한값 (빈틈없이 배낭채우기 문제를 통해 계산)
  • k: weight가 W를 넘게 되는 레벨
  • k-1까지는 온전하게 weight, profit 계산
• 노드의 유망 여부
  • bound > profit

의사코드

struct node {
    int level;
    int profit;
    int weight;
    float bound;
};

void knapsack2(int n, const int p[], const int w[], int W, int& maxprofit) {
    queue_of_node Q;
    node u, v;
    initialize(Q);    // initialize Q to be empty
    v.level = 0; v.profit = 0; v.weight = 0;   // initialize v to be the root
    maxprofit = 0;
    enqueue(Q, v);
    while(!empty(Q)) {
        dequeue(Q);
        u.level = v.level + 1;    // set u to a child of v
        // 다음 item 포함
        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);

        // 다음 item 포함 X
        u.weight = v.weight;     // set u to the child that does not include the next item
        u.profit = v.profit;
        if(bound(u) > maxprofit)
            enqueue(Q, u);
    }
}

• bound = 되추적 기법에서의 promising

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;   // bound 값 자체 넘겨줌
    }
}

☁️ 최고우선 검색 분기한정 가지치기

• 노드의 모든 자식 노드를 검색한 후에 유망하면서 아직 확장하지 않은 노드들 중 가장 좋은 한계치를 가진 마디를 먼저 확장
  • 유망성이 가장 좋은 노드부터 확장
    • maxprofit이 더 빨리 크게 update됨 -> 더 많은 가지치기
• 일반 큐 대신 우선순위 큐 (max heap) 사용

일반적인 최고 우선 검색 분기한정 알고리즘

• 너비우선과 비슷하지만, 우선순위 큐 사용 & 꺼낸 노드의 bound 비교 후 확장 여부 결정

number best_first_branch_and_bound(state_space_tree T) {
    priority_queue_of_node PQ;
    number best;
    node u, v;
    PQ.initialize();
    v = root of T;
    PQ.enqueue(v);
    best = value(v);
    while(!PQ.empty()) {
        v = PQ.dequeue();
        if(bound(v) is better than best) {  // 꺼내서 bound 비교 후 자식노드 확장 결정
            for(each child u of v) {
                if(value(u) is better than best) best = value(u);
                if(bound(u) is better than best) PQ.enqueue(u);
            }
        }
    }
    return best;
}

• 너비우선 탐색: 꺼내고 바로 자식노드와 bound 비교
• 최고우선 탐색: 꺼낸 노드의 bound와 maxprofit 비교 후 자식노드 확장 여부 결정

의사코드

void knapsack3(int n, const int p[], const int w[], int W, int& maxprofit) {
    priority_queue_of_node PQ;
    node u, v;
    initialize(PQ);
    v.level = 0; v.profit = 0; v.weight = 0;
    maxprofit = 0; v.bound = bound(v);
    enqueue(PQ, v);
    while(!empty(PQ)) {
        v = dequeue(PQ);
        if(v.bound > maxprofit) {     // 너비 우선 검색에 없는 부분
            // 다음 item 포함
            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(PQ, u);
            // 다음 item 포함 X
            u.weight = v.weight;
            u.profit = v.profit;   // maxprofit update 될 일 없음
            if(bound(u) > maxprofit)
                enqueue(PQ, u);
        }
    }
}

• maxprofit update와 큐에 넣는 것은 다른 문제

☁️ 최적 일주 경로

• 외판원 문제
  • 출발 도시에서 각 도시를 한 번씩 방문하고 되돌아오는 가장 빠른 경로 찾기
• 가중치 방향 그래프로 표현
  • 가중치: 음이 아닌 정수
• 최적의 해밀토니안 순환경로를 찾는 문제와 같음 -> 최적의 일주여행 경로

• ex)

  • 모든 경로를 고려한 다음 최적의 일주 여행 경로를 찾는 시간 복잡도: $(n-1)!$

• n = 40일 때
  • 동적 계획법 알고리즘: $Θ(n^22^n)$ → 6년 이상
  • 무작정 알고리즘: $Θ(n!)$ → 3,800년
  • 분기한정법 시도

• 한계치
  • 노드의 한계치는 그 노드를 확장하여 얻을 수 있는 일주여행 경로 길이의 하한값으로 정의됨
  • 노드의 한계치가 지금까지 계산된 최적의 일주여행 경로 길이보다 크면 그 노드는 유망하지 않음

알고리즘

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];
    minlength = ∞;
    v.bound = bound(v);
    insert(PQ, v);
    while(!iempty(PQ)) {
        v = remove(PQ);
        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.bound = bound(u);
                    if(u.bound < minlength) insert (PQ, u);
                }
            }
    }
}

알고리즘 분석

• 방문하는 마디의 개수가 더 적음
• 그러나 아직도 알고리즘의 시간복잡도는 지수적이거나 그보다 못함
• 즉, n=40이 되면 문제를 풀 수 없는 것과 다름없다고 할 수 있음
  • -> Approximation Algorithms (근사 알고리즘)을 사용하여 최적해에 근접한 해답 찾음