[알고리즘] 8. Branch and Bound

이전 내용

[알고리즘] 7. Backtracking

 

 

1. Brute force
2. Divide and conquer
3. Decrease and conquer
4. Transform and conquer
5. Greedy Method
6. Dynamic Programming
7. Backtracking
8. Branch and Bound

여기서는 Branch and bound에 대해 다룬다.

---

Branch and Bound이란?

• 백트래킹과 유사하게 조건에 따라 최적의 경우의 수를 파악해 나간다.
• 백트래킹은 최적치 없이 조건만 있지만 branch and bound는 보통 최적치를 가장 좋게하는 숫자 처리 과정에서 쓰인다.
• 이론상 최적 기댓값을 만들고, 매번 그 값에 가장 가까운 쪽부터 뻗어나간다. 그래서 최적치 계산을 매번 해야하고, greedy와 비슷한 느낌이 든다.
• 하지만,  이미 최적값 하나가 끝까지 가서 나왔는데, 그 값보다 이론상 최적치가 안좋은 쪽의 경로는 차단된다. 즉 이런 부분을 통해 backtracking이나 greedy보다는 탐색과정을 줄일 수 있다.
• 처음의 최적 분기와 실제 최적 분기가 다를 경우 시간이 많이 증가할 수 있다.(처음 선택하는게 많이 안좋은 값인데 그래야만 최적값이 나오는 경우)

---

Branch and Bound 예시

1. 0/1 배낭 문제
2. Job assignment problem
3. Traveling salesman problem

---

0/1 배낭 문제

• 배낭문제는 일반적으로 DP로 푸는게 정설이지만 Branch and bound로도 풀 수는 있다.
• 무게대비 value 값으로 최적값을 만들고, 각 그래프는 넣을지 안넣을지를 기준으로 뻗어나간다.
• 그렇게 하여 가장 최적치가 좋은 branch 위주로 선택한다.
• DP로 푸는게 더 효율적이긴 하다..

---

Job assignment problem

• Job assignment problem 역시 마찬가지로 bruteforce보다는 효율적인 branch and bound로 풀 수 있다.
• 이때 직업을 기준으로 하는지, 사람을 기준으로 하는지에따라 전개 과정이 달라진다. 하지만 당연히 최종 답은 같게 나온다.

 

---

Traveling salesman problem

import numpy as np
import heapq

big = np.inf

class Node:
    def __init__(self, level, path, cost, reduced_matrix):
        self.level = level
        self.path = path
        self.cost = cost
        self.reduced_matrix = reduced_matrix

    def __lt__(self, other):
        return self.cost < other.cost

def reduce_matrix(matrix):
    n = len(matrix)
    row_reduction = np.min(matrix, axis=1)
    row_reduction[row_reduction == big] = 0
    matrix -= row_reduction[:, np.newaxis]

    col_reduction = np.min(matrix, axis=0)
    col_reduction[col_reduction == big] = 0
    matrix -= col_reduction

    total_reduction = np.sum(row_reduction) + np.sum(col_reduction)
    return matrix, total_reduction

def branch_and_bound_tsp(cost_matrix):
    n = len(cost_matrix)
    initial_matrix, initial_cost = reduce_matrix(cost_matrix.copy())

    root = Node(0, [0], initial_cost, initial_matrix)
    priority_queue = []
    heapq.heappush(priority_queue, root)

    min_cost = big
    best_path = None

    while priority_queue:
        current_node = heapq.heappop(priority_queue)

        if current_node.level == n - 1:
            current_path = current_node.path + [0]
            current_cost = current_node.cost + cost_matrix[current_node.path[-1]][0]
            if current_cost < min_cost:
                min_cost = current_cost
                best_path = current_path
            continue

        current_city = current_node.path[-1]
        for next_city in range(n):
            if next_city not in current_node.path:
                new_matrix = current_node.reduced_matrix.copy()
                new_matrix[current_city, :] = big
                new_matrix[:, next_city] = big
                new_matrix[next_city, 0] = big

                reduced_matrix, reduction_cost = reduce_matrix(new_matrix)
                new_cost = current_node.cost + cost_matrix[current_city][next_city] + reduction_cost

                if new_cost < min_cost:
                    new_path = current_node.path + [next_city]
                    new_node = Node(current_node.level + 1, new_path, new_cost, reduced_matrix)
                    heapq.heappush(priority_queue, new_node)

    return best_path, min_cost

cost_matrix = np.array([
    [0, 14, 4, 10, 20],
    [14, 0, 7, 8, 7],
    [4, 5, 0, 7, 16],
    [11, 7, 9, 0, 2],
    [18, 7, 17, 4, 0]
], dtype=float)

path, cost = branch_and_bound_tsp(cost_matrix)
print(f"Optimal Path: {path}")
print(f"Optimal Cost: {cost}")

 

• 파이썬의 힙을 이용하여 TSP 문제도 branch and bound로 풀 수 있다.

 

---

결론

branch and bound 알고리즘이었다.