11. Backtracking(DFS) B&B(BFS)

🎒 0/1 Knapsack Problem (with Backtracking)

📌 문제 정의

• 무게 집합:
  $w_i = (w_1, w_2, ..., w_n)$

• 이익 집합:
  $p_i = (p_1, p_2, ..., p_n)$

• 최대 수용 무게:
  $W$ (Knapsack 용량)

• 목표:
  총 무게가 $W$를 넘지 않으면서, 이익(profit)이 최대가 되도록 아이템 집합 $A$ 선택

---

이 슬라이드에서는 0/1 Knapsack 문제에서의 Backtracking과 Bounding Function 설계를 다루고 있어요. 요점 정리해줄게요:

---

🔹 Promising / Nonpromising Function (오른쪽 위)

Promising function이란?
탐색을 계속할지 말지 판단하는 기준 함수.

• 조건 1: 현재 weight > W → 확장 중지
• 조건 2: (현재 weight + 다음 아이템 weight) > W → stop
• 조건 3: (현재 weight + 다음 아이템들의 총합) < W → stop

⇒ 즉, 더 넣어봐도 W를 넘지 못하면 확장할 필요가 없음.
⇒ 이게 바로 Nonpromising, 즉 더 이상 유망하지 않음.

✳️ 여기서 말하는 것처럼:
Nonpromising function ≈ Bounding function 으로 봐도 됨.

---

✴️ 탐색 조건:

bound(g+h) < BEST(현재까지 얻은 최선의 이익) → 더 탐색 안 함 (nonpromising)

• h는 문제마다 다양한 방식으로 추정 가능 (교수는 자유롭게 해보라고 함)
• 예시에서 h는 fractional knapsack 방식으로 일부 아이템만 나눠 담는 것도 허용하여 계산

---

📌 정리

용어	의미
Promising	유망해서 계속 탐색할 가치가 있음
Nonpromising	더 탐색해도 최적 해에 못 미침 → Prune
Bound Function	현재 이익 + 미래 최대 추정 이익
g + h < BEST	현재 경로는 더 볼 필요 없음

---

🧭 Promising / Non-promising 조건

Promising function이란?
탐색을 계속할지 말지 판단하는 기준 함수.

조건 1: 현재 weight > W → 확장 중지
조건 2: (현재 weight + 다음 아이템 weight) > W → stop
조건 3: (현재 weight + 다음 아이템들의 총합) < W → stop

⇒ 즉, 더 넣어봐도 W를 넘지 못하면 확장할 필요가 없음.
⇒ 이게 바로 Nonpromising, 즉 더 이상 유망하지 않음.

✳️ 여기서 말하는 것처럼:
Nonpromising function ≈ Bounding function 으로 봐도 됨.

---

📐 Bound Function 개념

• 백트래킹에서 promising 판단 기준 = bound function

• 정의:
  $\text{Bound} = g + h$

  • $g$: 지금까지 선택한 아이템들의 이익 총합 (현재 profit)
  • $h$: 남은 아이템들로부터 얻을 수 있는 최대 이익의 추정치

• 판단 기준:
  $g + h < \text{현재까지의 BEST}$ → Non-promising

---

🔸 예시 수식 (오른쪽 아래):

• g: item_1 ~ item_i 까지의 이익 합

• h: item_i+1 ~ item_k 까지 이익 합

  • item_k+1 일부만 담을 수 있다고 가정하고 비율 계산

p_k+1 / w_k+1 * 남은 무게

💡 추가 설명

• $h$: 경험적 추정값 (heuristic)
  → 미래 이익을 예측하기 위한 추정치

---

❓ 교수님 질문

Q. $h$를 크게 추정하면 pruning이 더 잘 될까?

---

✅ Yes — 장점

• Pruning power 증가
  → 유망하지 않은 경로를 더 빨리 잘라냄
  → 탐색 속도 향상

---

❌ No — 단점

• 잘못된 가지치기 (Invalid pruning) 발생 가능
  → 실제로는 좋은 해가 존재하는 경로를 조기에 제거할 위험
  → 최적 해를 놓칠 수 있음

---

🔁 결론

• $h$ 값은 보수적이고 신중하게 설계되어야 함
• 속도와 정확성 사이의 균형이 중요함

위는 Backtracking 으로 푼 것이다 ( 빨강 → 파랑 → 핑크 )
다음으로 Branch and Bound (B&B) 알고리즘을 사용해서 풀어보자

---

📘 Branch and Bound

🐖 기본 B&B Algorithm

---

🆕 NEW B&B Algorithm:

1. Branch and Bound with Best-First (Search)

   • 평가 함수:

     $f(n) = g(n) + h(n)$

     (g: 현재까지 비용, h: 휴리스틱 예측)

   • 우선순위가 가장 좋은(h가 제일 큰) 노드를 먼저 확장하는 방식

2. Best-first Branch and Bound

   • Best-first 전략을 사용하여 탐색 성능 향상

3. A 알고리즘 (인공지능에서 사용됨)

   • 대표적인 Best-first Search 기반 알고리즘

---

☃️ 예시

이 경우 h = 98 로 가장 큰 노드를 제일 먼저 수행한다

---

"모든 방법들은 all enumerations 가능"
→ 모든 가능한 경우의 수(열거)를 다 탐색할 수 있는 구조라는 뜻입니다.