반응형
https://tonnykang.tistory.com/224
백트래킹 알고리즘의 개선: 분기 한정법
분기 한정법은 백트래킹 알고리즘을 개선한 방법으로, 각 노드에서 한계값(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
- 초기화 Initialization:
- 시작 도시를 루트 노드로 하고 빈 경로set으로 시작한다.
- 루트 노드에 대한 한계값을 계산합니다. Bound!
- 지금까지 경로를 계속 택하면 대충 최소 이정도는 걸리겠다는 예상 값이므로, 현재 최적해 보다 오래 걸리면 굳이 탐색할 필요가 없다
- 분기 Branching:
- 현재 노드를 확장하여 자식 노드를 생성g한다. 각 자식 노드는 현재 도시에서 방문 가능한 다음 도시를 나타낸다.
- 각 자식 노드에 대해 부분 경로를 업데이트하고 해당 도시로 이동하는 비용을 계산한다.
- 각 자식 노드에 대한 하한값을 계산한다.
- 한정 Bounding:
- 계산된 한계값을 사용하여 탐색할 노드를 결정합니다. 노드의 하한값이 현재 최적 해보다 크면 해당 노드를 가지치기합니다.
- 위에 언급한 Breadth First나 Best First방식을 쓰면 됨
- 노드의 하한값이 현재 최적 해보다 작거나 같으면 해당 노드를 탐색할 노드 목록에 추가한다.
위와 같은 방식으로 분기 한정법을 적용하여 TSP 문제를 효율적으로 해결할 수 있다!!
반응형
'컴퓨터공학 > 알고리즘' 카테고리의 다른 글
String Matching Algorithms 문자열 매칭 알고리즘 (33) | 2024.06.08 |
---|---|
A* 알고리즘 (Dijkstra algorithm) (23) | 2024.06.06 |
Back Tracking 백트래킹 알고리즘 (40) | 2024.06.03 |
Merge Sort 합병 정렬 (45) | 2024.04.23 |
퀵 정렬 퀵 소트 quick sort (43) | 2024.04.22 |