algo_lec17

Branch-and-Bound (B&B)

Branch-and-Bound 개념

• Backtracking의 확장 개념
• 상태 공간 트리를 기반으로 탐색
• Optimization 문제에만 사용됨
• 항상 최적해(optimal solution)를 보장
• 트리 탐색 방법은 다양함:
  • Depth-First Search (DFS)
  • Breadth-First Search (BFS)
  • Best-First Search (우선순위 큐 기반)

 

B&B 핵심 원리

• 각 노드에서 bound(상한)을 계산하여, promising 여부를 판단
• promising 노드: bound 값이 현재까지 발견된 최적값(current)보다 더 좋을 가능성이 있는 경우
• non-promising 노드: bound ≤ current → 더 이상 탐색할 가치 없음 → pruning

 

주요 B&B 탐색 전략

(1) DFS + Bound (일반적인 Backtracking과 동일)

• 현재 경로를 따라 깊게 탐색
• bound를 이용해 불필요한 경로 가지치기

(2) BFS + Bound (FIFO B&B)

• 노드를 큐(queue)에 넣고 생성 순서대로 확장
• 각 노드를 꺼낼 때 bound를 계산하여 pruning
• 구현 방법:
  • 큐 초기화 → 루트 노드 삽입
  • 큐에서 꺼낸 노드의 자식 생성
  • bound가 current보다 좋은 경우에만 자식 노드 삽입
• 슈도코드

void bfs_b&b (T, current)
{
	node u, v;
	initialize(Q); // Initialize queue
	v = root of T; // Create root node
	enqueue(Q,v);
	current = value(v);
	while(!empty(Q)) {
		dequeue(Q,v); // Pop node to create its children
		for(each child u of v) { // Create child nodes
			if(value(u) is better than current)
				current = value(u); // record the best profit so far
			if(bound(u) is better than current)
				enqueue(Q,u);
		}}}

 

(3) Best-First Search + Bound (Least-Cost or LC B&B)

• 우선순위 큐(priority queue) 사용
• bound 값이 가장 좋은(낮은 비용 or 높은 이익) 노드를 먼저 꺼내서 확장
• 일반적으로 BFS보다 효율적
• 우선순위 큐는 heap으로 구현

 

Revisit 0-1 Knapsack problem with FIFO B&B

문제 설정

• 아이템 수: n = 4
• 무게: w = (2, 4, 10, 5)
• 이익: p = (30, 20, 40, 10)
• 배낭 용량: M = 15
• 단위 이익 기준 정렬 (pᵢ/wᵢ): (15, 5, 4, 2) 순서

Bound 계산 공식

psum = 현재까지의 이익
wsum = 현재까지의 무게
k = 무게 누적으로 처음 초과되는 항목의 인덱스
wtotal = wsum + ∑(i+1 ~ k-1) wj
bound = psum + ∑(i+1 ~ k-1) pj + (M - wtotal) × (pk / wk)

→ fractional knapsack 방식으로 bound 계산

 

Pruning 조건

• wsum ≥ M: 배낭 초과 → 탐색 중단
• bound ≤ current: 더 좋은 해 불가 → 탐색 중단

 

FIFO B&B 예시

 

탐색 절차

 

①번 노드 확장; create 2,3 and insert them

• current = 30으로 갱신 (노드 1의 value가 30)
• 자식 노드 ②, ③ 생성 → 둘 다 bound > current → 큐에 삽입
• 큐 상태: [②, ③]

②번 노드 확장; create 4,5 and insert them

• current = 50으로 갱신 (노드 2의 value = 50)
• 자식 노드 ④, ⑤ 생성 → 둘 다 bound > current → 삽입
• 큐 상태: [③, ④, ⑤]

③번 노드 확장; create 6,7 and only insert 6

• value = 30 → current 유지 (50)
• 자식 노드 ⑥, ⑦ 생성
  • ⑥의 bound > current → 삽입
  • ⑦의 bound ≤ current → pruning
• 큐 상태: [④, ⑤, ⑥]

