분지 한정법(Branch and Bound) 알고리즘

분지 한정법(Branch and Bound) 알고리즘

• 분지 한정법(Branch and Bound) 은 최적의 해를 찾기 위해 탐색 공간을 체계적으로 줄여가는 알고리즘으로, 주로 조합 최적화 문제 에서 활용됩니다.
• 복잡한 문제일수록 가능한 해의 수가 기하급수적으로 증가하기 때문에, 모든 경우를 탐색하는 완전 탐색(Brute Force) 방법은 매우 비효율적입니다.

• 예를 들어, 외판원 문제(Travelling Salesman Problem, TSP) 나 배낭 문제(Knapsack Problem) 와 같은 문제는 가능한 경로와 조합의 수가 매우 크기 때문에 단순한 탐색으로는 현실적인 시간 내에 최적의 해를 찾기 어렵습니다.
• 이때 분지 한정법은 불필요한 경로와 경우의 수를 조기에 제거하여 탐색 효율을 크게 개선하는 데 중요한 역할을 합니다.

---

1. 기본 아이디어

• 분지 한정법(Branch and Bound)은 최적화 문제를 해결하는 조합 최적화 기법으로, 주로 다음과 같은 문제에 사용됩니다:
  • 배낭 문제 (Knapsack Problem)
  • 외판원 문제 (Travelling Salesman Problem, TSP)
  • 정수 선형 계획법 (Integer Linear Programming, ILP)
  • 최소 비용 신장 트리 (Minimum Spanning Tree)

---

2. 구성 요소

• 상한 (Upper Bound) : 최적해가 가질 수 있는 최댓값 (예: 배낭 문제에서의 최대 가치)
• 하한 (Lower Bound) : 최적해가 가질 수 있는 최솟값 (예: 최소 경로 길이)
• 결정 변수 (Decision Variables) : 각 분기점에서 결정해야 하는 변수
• 가지치기 (Pruning) : 불필요한 분기를 제거하여 탐색 공간을 줄이는 작업

---

3. 알고리즘 단계

• (1) 초기화
  • 최상의 해를 저장하는 변수 초기화
  • 루트 노드 생성 (전체 문제)
• (2) 분기
  • 현재 노드를 여러 하위 노드로 분할
  • 각 하위 노드에서 가능한 모든 선택을 나열
• (3) 한정
  • 각 하위 노드에 대해 상한과 하한 계산
  • 하한이 현재 최상의 해보다 나쁜 노드는 가지치기
• (4) 탐색
  • 분할된 노드들을 우선순위 큐(Priority Queue) 또는 스택(Stack)에 추가하여 탐색
  • 목표는 최상의 해를 찾는 것
• (5) 종료
  • 모든 노드를 탐색하거나, 더 이상 나은 해를 찾을 수 없을 때 알고리즘 종료

---

4. 예시: 0/1 배낭 문제 (Knapsack Problem)

• 주어진 배낭의 용량을 넘지 않으면서, 최대 가치를 얻는 방법을 찾는 문제입니다.
• 분지 한정법을 사용하여 각 아이템을 포함할지 결정하고, 포함하지 않는 경우를 분할하여 탐색합니다.
• 관련 글 : https://j2doll.tistory.com/1089

view raw Branch.and.Bound.ko.md hosted with ❤ by GitHub

---

• 도움이 되셨으면 하단의 ❤️ 공감 버튼 부탁 드립니다. 감사합니다! 😄
• 일부 모바일 환경에서는 ❤️ 버튼이 보이지 않습니다.

view raw i.like.it.ko.md hosted with ❤ by GitHub