이번챕터에서는 branch-and-bound 알고리즘에 대해 정리할 예정이다. 목차는 다음과 같다.
- Branch-and-Bound algorithm
- 0/1 Knapsack Problem
- using DFS
- using BFS (Breath-First Search)
- using BFS (Best-First Search)
BFS, DFS 개념은 아래 게시물에 정리되어있다.
https://wanna-developer02.tistory.com/54
[알고리즘] CHAP 5. Backtracking Algorithm (백트래킹 알고리즘) - Monte Carlo Algo-
이번 챕터에서는 백트래킹 알고리즘에 대해 정리하려고 한다. 목차는 다음과 같다. Backtracking Algorithm (백트래킹) DFS BFS Monte Carlo Algorithm (몬테카를로 알고리즘) Solve problem 1. N Queens Problem 2. Sum-of-Su
wanna-developer02.tistory.com
1. Branch-and-Bound Algorithm (분기한정 알고리즘)
분기한정알고리즘은 백트래킹 향상기법으로 오직 최적화 문제에만 사용된다는 특징이 있다. 탐색하는 분기(branch)를 한정하여 불필요한 탐색을 줄인다. 여기서 분기를 한정하는 방법으로 Bound가 사용되는데, bound는 노드의 경계값으로 이를 계산하여 promising여부를 판단한다.
여지껏 발견된 최고의 solution 값보다 좋지 않으면 non-promising으로 판단하여 탐색하지 않는다.
2. 0/1 Knapsack Problem
knapsack problem (배낭문제)는 n개의 물건을 가치(profit)이 가장 높게, 지정된 무게를 넘지 않도록 담는 문제로 DP 문제로 많이 알려져있다. knapsack에는 물건을 쪼개 가져갈 수 있는 Fraction Knapsack problem과 가져가거나 가져가지 않는 선택지만 있는 0/1 Knapsack problem이 있다. 지금 살펴볼 문제는 0/1 Knapsack problem이다.
노드에는 profit, weight, bound를 기입해야한다.
- profit : 여지껏 선택한 물건의 총 가격
- weight : 여지껏 선택한 물건의 총 무게
- bound : 해당 노드를 넘어서 최고로 얻을 수 있는 경계값
- bound = profit + ∑p (현재노드의 다음노드부터 k-1까지) + (W - totweight) * (pk / wk) -> (k = 주어진 무게 넘는 첫 노드의 인덱스, W = 주어진 한정무게)
- totweight = weight + ∑w (현재노드의 다음노드부터 k-1까지)
bound <= maxprofit이면 노드는 non-promising이다!
이를 SST에서 내려가며 계산해나가야 한다. SST를 탐색하는 알고리즘에 따라 방문하는 노드의 순서가 달라지고, 효율 또한 달라질 수 있다!
예시 문제를 보면서 알아보자.
1. SST in DFS
위 그림은 DFS를 이용해 노드를 방문한 경우이다. 세번째 숫자가 bound를 계산한 값이다. 노드 (1,1)의 bound를 계산하는 과정을 설명하면 다음과 같다.
(1,1) 노드는 i = 1인 물건을 훔쳤다고 가정하는 경우이고, (1,2) 노드는 i = 1인 물건을 훔치지 않았다고 가정하는 경우이다. (Decision Tree와 비슷하다고 보면 될 것 같다)
(1,1)은 i = 1 물건을 훔쳤다고 가정하기 때문에, profit = 40, weight = 2가 된다. bound는 아래와 같이 계산한다.
우선 totweight를 먼저 구해주면 weight + ∑w (현재노드의 다음노드부터 k-1까지) 이고, k는 무게를 넘는 첫 노드 즉 3이다. (3번 물건까지 담으면 weight가 17이 되므로 16을 초과하는 첫 물건이 된다.)
따라서 totweight = 2 + 5 = 7 이 된다.
이를 이용해 bound도 계산할 수 있다. bound = profit + ∑p (현재노드의 다음노드부터 k-1까지) + (W - totweight) * (pk / wk) 이므로 40 + 30 + (16 - 7) * 5 = 115 가 된다. 따라서 위 그림은 잘 계산되었다고 볼 수 있다!
이때 promising을 판단하는 조건은 2개이다.
- 무게를 초과하지 않았는가?
- bound값이 maxprofit보다 큰가?
두가지 조건을 모두 만족해야만 한다. maxprofit은 노드의 profit의 최대를 뜻해서, 노드를 방문할 때 갱신된다. (조건1을 만족하고 조건2를 판단하기 전에 갱신된다는 점에 유의하자)
그래서 (3,2)를 만났을 때 maxprofit이 70으로 갱신되고, (4,1)을 만날 때 80으로 갱신되지만 (4,1)의 bound가 80이므로 non-promising으로 판단되어 더이상 탐색하지 않는다.
위 과정을 반복하여 총 13개의 노드를 탐색하게 된다.
2. SST in BFS
위 그림은 BFS를 이용해 탐색한 경우이다. 위 그림과 같이 BFS를 이용하면 17개의 노드를 방문해야 하고, 이는 DFS보다 비효율적이라는 것을 확인할 수 있다.
Knapsack문제를 DP로 풀 때에는 O(2^n)의 time complexity가 나오고, Branch&Bound 알고리즘을 이용하면 O(2^(n/2))가 나온다. 이를 통해 Branch&Bound를 쓰는 것이 DP를 이용했을 때보다 time complexity가 효율적이라는 것을 확인할 수 있다.
DFS나 BFS보다 효율적으로 계산하기 위해 Best-First Search가 고안되었다고 한다.
3. SST in BFS (Best First Search)
Best-First Search는 bound다 큰 노드를 우선 탐색하는 방법이다. 먼저 어떤 노드의 모든 자식을 방문한 후, bound가 크고 유망한 (promising) 노드를 먼저 탐색한다. 아직 자식을 탐색하지 않는 노드 중 bound가 큰 노드의 자식들을 탐색하는 알고리즘이라고 생각하면 된다.
이렇게 정리가 끝났다. NP, P를 다음챕터이자 마지막 챕터로 다룰까 했지만, 나조차도 아직 완벽히 이해하지 못한 거 같아서 일단 패스하려고 한다! 이렇게 알고리즘 기초 정리 끝!
'알고리즘' 카테고리의 다른 글
| [알고리즘] CHAP 5. Backtracking Algorithm (백트래킹 알고리즘) - Monte Carlo Algo- (1) | 2024.01.03 |
|---|---|
| [알고리즘] CHAP 4. GA - Dijkstra's algorithm (다익스트라 알고리즘) (0) | 2023.12.30 |
| [알고리즘] CHAP 4. GA - Kruskal's algorithm (크루스칼 알고리즘) (0) | 2023.12.30 |
| [알고리즘] CHAP 4. The Greedy Approach (탐욕알고리즘) - Prim's alg (프림알고리즘) (4) | 2023.12.29 |
| [알고리즘] CHAP 3. Graph Theory (그래프) - 그래프로 최단거리 구하기 (1) | 2023.12.28 |