④번 노드 확장; create 8,9 and only insert 10

• value = 50 → current 유지 (50)
• 자식 노드 ⑧, ⑨ 생성
  • ⑨의 bound > current → 삽입
  • ⑧의 bound ≤ current → pruning
• 큐 상태: [⑤, ⑥, ⑨]

⑤번 노드 확장; create 10,11 and only insert 10

• value = 70 → current 갱신 (70)
• 자식 노드 ⑩, ⑪ 생성
  • ⑩의 bound > 70 → 삽입
  • ⑪의 bound ≤ 70 → pruning
• 큐 상태: [⑥, ⑨, ⑩]

⑥번 노드 확장; create 12,13 and not insert them

• value = 50 → current 유지
• 자식 노드 ⑫, ⑬ 생성 → 둘 다 bound ≤ current → 삽입 안 함
• 큐 상태: [⑨, ⑩]

⑨번 노드 확장; create 14,15 and not insert them

• value = 50 → current 유지
• 자식 노드 ⑭, ⑮ 생성 → 둘 다 bound ≤ current → 삽입 안 함
• 큐 상태: [⑩]

⑩번 노드 확장; create 16,17 and not insert them

• value = 50 → current 유지
• 자식 노드 ⑭, ⑮ 재생성 시도 → bound ≤ current → 삽입 안 함
• 큐 상태: 비어 있음 → 종료

---

• 큐 초기화 → 루트 노드 삽입
• 각 노드에서 자식 노드 생성
• promising 여부에 따라 큐에 삽입

결과 요약

• Order to be expanded: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17
• 총 17개 노드가 생성됨
• Order to be popped: 1,2,3,4,5,6,9,10
• 그 중 실제로 꺼내져 확장된 노드는 8개

 

LC (Best-First 방식) B&B 예시

 

Strategies

• Search all child nodes of current node
  • 지금 확장 중인 노드의 자식 노드를 모두 만든 후, 각각에 대해 bound 값을 계산하고 판단함
  • pruning은 자식 노드가 생성된 뒤에 수행됨
• 아직 확장되지 않은 노드 중 bound 값이 가장 높은 노드를 선택하여 확장한다

Mostly LC B&B yield more efficiency than BFS B&B

대부분의 경우 LC B&B는 BFS B&B보다 더 효율적이다

• Use priority queue to select the node with highest bound in better manner
  • 우선순위 큐를 사용해 가장 높은 bound 값을 가진 노드를 선택한다
• Use heap to implement priority queue
  • 우선순위 큐는 heap을 사용해 구현하는 것이 일반적

슈도코드

void best_first_b&b (T, current)
{
	node u, v;
	initialize(PQ); // Initialize the priority queue
	v = root of T; // Create root node
	enqueue(PQ,v);
	current = value(v);
	while(!empty(PQ)) {
		dequeue(PQ,v); // Pop the node with the highest bound
		if(bound(v) is better than current)
			for(each child u of v) { // Create the child nodes
				if(value(u) is better than current)
					current = value(u); // record the best profit so far
				if(bound(u) is better than current)
					enqueue(PQ,u);
		}
	}
}

 

 

예제

 

1단계: 노드 ① (루트)

• (psum=0, wsum=0), bound = 86
• current = 0 → 노드 ① 확장

자식 노드 ② (include w₁=2 → psum=30)
자식 노드 ③ (exclude w₁)

→ 둘 다 promising하므로 큐에 삽입

 

current = 30

큐: [②, ③]

자식 노드 u 중에서 현재까지 얻은 최적값보다 더 높은 이익(value(u))이 있으면, 그때 current를 갱신.

if bound(u) > current: node u is promising → 탐색 계속 (큐에 삽입)
else: node u is not promising → 가지치기 (prune)

 

2단계: 노드 ② (psum=30, wsum=2), bound=86

• include w₂ (②) → 노드 ④: psum=50, wsum=6
• exclude w₂ → 노드 ⑤: psum=30, wsum=2

→ 둘 다 promising하므로 큐에 삽입

 

