Branch and Bound Algorithm
- backtracking을 개선한 알고리즘
- state space tree은 backtracking처럼 그대로 사용됨
- 최적화 문제에 사용
What is a bound?
: 바운드는 노드를 넘어 확장하여 얻을 수 있는 해의 값?
- 노드의 경계를 계산하여 노드가 유망한지 여부를 확인
- 경계값이 지금까지 발견된 최상의 솔루션의 값보다 크지 않으면 non-promising
=> k - 1까지의 가장 큰 값이 bound라서 다음 노드의 bound가 Maxprofit보다 작으면 확인 할 필요 없음!
-> 내가 찾은 값이 더 크니까!
The 0/1 Knapsack Problem Revisited
: 가방에 최대한 많은 물건을 훔치자!-> 얼마짜리를 몇키로까지 훔칠 수 있는가 -> 가격과 무게를 고려
- profit : 지금까지 내가 고른 노드들의 총 값(가격)- weight : 지금까지 고른 노드들의 총 무게(무게)- total weight(totweight) : 넘치기 일보 직전의 weight 값
-> k에서 weight값이 넘친다면 k - 1까지의 합은 절대로 넘치지 않음
i까지 고른건 weight고 그렇기 때문에 넘치기 전까지는 i다음(i + 1)부터 k하나 전 까지(k - 1)의 weight의 합과 같다.
- maxprofit : 지금까지 내가 찾은 물건들의 합 중에 가장 큰 경우의 값- bound : 해당 상태에서의 최적해의 가능성을 평가하기 위한 값
-> 여기서 더 진행하는게 promising한가 판별할 수 있는 값
bound = 지금까지 고른 값 + 넘치기 직전까지의 값 + (전체 무게 - 최대한의 무게) * pk / wk
pk / wk는 무게 당 가격? 남는 자리 중에 가장 큰 값을 더하기..~ << item k의 단가
+ bound가 maxprofit보다 작은가?-> bound가 maxprofit보다 작다면 자식 노드를 탐색해도 더 큰 값을 얻을 수 없기 때문에 탐색 할 필요 없음(= non-promising)
그럼 어떻게 하면 될까요?
- 노드를 DFS나 BFS로 방문하기
- profit, weight, bound를 계산하기
- <W랑 bound>가? maxprofit이 될 때 까지 검색하기
- 없다면 backtrack
e.g n = 4 and W = 16
(0.0)에서 출발하다..
아마 $115는 bound 값?
115 = profit(0) + (i + 1)부터 k - 1까지의 profit의 합 + (최대 무게(W) - 지금 전체 무게(totweight)) * k의 profit / k의 weight
= 0 + ( 40 + 30 ) + (16 - 7) * 5 = 70 + 9 * 5 = 11598 = (p1 값은 선택, p2값은 미선택) + (i + 1 = 3, k - 1 = 3) + W - (1번은 이미 담고 2번은 이미 버려서 이제 3까지 담을 수 있음) + 4는 담을 수 없기 때문에 k = 4= 40 + 50 + (16 - 12) *2 = 40 + 50+ 4 * 2 = 98-> tree타고 내려가면서 mp(maxprofit)보다 큰 bound값을 발견했을 때 계속 찾으러 감
Analysis : 0/1 Knapsack Problem
Q. 좋아졌나요?
A. Monte Carlo Algorithm은 O(2^(n/2)) 이고 dynamic programming은 O(2^n)이기 때문에 아무튼 좀 더 좋아졌습니다.
Q. 더 좋은 방법은 없나요?
A. 트리 순회 방식을 DFS에서 BFS로 변경하면 어떨까요?
The Breadth First Search
void breadth_first_branch_and_bound(state_space_tree T, number& best) {
queue_of_node Q;
node u, v;
initialize(Q); //큐 초기화
v = root of T; //방문 중인 노드
enqueue(Q, v); // Q에 v(root node)를 넣기?
best = value(v); //가장 큰 값 일단 넣기
while(!empty(Q)) { //Q가 비어있지 않다면
dequeue(Q, v); //Q에서 v꺼내기
for(each child u of v) { //v의 child node u가 존재하면
if(value(u) is better than best) //best보다 u 좋다면
best = value(u); //바꾸기
if(bound(u) is better than best) //bound가 더 크다면
enqueue(Q, u); //u를 타고 내려감
}
}
}BFS 방식으로 해보기(ง˙∇˙)ว
+ DFS : 가로로 타고 내려감
- (4, 1)은 너무 무거워서 promising x
- (4, 2)는 (3, 2)보다 bound가 작음
- (4, 4)는 maxprofit과 동일하기 때문에 안됨
Best First Search with Branch and Bound
Q. 더 좋은 방법이 없을까요?
A. 모든 자식노드의 bound를 계산할 수 있죠. bound가 많으면 더 좋은가요? best first search를 해보아요.
void best_frist_brabch_and_bound(state_space_tree T, number best) {
priority_quere_of_node PQ;
node u, v;
initialize(PQ); // PQ 초기화
v = root of T; // v == root node
best = value(v); // root를 best로 설정
insert(PQ, v); // PQ에 v 넣기
while(!empty(PQ)) {
remove(PQ, v); //v 꺼내기
if(bound(v) is better than best) // v가 best보다 큰가 = promising한가
for(each child u of v) { //v의 자식들 u?
if(value(u) is better than best) //v의 값이 best보다 크면
best = value(u);
if(bound(u) is better than best) // u의 bound가 best보다 크면 찾으러 감
insert(PQ, u); //PQ에 u넣기
}
}
}
(0.0)부터 출발
- mp = 0
- profit = 0, bound = 115
(1, 1)
- profit(40) > mp(0)
- mp = 40, bound = 115
(1, 2)
- mp(40) < bound(82)
but mp(40) > profit(0)
-> non-promising
아무튼 그렇게 쭉쭉 타고 내려감..
그래서 branch and bound가 무엇이냐
1. mp(내가 지금까지 확인한 값 중에 가장 큰 값)이랑 bound(아마 이정도 되는 값을 찾을 수 있을 것)중에 bound가 더 큰가
2. profit이랑 mp랑 누가 더 큰가 -> mp가 더 크면 확인할 필요 x
3. 자식의 bound가 mp보다 더 크면 ~~(1번)
그래서 우리가 0/1 Knapsack Problem을 하기 위해 알아본 방식이 5개라고?
1. 아마 다이나믹 프로그래밍..(표 오백개 그리는 무언가)
2. Monte Carlo Algorithm
3. DFS(깊이 우선 탐색)
4. BFS(너비 우선 탐색 | 옆으로 타고감)
5. BFS(best first search)
아마도 이렇게 5개? 라고 합니다.
끝 !
'아무튼 공부중 > algorithm' 카테고리의 다른 글
| [알고리즘] problem Analysis in Insertion Sort (0) | 2023.12.13 |
|---|---|
| [알고리즘] The Traveling Salesperson Problem(외판원 문제) (0) | 2023.12.13 |
| [알고리즘] Monte Carlo Algorithm | Sum of Subsets Problem | Hamiltonian Circuits Problem (1) | 2023.12.06 |
| [알고리즘] Backtracking | n Queens Problem (0) | 2023.12.03 |
| [알고리즘] Chained Matrix Multiplication (연쇄 행렬 곱셈) (1) | 2023.10.24 |