사전 분기 한정
알고리즘

분기 한정

gabury1고친 사람 github-actions[bot]

분기 한정은 가장 좋은 답을 찾을 때 이길 가망이 없는 후보를 한꺼번에 건너뛰는 탐색 방법입니다. 후보를 여러 묶음으로 나누고 묶음마다 그 안에서 나올 수 있는 가장 좋은 값을 어림합니다. 어림한 값이 지금까지 찾은 답보다 못하면 그 묶음은 열어 보지 않습니다. 모든 후보를 따지는 것과 같은 답을 내면서 따지는 양을 줄입니다.

쉽고 빠른 이해

분기 한정은 이길 수 없는 후보 묶음을 열어 보지 않고 버립니다. 최저가를 찾다가 이미 3만 원짜리를 봤다고 해 봅시다. 가장 싼 물건도 4만 원인 가게는 들어가 볼 필요가 없습니다.

답은 「이 물건을 넣나 빼나」 같은 결정 여럿으로 정해집니다. 후보를 하나하나 다 따지면 결정이 하나 늘 때마다 후보 수가 두 배가 됩니다. 묶음째 버리면 그 안의 후보 수백, 수천 개를 한 번의 계산으로 건너뜁니다.

어떻게 도나:

  1. 후보 전체를 결정 하나로 두 묶음으로 나눕니다
  2. 묶음마다 「아무리 잘 돼도 이 값까지」를 어림합니다
  3. 그 값이 지금까지 찾은 답보다 못하면 묶음을 버립니다. 나으면 다시 나눕니다

무엇이 나빠지나 — 어림이 느슨하면 버리는 묶음이 거의 없습니다. 그러면 모든 후보를 따지는 것만큼 오래 걸립니다. 문제마다 좋은 어림을 따로 궁리해야 합니다.

언제 쓰나 — 가장 좋은 답이 꼭 필요할 때 씁니다. 쓸 만한 답이면 충분할 때는 더 빨리 끝나는 방법을 씁니다.

상세

분기 한정(branch and bound)은 가장 좋은 답 하나를 고르는 문제를 푸는 알고리즘 설계 기법입니다. 문제 하나를 푸는 특정한 절차가 아닙니다. 여러 문제에 두루 입히는 뼈대입니다. 그리디 알고리즘이나 동적 계획법과 같은 부류의 이름입니다.

이 절은 먼저 이 기법이 푸는 문제와 후보를 늘어놓는 트리를 봅니다. 다음으로 이름을 이루는 두 동작인 분기와 한정을 봅니다. 이어서 물건 네 개짜리 배낭 문제를 손으로 풀고 같은 풀이를 코드로 봅니다. 끝으로 어림을 고르는 법, 탐색 순서, 이웃 기법과의 차이, 비용을 봅니다.

최저가 가게 고르기

최저가를 찾아 가게 여러 곳을 돈다고 해 봅시다. 첫 가게에서 3만 원짜리를 찾았습니다. 다음 가게 앞에 「전 품목 4만 원부터」라고 붙어 있습니다.

그 가게에는 들어갈 이유가 없습니다. 안의 물건을 하나도 안 봐도 3만 원보다 싼 것이 없다는 것을 압니다. 분기 한정은 이 판단을 후보 묶음마다 기계적으로 되풀이합니다.

최적화 문제와 탐색 트리

가능한 답 여럿 가운데 어떤 값을 가장 크게 또는 가장 작게 만드는 답을 고르는 문제를 최적화 문제라고 합니다. 가방에 담은 물건의 값 합을 가장 크게 하거나, 여러 도시를 도는 길이를 가장 짧게 하는 문제가 그렇습니다. 가장 좋은 답을 최적해라고 부릅니다.

답은 문제가 정한 조건을 지켜야 합니다. 가방에 물건을 담는 문제라면 담은 무게의 합이 가방이 버티는 한도를 넘으면 안 됩니다. 조건을 어긴 답은 값이 아무리 좋아도 답으로 치지 않습니다.

이런 문제의 답은 대개 작은 결정 여럿이 모여 만들어집니다. 배낭 문제라면 물건마다 「넣는다」와 「뺀다」 가운데 하나를 고릅니다. 물건이 n 개면 결정도 n 개입니다.

결정을 하나씩 내려 가는 과정은 트리로 그릴 수 있습니다. 맨 위 노드는 아무것도 안 정한 상태입니다. 한 단계 내려갈 때마다 결정이 하나 늘어납니다. 맨 아래 노드 하나가 완성된 답 하나입니다. 이 트리를 상태 공간 트리라고 부릅니다.

