T'SPACE

다채로운 에디터들의 이야기

컴퓨터공학/알고리즘

Branch and Bound 분기 한정 알고리즘

Tonny Kang 2024. 6. 5. 16:14
반응형

https://tonnykang.tistory.com/224

 

Back Tracking 백트래킹 알고리즘

백트래킹 알고리즘여러 다양한 방법을 순서대로 탑색하면서조건을 만족시키는 솔루션을 찾을 때 까지 되돌아가서 찾는 방법이다마치 미로를 탐색하는 것을 생각하면 되고탐색하다가 Promising

tonnykang.tistory.com

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


분기 한정법은 백트래킹 알고리즘을 개선한 방법으로, 각 노드에서 한계값(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 문제를 효율적으로 해결할 수 있다!!

반응형