Algorithms : Branch and Bound

이번 포스트에서는 Branch and Bound 알고리즘에 대해 배우고, 0 / 1 Knapsack, TSP 예제에 대해 다뤄볼 생각이다.

Branch and Bound

Backtracking vs Branch and Bound

Backtracking

• DFS 기반 으로 탐색 순서가 고정되어있다.
• g-value 중심으로 탐색을 진행한다.
• 코드 구현이 가능하다.

Branch and Bound

• Backtracking 과 유사한 구조이긴 하지만, 탐색 순서와 pruning 전략이 다르다.
• 목적
  • 최적화 문제 (Optimization P) : 최댓값 or 최솟값 찾기
  • 예) 0 / 1 Knapsack, TSP 등
• 구성
  • 각 노드에서 f = g + h 계산
    • g : 현재까지의 정확한 값 (exact value)
    • h : 앞으로 기대 가능한 값 (estimate, upper bound or lower bound)
  • promising 판단 여부
    • Maximization : f < Best (Non- promising) : Prune
    • Minimization : f > Best (Non - promising) : Prune

Branch And Bound란?

• 보통 BFS를 기반으로 한다.
• Bound 기반으로 유망한 노드를 우선적으로 탐색한다.
• g + h의 값으로 pruning을 진행하고, 탐색 순서가 유동적이다.
• 성능은 B&B가 더 좋기에 많이 사용된다.

f = g + h < Best (Bounding Function) 관점에서 비교하세요.

• tree traverse (child visit) 순서에 따라, g , h value는 update 차이가 발생한다.
• 미래 estimate인 h-value의 값이 좋으면 (정확한 예측이 가능), 잘 맞추기 때문에 BFS가 더 좋다.
  • start root 근처에서 Pruning을 일찍 발생하여 실제 속도를 더 빠르게 할 수 있기 때문이다.
• Backtracking은 탐색을 진행할수록, ‘g-value’ 가 빨리 갱신된다.
  • g-value가 정확해지고, h-value에 대한 불확실성이 빠른 속도로 줄어든다.

따라서,

h-value 설계/ 추정/ 수식 유도 등에 경험을 통해 자신감을 향상했을 때는 Branch and Bound가 훨씬 우월하다.

• 그렇지 않다면, Backtracking을 선호하는 것이 좋다.

Branch and Bound : Knapsack

• 0/1 Knapsack : Maximization Problem
• Upper Bound 사용 (Bound = g + h)
  • g : 현재까지 선택한 item의 profit 총합
  • h : 앞으로의 최대 profit 예상치

기본 알고리즘 Flow

1. 시작 노드 -> Queue에 넣기 (FIFO or Priority Queue사용)
2. 반복 과정
   • Queue에서 노드를 꺼낸다.
   • f = g + h를 계산한다.
   • promising 여부를 확인한다.
     • f < Best -> prune
     • promising -> 자식 노드 생성 -> Queue에 추가
3. Queue가 빌 때까지 반복한다.

Best-Frist B&B

• 일반적인 B&B는 BFS 기반 -> FIFO Queue
• Best-Frist B&B는 Priority Queue 사용
  • Bound 값(f)가 가장 좋은 노드부터 탐색

-> 탐색 순서가 Bound 기반으로 유동적으로 바뀐다. -> 성능향상

• Best First B&B는 Greedy 성향 + Global Optimal 보장
  • greedy와 다르게 Proof 가 필요하다.

여기서 할 수 있는 2가지 질문이 존재한다.

Q1. If Promising / Bound value가 다른 값이 배정된다면?

Q2. Best-First B&B + Greedy approach 가 optimal 한가?

1. Best Frist B&B 에서는 Queue 기준과 Promising check 기준을 일치시키는 것이 안전하다.

• 각 노드에서 Promising 여부 판단할 때 쓰는 기준과 Queue 정렬 기준인 Bound value가 다를 수 있다.
• 문제점은 만약 Queue에서 f값 기준으로 넣고 있지만, promising 판단에서 다른 기준으로 판단하면 비일관성(Inconsistency) 발생으로 최적성이 깨질 수 있다.
• 안전한 설계 방법
  • 보통은 Queue에 넣을 때 사용하는 f= g + h값과 동일한 기준으로 promising 판단을 해야한다.
  • 이걸 지키면 탐색 순서에 관계없이 optimal 하여 보장이 가능하다.

1. Best-Frist B&B는 탐색 순서가 Greedy 처럼 보여도 pruning 조건을 올바르게 잡으면 Optimality가 보장이 가능하다. 반면에 Greedy approach 자체는 local optimal choice만 보고 Global 보장을 못한다.

• Best-First B&B 가 global optimal을 만족하는 이유
  • 탐색 순서를 Greedy하게 가져가지만 pruning을 할 때는 반드시 Global Optimal 하도록 설계한다.
  • 핵심은 pruning 기준에 있다.
    • 절대로 현재까지 Best보다 f값이 큰 노드들은 남겨둔다.
    • 그래도 언젠가는 optimal solution이 들어있는 노드까지 탐색한다.

Branch and Bound : h-value

h-value의 정의

• 앞으로 얻을 수 있는 최대 profit의 추정치
• h 값이 크면 pruning이 잘 안된다. (보수적)
• h 값이 작으면 pruning이 잘 된다. (공격적)
  • 하지만 underestimate 하면 optimality가 깨질 수 있다.