물건이 가·나·다·라 넷이면 트리는 아래 그림처럼 생겼습니다. 맨 위에서 몇 단계 내려왔는지를 깊이라고 합니다. 깊이가 하나 늘 때마다 노드 수가 두 배가 됩니다.

flowchart TD
    subgraph L0["깊이 0 · 노드 1개"]
        R["아무것도 안 정함"]
    end
    subgraph L1["깊이 1 · 노드 2개"]
        A["가 넣음"]
        B["가 뺌"]
    end
    subgraph L2["깊이 2 · 노드 4개"]
        A1["가 넣음 · 나 넣음"]
        A2["가 넣음 · 나 뺌"]
        B1["가 뺌 · 나 넣음"]
        B2["가 뺌 · 나 뺌"]
    end
    subgraph L4["깊이 3 은 생략 · 깊이 4 · 노드 16개"]
        AA["가를 넣은 답 8가지"]
        BB["가를 뺀 답 8가지"]
    end
    R --> A
    R --> B
    A --> A1
    A --> A2
    B --> B1
    B --> B2
    A1 --> AA
    A2 --> AA
    B1 --> BB
    B2 --> BB

트리의 노드 하나는 후보 묶음 하나이기도 합니다. 「가 넣음」 노드 아래에는 가를 넣은 답 8가지가 전부 달려 있습니다. 이 노드 하나를 버리면 그 8가지를 한꺼번에 버리게 됩니다.

노드 수는 깊이마다 두 배씩 불어납니다. 물건 30 개짜리 문제라면 맨 아래 노드가 10억 개가 넘습니다. 이 노드를 전부 보는 방법이 완전 탐색입니다.

분기

분기(branch)는 후보 묶음 하나를 결정 하나로 여러 묶음으로 나누는 일입니다. 「가를 넣은 답」과 「가를 뺀 답」으로 가르는 것이 한 번의 분기입니다. 트리에서는 노드 하나 아래에 자식 노드를 다는 일입니다.

이름의 「분기」는 가지가 갈린다는 뜻입니다. 코드의 조건 분기나 한 해를 넷으로 나눈 분기와는 다른 말입니다.

한정

한정(bound)은 묶음을 열어 보기 전에 「이 묶음에서 나올 값은 아무리 좋아도 여기까지」를 어림하는 일입니다. 묶음 안의 답을 하나하나 만들지 않고 계산 한 번으로 어림합니다.

한정으로 얻은 값을 한계라고 부릅니다. 한정은 어림하는 동작이고, 한계는 그 결과로 나온 값입니다. 뒤에서 자르는 판단은 전부 이 값을 보고 내립니다.

값을 가장 크게 만드는 문제에서 한계는 「이 묶음에서 나올 값은 아무리 커도 이것을 못 넘는다」는 값입니다. 이런 한계를 상한이라고 합니다.

값을 가장 작게 만드는 문제에서는 방향이 뒤집힙니다. 「아무리 작아도 이것 밑으로는 안 내려간다」는 하한을 씁니다. 앞의 가게 앞 「4만 원부터」가 하한입니다. 이 절의 나머지는 값을 크게 만드는 쪽으로 적습니다.

탐색하는 동안 지금까지 찾은 완성된 답 가운데 가장 좋은 것을 들고 다닙니다. 이 답을 현재 최선이라고 부릅니다. 한 묶음의 한계가 현재 최선보다 크지 않으면 그 묶음에서는 더 좋은 답이 나올 수 없습니다. 그 노드 아래를 전부 안 만듭니다.

가망 없는 갈래를 만들기 전에 잘라 내는 일을 가지치기라고 합니다. 분기 한정의 가지치기는 한계와 현재 최선을 견주어 자릅니다. 한정이 한계를 내놓습니다. 가지치기가 그 한계를 보고 자릅니다.

전체 절차는 안 본 노드가 떨어질 때까지 아래 셋을 되풀이합니다. 끝났을 때 들고 있는 현재 최선이 답입니다.

  1. 아직 안 본 노드 하나를 꺼냅니다
  2. 조건을 어겼거나 한계가 현재 최선보다 크지 않으면 버립니다
  3. 결정이 다 끝난 노드면 현재 최선과 견주어 바꿉니다. 아니면 분기해 자식 노드를 만듭니다

같은 절차를 그림으로 그리면 아래와 같습니다. 어느 갈래로 빠지든 다시 1번으로 돌아갑니다.