current = 50

큐: [③, ④, ⑤]

 

3단계: 노드 ④ (psum=50, wsum=6), bound=86

• include w₃ (10kg, 40) → wsum=16 > 15 → 초과 → pruning
  → 노드 ⑥: psum=90, wsum=16 → X
• exclude w₃ → 노드 ⑦: psum=50, wsum=6, bound=60
  → bound=60 < current=50 → 조건 만족하므로 삽입

큐: [③, ⑤, ⑦]

 

4단계: 노드 ⑤ (psum=30, wsum=2), bound=76

• include w₃ → 노드 ⑧: psum=70, wsum=12
• exclude w₃ → 노드 ⑨: psum=30, wsum=2

→ 노드 ⑧은 psum이 70 → current 갱신
→ 노드 ⑨은 bound=40 < current=70 → pruning

 

current = 70
큐: [③, ⑦, ⑧]

 

5단계: 노드 ⑧ (psum=70, wsum=12), bound=76

• include w₄ → psum=80, wsum=17 > M → pruning
• exclude w₄ → psum=70, wsum=12

→ 둘 다 bound ≤ current → 삽입 안 함

 

큐: [③, ⑦]

 

6단계: 노드 ③ (exclude w₁), psum=0, wsum=0, bound=62

• bound=62 < current=70 → non-promising 노드 → 확장 안 함, 버림

큐: [⑦]

 

7단계: 노드 ⑦ (psum=50, wsum=6), bound=60

• bound < current → non-promising 노드 → 확장 안 함, 버림

---

탐색 절차

• 우선순위 큐에 루트 삽입
• bound가 가장 좋은 노드를 꺼내서 자식 확장
• promising한 자식만 다시 큐에 삽입

 

결과 요약

• Ordered to be expanded: 1,2,3,4,5,6,7,8,9,10,11
• 총 11개 노드만 생성/확장됨
• Order to be popped: 1,2,4,5,8,3,7
• FIFO B&B보다 적은 탐색으로 동일한 최적값 도달

---

Example: 15 Puzzle Problem

• 4x4 보드에서 1~15번 타일을 슬라이딩하여 정렬하는 문제
• How many initial arrangements? 16! = 16x15x14x...x2x1
• But not all the initial arrangements can reach the goal arrangement. (단, 항상 도달 가능한 상태만 탐색)

해답 조건 판별

• Thm. The goal state is reachable from the initial state iff ∑ (𝑖=1 to 16) less(i) + X is even
• 타일 순서의 역전 개수 + X 값이 짝수면 해답 도달 가능
  • position(i) is the position index of i in the initial state of the tile : goal에서 타일i의 위치값
  • less(i) is the # of tiles j s.t. j<i and position(j) > position(i) : 타일 i의 뒷 타일 중에 역순인 타일 개수
  • X = 1: 빈칸이 회색 영역일 경우 / X = 0: 그 외

왜 less(6)=1 인가?
→ {1,2,3,4,5} 중에서 위치가 5보다 큰 것: 5만 해당 ∴ 1

 

Use LC B&B

f(x) = 실제 깊이
ĝ(x) = 제자리에 있지 않은 타일 수 (misplaced tiles, excluding empty space)
ĉ(x) = f(x) + ĝ(x) → 우선순위

• 해는 이동 횟수를 최소화해야 하므로, 우선순위 큐에서 ĉ(x) 값이 가장 작은 노드를 선택한다.
• 노드 2, 3, 4, 5를 생성하여 큐에 삽입한다.
• ĉ(x) 값이 가장 작은 노드를 선택한다.

 

 

• 목적) 퍼즐을 최소 이동 횟수로 Goal 상태로 만들기

 

• 우선순위 큐에 있는 노드: 2, 3, 5, 10, 11, 12
• 평가값: 𝑐̂(10) = 2 + 1, 𝑐̂(11) = 2 + 3, 𝑐̂(12) = 2 + 3
• 따라서 노드 10 선택
• 노드 23에서 h(x) = 0 → 목표 도달!