→ B&B에서는 Overestimate가 안전함 → Optimal 해 보장 가능

→ Underestimate는 Optimal 해 pruning 위험 있음 → 쓰면 안 됨

Maximization 문제에서는 Upper Bound 역할

Minimization 문제에서는 Lower Bound 역할

OverEstimate 해도 되는 이유

• OverEstimate는 어쩌면 더 좋은 해가 있을지도 모른다 는 이유로 계속 탐색을 진행한다. -> pruning 보수적이다.
• 정답 Optimal한 해가 있는 branch는 pruning이 되지 않는다.

계산 방법

기본적으로 아래와 같은 수식으로 정의한다. \(0 < h^* < h < \infty\)

• h* : 실제 global optimal upper bound
• h : 우리가 계산해서 사용하는 추정치 (Estimate)

h는 항상 h*보다 크거나 같아야 안전하게 pruning이 가능하다

좋은 H-value 설정 방법

• h는 가능한 h*보다 조금만 큰 값이 좋다.

  • pruning 효과가 좋으면서 Optimal을 보장한다.
  \[h = h^* + \alpha \quad (\text{작은 값} \alpha)\]

0/1 Knapsack 에서의 H-value 계산

Fractional Knapsack (Greedy) 기반으로 h-value 계산

• 현재 남은 용량에서 가장 높은 profit/weight 비율가진 item 부터 채우기
• 마지막 item은 fractional로 채운다.
  • 최대 profit을 추정하면서 Upper Bound의 역할을 수행한다.

→ Fractional KS 기반 h-value는 Overestimate가 됨 → pruning 성능 좋고 correctness 유지 가능

Q. Minimization 문제에서는?

Lower Bound를 사용해야한다.

• h가 underestimate면 pruning이 안정적이다.
• Overestimate하면 pruning이 잘 안되고 느리다.
• Lower Bound 대표적 예시 문제 : TSP

Branch and Bound : TSP

• TSP : Traveling Salesman (Sales Person) Problem

• 목표: 모든 모든 도시를 한 번씩 방문하고 다시 출발점으로 돌아오는 최소 비용의 경로 찾기 -> Minimization

  • B&B 사용시에 h-value 설계가 핵심이다.

Minimization 문제에서는:

• h는 Lower Bound 역할을 해야 한다.

• 반드시 UnderEstimate 해야 안정적으로 pruning이 가능하다. \(h < h^*\)

  • Overestimate 사용 시 Optimal 해 pruning risk 존재하다.

TSP Idea

• TSP에서 쓸 수 있는 heuristic \(h = h^* - α (작은 값)\)

1. min outgoing edge cost per node

각 노드에서 나가는 edge 중에서 최소 비용을 사용한다.

1. min incoming edge cost per node

각 노드로 들어오는 edge 중 최소 비용을 사용한다.

• 이런 값들의 합이 h-value로 사용 -> Lower Bound 역할

• g-value
  • 현재까지 방문한 edge들의 정확한 cost의 합계
• h-value
  • 방문하지 않은 node들의 최소 outgoing/incoming edge cost 합산

예시)

node 1 방문 후에 node 2를 방문하고 나머지 node 들에 대해 \(h = min(V3. outgoing. edge) + min(V4. outgoing .edge) + min(V5 .outgoing. edge)\)

H-value 설계 유연성

Bound Function (h-value)는 유일하지 않다.

• 여러 heuristic 을 조합하거나 다양한 방법으로 설계가 가능하다.

• 더 강력한 pruning을 원하면 좋은 heuristic을 사용해야한다.

• 예시 ) In TSP

  • entering cost + existing cost 의 평균 사용
  \[h3 = (min. entering v2 + min.exiting v2) / 2\]
  • 더 강력한 h-value 설계가 가능하다.
  • 더 강력한 pruning power를 얻을 수 있다.

Advanced Issue

1. Branch Factor

• TSP B&B 에서는 Branch Factor가 작을수록 pruning 효과가 좋다.
• 하지만 너무 작으면 exploring 부족으로 optimal한 해를 놓칠 수 있다.
  • 적절한 balance가 필요하다.

1. Relaxation Technique

• h-value 계산 시 Relaxation 사용
  • Constraint를 약화시켜 계산을 단순화한다.
  • 매우 중요한 요소이지만, h-value 에 대한 절대적인 가이드라인은 없다.

Relaxation Technique이란?

• 문제의 Constraints를 일부 제거하여 문제를 단순화한다.
• Relaxed 문제의 optimal soluton을 h-value로 사용한다.

1. What if |v| = n is HUGE in TSP?

• TSP 문제 사이즈 폭발 -> 탐색 공간이 O(n!) -> FULL 탐색 불가능

• 기존 B&B 기반 접근으로는 비효율적이다.

  • 새로운 New Design approach가 필요.

• TSP는 NP-Hard 문제

  • polynomial 시간에 optimal 해를 보장하는 알고리즘은 없다.

  • Approximation Algorithm 사용이 필요하다.

---

앞서 Branch and Bound 외에 Backtracking 문제를 보면 NP-Hard, NP-Complete, Polynomial Time 이런 얘기가 많았지만, 다음 Algorithm : Approximation Algorithm 에서 NP 에 대한 정의와 설명을 다룰 예정이다.