flowchart TD
    P["1 · 아직 안 본 노드 하나를 꺼냄"]
    Q{"조건을 어겼나<br/>또는 한계가 현재 최선보다 크지 않나"}
    X["버림"]
    D{"결정이 다 끝났나"}
    U["현재 최선과 견주어 바꿈"]
    S["분기해 자식 노드를 만듦"]
    P --> Q
    Q -->|예| X
    Q -->|아니오| D
    D -->|예| U
    D -->|아니오| S
    X --> P
    U --> P
    S --> P

배낭 문제로 한 번 풀기

배낭 문제는 무게 한도가 있는 가방에 물건을 골라 담아 값의 합을 가장 크게 만드는 문제입니다. 물건은 통으로 넣거나 빼야 하고 쪼갤 수 없습니다. 가방 한도는 10 입니다. 물건은 아래 넷이라고 칩시다.

물건 무게 값 무게 1 당 값
가 5 50 10
나 4 32 8
다 3 18 6
라 2 8 4

물건을 무게 1 당 값이 큰 순서로 늘어놓았습니다. 한계를 어림할 때 이 순서를 씁니다. 물건마다 넣고 빼는 조합은 모두 16 가지입니다.

한계는 「남은 물건을 쪼개 담을 수 있다고 치면」으로 어림합니다. 무게 1 당 값이 큰 것부터 담습니다. 마지막 물건은 남은 무게만큼 잘라 담습니다. 맨 위 노드에서 가와 나를 담으면 무게 9, 값 82 입니다. 남은 무게 1 에 다의 3분의 1 을 담으면 값 6 이 늘어 한계는 88 입니다.

쪼갤 수 있다고 치면 고를 수 있는 담는 법이 늘어납니다. 담는 법이 늘어도 가장 좋은 값은 줄지 않습니다. 그래서 쪼개서 얻은 88 은 쪼갤 수 없을 때 얻을 수 있는 가장 좋은 값보다 작을 수 없습니다. 문제의 조건 하나를 풀어 더 쉬운 문제로 바꾸는 이 방법을 완화라고 부릅니다.

넣는 쪽을 먼저 내려가며 풀면 아래 그림처럼 됩니다. 「버림」이 붙은 노드는 아래를 만들지 않은 노드입니다. 「82 확정 뒤」는 첫 답 82 가 나온 다음에 돌아와서 본 노드라는 뜻입니다.

flowchart TD
    R["맨 위 · 한계 88"]
    R -->|가 넣음| A["값 50 · 한계 88"]
    R -->|가 뺌| B["82 확정 뒤 · 한계 58 · 버림"]
    A -->|나 넣음| C["값 82 · 한계 88"]
    A -->|나 뺌| D["82 확정 뒤 · 한계 76 · 버림"]
    C -->|다 넣음| E["무게 12 · 초과"]
    C -->|다 뺌| F["값 82 · 한계 86"]
    F -->|라 넣음| G["무게 11 · 초과"]
    F -->|라 뺌| H["답 · 값 82"]

가·나를 넣고 다·라를 뺀 답이 처음 완성된 답입니다. 값은 82 입니다. 이 답이 현재 최선이 됩니다. 다를 넣은 노드와 라를 넣은 노드는 무게가 한도를 넘어 거기서 멈췄습니다.

그다음 돌아가서 본 두 노드가 분기 한정이 일하는 곳입니다. 가를 넣고 나를 뺀 묶음은 남은 다와 라를 다 담아도 한계가 76 입니다. 가를 뺀 묶음은 나·다·라를 다 담아도 58 입니다. 둘 다 82 를 못 넘으므로 아래를 만들지 않습니다.

가를 뺀 묶음 하나를 버리면서 조합 8 가지를 한 번에 건너뛰었습니다. 16 가지 조합 가운데 끝까지 따져 값을 낸 것은 하나뿐입니다. 그 하나인 가·나 조합, 값 82 가 최적해입니다.

같은 풀이를 코드로

앞의 손풀이를 파이썬으로 옮기면 아래와 같습니다. bound 가 한계를 어림하고 visit 가 트리를 넣는 쪽부터 내려갑니다.

Python
def solve(items, cap):
    best = 0

    def bound(i, w, v):
        for wt, val in items[i:]:
            if w + wt <= cap:
                w, v = w + wt, v + val
            else:
                return v + val * (cap - w) / wt
        return v

    def visit(i, w, v):
        nonlocal best
        if w > cap:
            return
        if i == len(items):
            best = max(best, v)
            return
        if bound(i, w, v) <= best:
            return
        wt, val = items[i]
        visit(i + 1, w + wt, v + val)
        visit(i + 1, w, v)

    visit(0, 0, 0)
    return best

items = [(5, 50), (4, 32), (3, 18), (2, 8)]
solve(items, 10)   # 82

