breadth first search with branch and bound pruning for 0-1 knapsack problem
W=16인 이 트리구조가 어떻게 나온건지 알아보자.
먼저 value값은 실제적으로 넣은 값을 넣어준다. 반면 bound 값은 현재 노드 상황에서 Item들을 쪼갤 수는 없지만 무게에 맞춰 쪼개서까지 가방에 넣을수 있다고 했을때의 최대 가치 값이다. 이걸 기억하면서 접근해보자.
- 트리구조의 자식중 왼쪽은 Item을 넣었을때, 오른쪽은 넣지 않았을때이다.
- bound > max profit 이라면 promising하고 bound <= max profit nonpromising하다. nonpromising한 경우에는 가지치기를 멈춘다.
생각해보면, nopromising 이라는건 같은 레벨의 max profit보다 bound가 작다는건데 bound라는게 앞으로 최대로 커질수 있는 값이라는 것이기 때문에, 당연히 가지치기를 그만두는게 맞다. - bound 값을 구하는 방법을 쉽게 예를들어보자면, 루트 노드에서는 Item1부터 순서대로 넣는다. Item1,2를 넣으면 profit =70 ,w = 7이다. 여기에는 들어갈 수 있는 무게가 9(16-7)가 남는다. 하지만 Item3은 무게가 10이므로 통째로 넣었을때 무게를 초과해 버린다. 그래서 Item3은 9/10만 넣는다. 따라서 가치도 50*9/10이 되므로
루트노드의 bound는 40+30+50*9/10 = 115가 된다.
4.w(무게)가 16을 넘어가면 bound를 0으로 reset해준다.
5.value값이 이제까지 구한 값중 가장 크고 w < W(16) 이라면 max profit값을 수정해준다.
이제 순서대로 계산을 해보자.
(1,1)
(1,1)은 Item1을 넣었을 경우이다.
이경우에는 40+30+40+30+50*9/10 = 115로 바운드 값을 줄 수 있다.
그리고 1만 넣어주었으므로 value = 40 w = 2이다.
(1,2)
Item1을 넣지 않았을 경우이다.
이때 bound는 Item1을 제외하고 생각해야한다. Item2,3을 합쳐도 w가 15이므로 item4를 무게1 만큼(1*10/5) 집어넣을수 있다.
따라서 30+50+(1*10/5) = 82이다.
(2,1)
Item 1을 넣고 2도 넣었을 경우이다.
1,2를 모두 넣었으므로 (1,1)노드처럼 결국 item3을 w를 9만큼만 넣을 수 있다. 따라서
bound 값이 115가 나오고 실제적으로는 1과 2를 넣었으므로 value는 70 w는 7이다.
이런식으로 순서대로 진행하면 된다.
참고로 BFS는 queue로 구현하기 때문에, 예를들어 (3,2)의 bound가 80이고, (3,3)의 maxprofit이 90이기 때문에 (3,2)가 분기하면 안되는거 아닌가 하겠지만, (3,2)는 먼저 일어나서 미래의 일을 예측할수 없다. 따라서 분기는 하고 다음번에 nopromising하게 되어 분기를 멈춘다.
best-first search with branch-and-bound pruning
위에 breadth-first search처럼 기본작동방식은 같다. 다만, 전체 확장되지 않은 노드 중에서 가장 유망한 즉, bound값이 가장 큰 노드를 확장함으로써 빠르게 결과를 도출할 수 있게 한다.
- (1,1)를 확장한다.(bound가 가장크다.)
- (2,1)를 확장한다.
- (2,2)를 확장한다.
- (3,3)를 확장한다.
