2.
Branch-and-Bound(분기한정법)
: '최적의 경우'를 찾는 알고리즘으로써, '최소한 이정도는 되어야 답이 될 가능성이 있다'라는 범위(bound)를 정해두고 범위를 벗어나는 값들은 가지치기(Branch)해가며 결과값을 추적한다.
branch-and-bound 알고리즘의 원리
- 각 노드를 검색할 때 마다, 그 노드가 promising한지의 여부를 결정하기 위해서 한계값(bound)을 계산한다.
- 그 bound는 그 노드로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계를 나타낸다.
- 따라서 만약 그 bound가 지금까지 찾은 최적의 해답치 보다 좋지 않은 경우는 더 이상 가지를 뻗어서 검색을 계속할 필요가 없으므로, 그 노드는 non-promising 할 수 있다.
3.
Optimization 문제를 풀기 위한 일반적인 Backtracking 알고리즘
void checknode(node v) {
node u;
if(value(v) is better than best)
best = value(v);
if(promising(v))
for(each child u of v)
checknode(u);
}
best : 지금까지 찾은 제일 좋은 해답치.
value(v) : v 노드에서의 해답치.
4.
0-1 knapsack problem
State Space Tree 구축
이렇게 정해놈)
-레벨 k에 있는 (현재) 노드에서 왼쪽가지로 가면 k번째 item을 배낭에 넣는 경우이고, 오른쪽가지로 가면 그 item을 배낭에 넣지 않는 경우이다.
- 루트에서 leaf까지의 모든 경로는 해답후보
- 최적의 해를 찾는 optimization problem이므로 '검색이 완전히 끝나기 전에는 해답을 알 수가 없다.' 따라서 검색 과정에서 항상 그 때까지 찾은 최적의 해를 기억해야 함.
5.
cost
c(x)=현재 루트에서 x까지 올때까지의 cost+x에서 답 노드까지의 min cost
min을 구한다면 approximate cost c'(x)<=C(X) lower bound
max를 구한다면 approximate cost c'(x)>=C(X) upper bound
6.
profit
:루트에서 현재 노드까지 올 때까지 선택한 item의 총이윤.
bound
:profit의 cost
단, 조건이 있음-> 무게가 넘으면 안됨 &
totweight
: i+1부터 k-1까지 담을 때 다 더한 것이
bound
:현재 노드까지의 이윤+물건이 넘치지기 직전(k-1)까지 다 담은 이윤
근데 이렇게 해도 남는 여분이 있을 수 있음
남는 여분은 W-totweight라고 표현할 수 있음. 이 남는 여분만큼 무게를 자름
bound식
7.
maxprofit : 지금까지 찾은 최선의 해답의 총 이윤값
즉, c(x)
- wi와 pi를 각각 i번째 item의 무게와 이윤이라고 하면, pi /wi 의 값이 큰 것부터 내림차순으로 item을 정렬한다. (일종의 탐욕적인 방법이 되는 셈이지만,
알고리즘 자체는 탐욕적인 알고리즘은 아니다.)
- maxprofit := $0; profit := $0; weight := 0
8
깊이 우선, bound 줘서 backtrack방식으로 풀어보기
1. profit, weight 계산.
weight 계산 이유: weight보다 넘치면 더 이상 갈 필요 없기 때문.
profit 계산 이유: 끝까지 계산할텐데 계속 profit을 더 좋은 걸로 업데이트하기 위해
2. bound 계산
3. 현재 주소담은 weight가 무게보다 작아야하고, bound가 maxprofit보다 크면 검색 계속, 아닐시 backtrack
9.
0-1knapsack은 꼭 끝까지 해봐야함.
ex) 물건 4개, 가방 capacity는 16
pi/wi는 무게당 이윤
bound-가방이 찢어지기 직전까지 짜투리까지 생각해서 내가 담을 수 있는 최대치를 말함
깊이 우선이기에 계속 왼쪽으로 감(계속 선택함)
9-21. 해봄
주의해야할 점
트리에서 오른 쪽으로가면 선택안하는 것임.
선택 안된 노드는 bound와 profit에서도 0으로 해야함. 빼야함!
헷갈리지 말기.
bound와 profit 계산할 때 헷갈리지 말기
bound가 max보다 크면 계속 해도 됨. bound가 max보다 작으면 할 필요 없음
가방 찢어지기 전까지 하고 그 다음에 짜투리 하는 거임. 가방 충분히 남아있는데 무조건 마지막 노드 바운드 계산이라고 짜투리 계산하면 안됨! 주의!
22.
똑같은 backtrack인데도 bound를 줘서(branch-and-bound방식이) 훨씬 봐야할 노드가 줄어듦.
O(n제곱)
다이나믹 방법으로 푼다면?
확실하게 대답 불가.
23.
branch-and-bound로 너비우선검색을 해보자.
결론적으로) backtrack보다 별로임.
3번째 방법인 최고우선검색이 제일 좋음
24.
큐를 사용함.
일반적인 너비우선검색 알고리즘
void breadth_first_search(tree T)
{ queue_of_node Q; node u, v;
initialize(Q);
v = root of T;
visit v;
enqueue(Q,v);
while(!empty(Q))
{ dequeue(Q,v);
for(each child u of v){
visit u;
enqueue(Q,u); }
}
}
25.
Branch-and-Bound 너비우선검색 알고리즘
void breadth_first_BranchBound(state_space_tree T, number& best) {
queue_of_node Q;
node u, v;
initialize(Q); // Q는 빈 대기열로 초기화
v = root of T; //루트를 방문
enqueue(Q,v);
maxprofit = profit(v);
while(!empty(Q)) {
dequeue(Q,v);
for(each child u of v) { // 각 자식노드를 방문
if(profit(u) > maxprofit)
maxprofit = profit(u);
if(bound(u) > maxprofit)
enqueue(Q,u);
}
}
}
//깊이와 달리 자식을 다 각각 방문
26-32. 해봄
깊이와 똑같이 bound와 maxprofit을 구하는 방법은 똑같지만 노드를 방문하는 방식이 다름. 자식들/밑에 노드를 다 벌려줘야 함.
bound가 max보다 크면 계속 해도 됨. bound가 max보다 작으면 할 필요 없음
33.
장점) backtrack방식보다 더 넓게 퍼지진 하지만 그만큼 더 깊게 내려가지 않고 빨리 짤림.
but, 깊이 우선보단 좋진 않음.
문제에 따라 달라질수있지만 거의 대부분 깊이우선이 더 좋음
34.
branch-and-bound로 best-first search를 해보자.
제일 좋아보이는 길로 가보자. 가지가 뻗어나가는 순서 없이 그냥 그 상황에 제일 좋아보이는 쪽으로 가면 됨.
어떤 기준으로 좋아보이는 것?
->bound를 보고 결정함.
1. 모든 자식노드를 검색
2. 당연히 non-promising한 건 패스,
3. promising하며 bound가 좋은 노드를 확장
35.
자료구조
뻗어있는 리프 노드의 값들은 heap를 사용
heap구조를 사용해야 훨씬 더 빠르고 효율적이기에 사용.
해볼 가치가 있는 것은 queue에 집어넣음 - 유망한 것들을.
36.
Branch-and-Bound 최고우선검색 알고리즘
void best_first_BranchBound(state_space_tree T, number best) {
priority_queue_of_node PQ; node u,v;
initialize(PQ); // PQ를 빈 대기열로 초기화
v = root of T; maxprofit = profit(v); //시작은 루트부터. //처음 이윤은 0
insert(PQ, v); //v는 현재 노드 //v를 확장한다~라는 의미로 큐에 집어넣음
while(!empty(PQ)) { // 최고 bound가진 노드를 꺼냄.
//프라이어티 큐에서 젤 위에 있는 애 (젤 좋은 애) 를 꺼내와서 시작
remove(PQ, v);
if(bound(V) > maxprofit) //노드의 promising점검.확장 여부 검사
//이 if문에서 bound를 기준으로 promising을 검사한다는 것을 알 수 있음.
for(each child u of V) { //v의 어린이들 u
if(profit(u) > maxprofit)
maxprofit = profit(u);
if(bound(u) > maxprofit)
insert(PQ,u); //아직 자르지 말고 큐에 넣어보자.
//자르지 않겠다 = 큐에 넣겠다=유망하다
}
}
}
*priority queue, heap 다시 설명*
순서대로 뽑는 것이 아닌, 가장 좋은 priority queue.
priority queue는 자료구성을 heap구조로 함.
최댓값이면 max heap, 최솟값이면 min heap.
37-43. 해봄.
계산 방법은 똑같은데 어떤 노드를 선택해서 expand하나가 가장 중요함. 노드가 확장되는 순서는 뒤죽박죽이 될 수 있고, bound가 큰 것들 순서대로 자식 확장하면 됨.
=========================1206필기
추가 6장 노트
6.
traveling saleswoman problem을 branch-and-bound로 풀기
[1,…,k]의 여행경로를 가진 노드의 Bound
= [1,…,k] 경로 상의 총거리
+ vk에서 A에 속한 정점까지의 에지중 최소치
+ 시그마iEA (vi에서 A교집합{v1}-{vi}에 속한 정점까지의 에지중 최소치)
7.
bound 21이 어떻게 나왔나?
각 행마다 가장 적은 것을 합한 것. v1,v2,v3,v4,v5를 더한 것.
이 이상 더 좋은 것은 나타날 수 없음.
8. (6슬라이드 노란색 부분 보면서 파악)
1-2는 기정사실
1에서 3을 가면 4가됨. 여기서 3이 k
나머지 노드 i는 2,4,5.
3에서 i로 가는 길 중 최소치는 5
그래서 5 선택
이제 2,4,5 에서 3을 제외한(k를 제외한) 가장 좋은 것을 찾아보자.
그래서 7, 2, 4가 선택됨
9.
4에서 2,3,5 가는 것중에 최소를 찾자-> 7, 9, 2 중 2를 선택
2, 3, 5 중에 4 제외하고 제일 작은 것을 찾으면 7, 4, 7이 됨
다 더해서 30
11. (파란색 7 부분 아님 그 옆옆의 7임)
지금 bound들이 minlength(무한대)보다 작기 때문에 해볼만 함.
"제일 작은" 22에서 expand하겠다.
1, 3, 2는 바꿀 수 없음.
4,5 정해짐.
2에서 4, 5 가는 것중에 작은 7을 선택
4, 5 에서 3으로 가도 안되고 2로 가도 안됨
그 중에서 작은 것은 2 와 4 임.
12.
4 에서 가는 것중 최소는 7과 2를 가지고 있는 노드 2, 5
그리고 최소치는 값 2
2, 5 에서 3과 4빼고 가는 것들 중 최소는 값 7과 값 7 임.
=> 4 + 7 + 2 + 7 + 7
=> 27
"다 할 때(리프까지 도달할때)까지 minlength는 바꾸면 안됨."
13
39 바운드 구하는 방식 동일
14.
지금 6개의 바운드가 있음
다 큐에 들어가있는데
이 중 뭘 익스펜드할까?
위에루트 쪽은 상관없이 리프들끼리 비교해서 제일 작은 22를 익스펜드 해야겠다!
1, 3, 2, 4 는 안해봐도 됨. 왜냐면 저절로 1, 3, 2, 4, 5, 1이 되기 때문.
//하나의 길이 나옴
37이 마지막.
min length가 37로 업데이트 됨.
다른 자식이 expand됨.
바운드가 31.
minlength가 31로 엄데이트됨.
큐안에 들어있는 애가 바운드 (31, 27, 29, 30, 42) 중 제일 적은 27로 expand됨.
15.
value 43, 34가되는데 minlength 업데이트 할 필요 없음
또 따시 큐에서 제일 작은 바운드 expand해줌.
30을 expand 해줌
똑같이 계속 계산해줌
16.(min length 31임. 30은 오타)
여기서 바운드 30.
min length 업데이트 해도 되나?
no!!!!!!!
끝까지 내려오지 않았기 때문에 최소라고 할 수 없음.
바꾸면 됨
17.
다 내려와서 밸류가 30인 애가 나타남.
minlength 30으로 업데이트 가능
18.
큐에 들어있는 31 과 42 두 개 남음.
31을 expand함
*확장을 하려면 minlength보다 작아야 하는데 큐에 남은 31과 42 보다 작지 않기 때문에(false됨) 해 볼 필요 없음.
19.
minlength보다 커서 힙에서 빠지는 순서
(이게 언제 빠지는지 헷갈리지 않게 알아두기/
:bound 31
bound 38,
bound 39
bound 42
bound 45
순서로 빠짐
왜? minlenght보다 커서. 할 필요 없음
(다른 바운드들, 바운드 22, 30은 31과 42와 달리 숫자가 적기 때문에 먼저 leaf로 내려 가서 minlength까지 업데이트함. 바운드 22와 30 까지 다 한다음에 순서대로 그 다음 작은 바운드인 31을 하려는데 이미 앞에서 minlength가 더 적은 수로 업데이트 했기에 안해도 되는 것임. 그 전에 바운드 30을 뺴버릴 순 없음.
(6장-BandB.pdf-36슬라이드 코드 보면서 해보기)
이 코드 보면서 순서 알아두기.
Comments