items 는 (무게, 값) 짝을 무게 1 당 값이 큰 순서로 담은 목록입니다. bound 는 남은 물건을 앞에서부터 담다가 안 들어가는 물건을 만나면 남은 무게만큼만 잘라 더하고 끝냅니다.

visit 의 세 return 이 앞 절차의 2번과 3번입니다. 첫째는 무게 초과로 버립니다. 둘째는 결정이 다 끝난 답을 현재 최선과 견줍니다.

셋째 return 이 한계로 자르는 가지치기입니다. bound 호출이 한정입니다. 그 값을 best 와 견주는 비교가 가지치기입니다. 한계가 best 보다 크지 않으면 이 노드 아래로 내려가지 않습니다.

촘촘한 한계와 느슨한 한계

한계는 두 가지를 지켜야 쓸모가 있습니다. 첫째, 한계는 그 묶음 안의 가장 좋은 값보다 작게 나오면 안 됩니다. 작게 나오면 최적해가 든 묶음을 버릴 수 있습니다. 그러면 틀린 답이 나옵니다.

둘째, 한계가 그 묶음 안의 가장 좋은 값에 가까울수록 많이 버립니다. 무게 한도를 아예 무시하고 남은 물건을 전부 더해도 상한은 됩니다. 맨 위 노드에서 이렇게 어림하면 한계가 108 입니다.

맨 위 노드의 묶음은 모든 답입니다. 그 안의 가장 좋은 값은 최적해의 값 82 입니다. 108 은 쪼개 담는 어림이 준 88 보다 82 에서 멉니다. 한계가 느슨할수록 현재 최선을 못 넘는 묶음이 적어져 덜 버립니다.

한계를 촘촘하게 잡을수록 계산이 무거워지기 쉽습니다. 한계는 노드마다 다시 어림하므로 한 번의 비용이 노드 수만큼 곱해집니다. 덜 버리더라도 가볍게 어림할지, 무겁더라도 많이 버릴지를 문제마다 저울질합니다.

탐색 순서

다음에 꺼낼 노드를 무엇으로 고르느냐에 따라 같은 트리를 다른 순서로 훑습니다. 흔히 쓰는 순서는 아래 셋입니다.

순서 다음에 꺼내는 노드 얻는 것 내주는 것
깊이 우선 탐색 방금 만든 자식 완성된 답이 빨리 나와 일찍부터 버린다. 메모리는 트리 깊이만큼만 든다 첫 갈래에서 현재 최선이 낮게 잡히면 한참 헤맨다
너비 우선 탐색 가장 먼저 만든 노드 깊이 순서대로 고르게 본다 완성된 답이 늦게 나와 오래 못 버린다. 같은 깊이의 노드를 다 들고 있어야 한다
최선 우선 탐색 한계가 가장 좋은 노드 대개 따지는 노드 수가 가장 적다 열어 둔 노드를 모두 들고 있어 메모리가 크게 든다

최선 우선 순서는 한계가 가장 큰 노드를 매번 꺼내야 합니다. 이때 우선순위 큐를 씁니다. 들어 있는 값 가운데 우선순위가 가장 높은 것을 먼저 꺼내 주는 자료구조입니다.

탐색을 시작하기 전에 현재 최선을 미리 채워 두기도 합니다. 매번 당장 가장 좋아 보이는 것 하나만 고르는 그리디 알고리즘으로 빠르게 답을 얻습니다. 그 답을 첫 현재 최선으로 씁니다. 앞의 배낭 예에서 무게 1 당 값이 큰 순서로 담으면 가·나를 담아 82 를 얻습니다. 이 값을 들고 시작하면 첫 분기부터 가를 뺀 묶음을 버릴 수 있습니다.

이웃 기법과의 차이

분기 한정은 완전 탐색에서 출발해 후보를 덜 보는 기법 가운데 하나입니다. 이웃 기법들과는 무엇을 근거로 버리거나 줄이느냐가 다릅니다.

기법 버리거나 줄이는 근거 답
완전 탐색 안 버린다 최적해
재귀 백트래킹 조건을 이미 어긴 묶음을 버린다 조건을 지키는 답 전부 또는 최적해
분기 한정 조건을 어긴 묶음에 더해 현재 최선을 못 넘는 묶음을 버린다 최적해
동적 계획법 여러 묶음이 함께 쓰는 작은 문제의 답을 한 번만 구한다 최적해
그리디 알고리즘 매번 한 갈래만 따라가고 나머지를 안 본다 문제에 따라 최적해를 놓친다

