분기 한정 알고리즘 (Branch and Bound)

분기 한정 알고리즘(Branch and Bound)은 조합 최적화 문제를 해결하기 위한 일반적인 방법론으로, 많은 경우의 수를 탐색하여 최적의 해를 찾는 데 사용됩니다. 주로 NP-완전 문제에 사용되며, 대표적인 예로는 외판원 문제(TSP, Traveling Salesman Problem), 배낭 문제(Knapsack Problem) 등이 있습니다. 분기 한정 알고리즘은 상태 공간 트리를 이용하여 탐색을 수행하며, 최적 해를 구할 때 불필요한 경로를 가지치기(pruning)하여 효율성을 높입니다.

이 글에서는 분기 한정 알고리즘의 기본 개념과 동작 원리를 설명하고, 자바와 C 언어를 사용하여 예제 코드를 제공합니다.

분기 한정 알고리즘의 기본 개념

분기 한정 알고리즘은 문제를 작은 하위 문제로 나누어 해결하는 방식으로, 상태 공간 트리(State Space Tree)를 사용하여 문제의 해를 찾습니다. 분기(branch)는 문제를 하위 문제로 나누는 과정이며, 한정(bound)은 가지치기를 통해 불필요한 하위 문제를 제거하는 과정을 의미합니다.

분기 한정 알고리즘의 주요 아이디어는 다음과 같습니다.

1. 상태 공간 트리 생성: 문제를 해결하기 위해 가능한 모든 해를 표현하는 트리를 생성합니다.
2. 분기: 트리의 각 노드에서 가능한 모든 선택을 나누어 하위 노드를 생성합니다.
3. 한정: 각 노드에서 하위 노드로 탐색을 계속할지 여부를 결정하기 위해 경계(bound)를 설정합니다. 만약 현재 노드가 최적 해를 제공할 가능성이 없으면 가지치기하여 탐색을 종료합니다.

이 과정을 반복하여 가능한 해 중 최적의 해를 찾습니다. 분기 한정 알고리즘은 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS)과 같이 다양한 탐색 전략을 사용할 수 있습니다.

예제: 배낭 문제 (Knapsack Problem)

배낭 문제는 대표적인 NP-완전 문제로, 제한된 무게의 배낭에 최대 가치를 가지는 물건을 넣는 문제입니다. 이 문제를 분기 한정 알고리즘으로 해결하는 과정을 자바와 C 언어로 구현해보겠습니다.

자바(Java)로 구현한 배낭 문제

import java.util.Arrays;

class Knapsack {
    static class Item {
        int weight, value;
        Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

    static int bound(int level, int weight, int value, Item[] items, int capacity) {
        if (weight >= capacity) return 0;
        int bound = value;
        int totalWeight = weight;
        for (int i = level; i < items.length; i++) {
            if (totalWeight + items[i].weight <= capacity) {
                totalWeight += items[i].weight;
                bound += items[i].value;
            } else {
                bound += (capacity - totalWeight) * items[i].value / items[i].weight;
                break;
            }
        }
        return bound;
    }

    static int knapsack(Item[] items, int capacity) {
        Arrays.sort(items, (a, b) -> b.value / b.weight - a.value / a.weight);
        return knapsackRecursive(items, 0, 0, 0, capacity);
    }

    static int knapsackRecursive(Item[] items, int level, int weight, int value, int capacity) {
        if (level == items.length) return value;
        if (weight + items[level].weight <= capacity) {
            int include = knapsackRecursive(items, level + 1, weight + items[level].weight, value + items[level].value, capacity);
            int exclude = knapsackRecursive(items, level + 1, weight, value, capacity);
            return Math.max(include, exclude);
        }
        return value;
    }

    public static void main(String[] args) {
        Item[] items = { new Item(2, 40), new Item(3, 50), new Item(5, 100) };
        int capacity = 8;
        System.out.println("Maximum value: " + knapsack(items, capacity));
    }
}

위의 코드에서는 분기 한정 알고리즘을 사용하여 배낭 문제를 해결합니다. 각 노드에서 가능한 선택(물건을 넣거나 넣지 않는 것)을 통해 상태 공간 트리를 탐색하며, 최적의 해를 찾습니다.

C 언어로 구현한 배낭 문제

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int weight;
    int value;
} Item;

int bound(int level, int weight, int value, Item items[], int n, int capacity) {
    if (weight >= capacity) return 0;
    int bound = value;
    int totalWeight = weight;
    for (int i = level; i < n; i++) {
        if (totalWeight + items[i].weight <= capacity) {
            totalWeight += items[i].weight;
            bound += items[i].value;
        } else {
            bound += (capacity - totalWeight) * items[i].value / items[i].weight;
            break;
        }
    }
    return bound;
}

int knapsackRecursive(Item items[], int n, int level, int weight, int value, int capacity) {
    if (level == n) return value;
    if (weight + items[level].weight <= capacity) {
        int include = knapsackRecursive(items, n, level + 1, weight + items[level].weight, value + items[level].value, capacity);
        int exclude = knapsackRecursive(items, n, level + 1, weight, value, capacity);
        return include > exclude ? include : exclude;
    }
    return value;
}

int knapsack(Item items[], int n, int capacity) {
    return knapsackRecursive(items, n, 0, 0, 0, capacity);
}

int main() {
    Item items[] = { {2, 40}, {3, 50}, {5, 100} };
    int capacity = 8;
    int n = sizeof(items) / sizeof(items[0]);
    printf("Maximum value: %d\n", knapsack(items, n, capacity));
    return 0;
}

C 언어 코드에서도 마찬가지로 분기 한정 알고리즘을 사용하여 배낭 문제를 해결합니다. 재귀적으로 각 노드에서 선택을 하며 최적의 해를 구합니다.

분기 한정 알고리즘의 장점과 단점

장점

• 최적해 보장: 분기 한정 알고리즘은 모든 가능한 해를 탐색하기 때문에 최적해를 보장합니다.
• 효율적인 탐색: 가지치기(pruning)를 통해 불필요한 경로를 제거하여 탐색 시간을 줄일 수 있습니다.

단점

• 높은 시간 복잡도: 최악의 경우 모든 노드를 탐색해야 하므로 시간 복잡도가 매우 높을 수 있습니다.
• 메모리 사용량: 상태 공간 트리를 저장하기 위한 메모리 사용량이 클 수 있습니다.

결론

분기 한정 알고리즘은 조합 최적화 문제를 해결하기 위한 강력한 방법입니다. 최적해를 보장하면서도 가지치기를 통해 탐색 효율성을 높일 수 있지만, 문제의 크기가 커지면 계산량이 기하급수적으로 증가할 수 있다는 단점이 있습니다. 따라서 실제 문제를 해결할 때는 문제의 특성과 크기에 따라 적절한 탐색 전략을 선택하는 것이 중요합니다.

위의 자바와 C 언어 예제를 통해 분기 한정 알고리즘이 어떻게 동작하는지 이해할 수 있었기를 바랍니다. 배낭 문제 외에도 다양한 최적화 문제에 분기 한정 알고리즘을 적용하여 최적해를 찾을 수 있습니다.