Branch and Bound 분기 한정 알고리즘

https://tonnykang.tistory.com/224

Back Tracking 백트래킹 알고리즘

백트래킹 알고리즘의 개선: 분기 한정법

---

분기 한정법은 백트래킹 알고리즘을 개선한 방법으로, 각 노드에서 한계값(bound)을 계산하여 해당 노드가 유망한지 판단한다. 만약 한계값(bound)이 현재까지의 최적 해보다 좋지 않다면, 그 방향으로 탐색을 진행할 필요가 없음으로 필요없는 탐색을 줄일 수 있다.

반응형

탐색 순서에는 크게 두가지가 있는데

너비 우선 분기 한정법 (BF-Branch and Bound)

---

일반적으로 큐(Queue)를 사용하여 구현된다

일반적이 BFS 그래프 탐색법을 이용하며

Promising하지 않으면 그 노드를 Pruning 하면된다

728x90

 

최선 우선 분기 한정법 (BestSearch-Branch and Bound)

---

우선순위 큐(Priority Queue)를 사용하여 가장 유망한 노드부터 탐색한다.

이는 힙(Heap)을 사용하여 구현할 수 있습니다.

• 우선순위 큐는 최소 힙(Min-Heap) 또는 최대 힙(Max-Heap)으로 구현할 수 있다
• Min-Heap은 트리의 root 노드가 최소값으로 되어있고 Max-Heap은 root 노드가 최대값으로 되어있다
• 삽입, 삭제, 최소/최대 값 확인의 시간 복잡도는 O(log n)이다.
• 삽입은 가장 트리 밑에 삽입되어 Bubble up 되어지고 (부모와 비교 후 sort)
• root와 가장 아래 노드를 위치를 바꾼뒤, 밑 노드를 버리고 root노드가 Bubble Down된다

TSP 문제에 분기 한정법 적용하기 

Traveling Salesman Problem with Branch and Bound

---

1.  초기화 Initialization:
   • 시작 도시를 루트 노드로 하고 빈 경로set으로 시작한다.
   • 루트 노드에 대한 한계값을 계산합니다. Bound!

   • 

   • 지금까지 경로를 계속 택하면 대충 최소 이정도는 걸리겠다는 예상 값이므로, 현재 최적해 보다 오래 걸리면 굳이 탐색할 필요가 없다

1. 분기 Branching:
   • 현재 노드를 확장하여 자식 노드를 생성g한다. 각 자식 노드는 현재 도시에서 방문 가능한 다음 도시를 나타낸다.
   • 각 자식 노드에 대해 부분 경로를 업데이트하고 해당 도시로 이동하는 비용을 계산한다.
   • 각 자식 노드에 대한 하한값을 계산한다.
2. 한정 Bounding:
   • 계산된 한계값을 사용하여 탐색할 노드를 결정합니다. 노드의 하한값이 현재 최적 해보다 크면 해당 노드를 가지치기합니다.
   •  위에 언급한 Breadth First나 Best First방식을 쓰면 됨
   • 노드의 하한값이 현재 최적 해보다 작거나 같으면 해당 노드를 탐색할 노드 목록에 추가한다.

 

위와 같은 방식으로 분기 한정법을 적용하여 TSP 문제를 효율적으로 해결할 수 있다!!