재귀 백트래킹은 「이 묶음에는 조건을 지키는 답이 없다」로 자릅니다. 분기 한정은 「이 묶음에 답은 있지만 더 좋은 답은 없다」로도 자릅니다. 그래서 분기 한정은 답마다 견줄 값이 있는 최적화 문제에만 씁니다.

분할 정복도 문제를 작게 나눈다는 점은 같습니다. 분할 정복은 나눈 조각을 전부 풀어 그 답을 합칩니다. 분기 한정은 나눈 묶음 가운데 가망 없는 것을 풀지 않고 버립니다.

비용

분기 한정은 가장 운이 없을 때 완전 탐색보다 나아지지 않습니다. 한계가 한 번도 현재 최선 아래로 안 내려가면 모든 노드를 만들게 됩니다. 결정이 n 개인 배낭 문제라면 이때 맨 아래 노드가 2ⁿ 개입니다. 빅오 표기법으로 O(2ⁿ) 입니다.

보통 얼마나 덜 따지는지는 문제와 한계에 달려 있습니다. 앞의 예처럼 16 가지 가운데 하나만 끝까지 따지고 끝나기도 합니다. 한계가 느슨한 문제에서는 완전 탐색과 거의 같은 수의 노드를 봅니다. 미리 셀 수 있는 수치가 없어서 입력마다 돌려 봐야 압니다.

메모리는 탐색 순서가 정합니다. 깊이 우선으로 돌면 트리 깊이만큼만 들고 다닙니다. 최선 우선으로 돌면 열어 둔 노드가 불어나 메모리가 먼저 바닥나기도 합니다.

이 기법으로 푸는 문제

분기 한정은 후보가 폭발적으로 늘어나도 최적해가 꼭 필요한 문제에 씁니다. 대표가 정수 선형 계획법입니다.

정수 선형 계획법은 정할 값 여럿을 정수로만 고르는 최적화 문제입니다. 이 정할 값을 변수라고 부릅니다. 목표와 조건은 변수에 수를 곱해 더한 식으로 적습니다. 앞의 배낭 문제도 물건마다 넣으면 1, 빼면 0 인 변수를 두면 이 꼴이 됩니다.

이 문제에 분기 한정을 쓸 때는 변수가 정수여야 한다는 조건을 풀어 쉬운 문제로 바꿉니다. 그 쉬운 문제의 답으로 한계를 어림합니다. 앞의 배낭 예에서 물건을 쪼갤 수 있다고 친 것과 같은 방법입니다.

모든 도시를 한 번씩 들르는 가장 짧은 길을 찾는 외판원 순회도 도시가 많을 때 정답을 구하려면 이 기법을 씁니다. 작업을 기계에 나눠 끝나는 시간을 가장 짧게 하는 작업 스케줄링도 같은 부류입니다.

최적해를 포기해도 되는 문제라면 쓸 만한 답을 빨리 내는 휴리스틱이나 근사 알고리즘으로 갑니다. 분기 한정도 멈추고 싶을 때 멈추면 그때까지의 현재 최선을 돌려줄 수 있습니다. 가장 큰 한계와 현재 최선의 차이를 보면 그 답이 최적해에서 얼마나 멀 수 있는지도 압니다.

관련 항목

분기 한정과 나란히 쓰는 설계 기법

완전 탐색 · 재귀 백트래킹 · 동적 계획법 · 그리디 알고리즘 · 분할 정복 · 메모이제이션 · 알고리즘 설계 기법

분기 한정을 이루는 부품

상태 공간 트리 · 가지치기 · 상한 · 하한 · 선형 계획 완화 · 라그랑주 완화 · 현재 최선해

분기 한정이 노드를 꺼내는 탐색 순서

깊이 우선 탐색 · 너비 우선 탐색 · 최선 우선 탐색 · 우선순위 큐 · A* 알고리즘

분기 한정으로 푸는 문제

배낭 문제 · 외판원 순회 · 정수 선형 계획법 · 혼합 정수 계획법 · 작업 스케줄링 · 최대 클릭 문제 · 조합 최적화

분기 한정을 넓힌 기법

분기 절단법 · 분기 가격법 · 알파-베타 가지치기 · 절단 평면법

최적해를 포기하고 분기 한정 대신 쓰는 풀이

휴리스틱 · 근사 알고리즘 · 지역 탐색 · 담금질 기법

분기 한정의 비용을 재는 도구

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · NP-난해 · 조합 폭발

분기 한정이 속하는 상위 분류

알고리즘 · 최적화 문제 · 최적해 · 탐색 알고리즘

다른 이름: branch and bound · 분기 한정법 · 분기와 한정 · B&B