Chap 6. Branch and Bound

Branch and Bound
- Backtraking과 같이 state-space tree를 사용한다.
- 트리를 탐색하는 방식에 제한을 두지 않는다.
- 오직 최적화 문제에만 사용된다.

BFS와 Best-First Search를 사용해서 탐색을 진행하는데 이번 포스팅에서는 Best-First Search로 0-1 Knapsack Problem을 해결하는 방식에 대해 작성하도록 하겠습니다.

0-1 Knapsack Problem using Best-First Search

 

Basic Idea

- 노드가 promising한지로 결정하기보다는 bound를 사용해서 다음으로 확장할 노드를 선택

- 노드의 bound로 우선순위가 정해지는 priority queue를 사용

 

1. item을 모두 넣지 않았을 떄, bound 값은 $115이다.

이때, node0만 존재하므로 current best solution은 자동으로 0이 된다.

 

2. item1을 담았을 때와 담지 않았을 때로 노드를 확장한 상태이다.

node1과 node2 각각의 bound를 계산해준다.(bound를 계산하는 방식은 이전 Chap 5. Backtracking에서 설명했다.)

이때, current best solution은 node1값으로 설정되는데 node2의 bound가 current best solution보다 크므로 queue 두 노드 모두 넣어준다.

 

3. node1에서 item2를 담았을 때와 담지 않았을 때로 노드를 확장한 상태이다.

추가된 node3과 node4의 bound를 계산해준다.

node2, node3, node4의 current profit을 비교했을 때, node3의 값이 가장 크므로 current best solution은 $70이 된다.

node2와 node4의 bound가 current best solution보다 크므로 두 노드 모두 탐색 대상으로 queue에 넣어준다.

 

4. 우선순위가 가장 높은 node3을 다음 탐색 대상으로 잡아서 item3을 담았을 때와 담지 않았을 때로 노드를 확장한다.

마찬가지로, 추가된 node5와 node6의 bound를 계산해줘야 하는데 node5의 current weight가 최대 무게인 16보다 무거워져서 탐색 대상이 아니므로 node6의 bound만 구해준다.

node2, node4, node6의 current profit을 비교했을 때, node6의 값이 가장 크므로 current best solution은 $70이 된다.

node2와 node4의 bound가 current best solution보다 크므로 node6만 새로운 탐색 대상으로 queue에 넣어준다.

 

5. 우선순위가 가장 높은 node4를 다음 탐색 대상으로 잡아서 item3을 담았을 때와 담지 않았을 때로 노드를 확장한다.

추가된 node7과 node8의 bound를 계산해준다. 이때, current best solution은 node7의 current profit인 $90이 되는데 node8의 bound가 $90보다 작은 $50이라 탐색 대상이 안된다.(이후 확장되어도 $90보다 커지지 않기 때문에)

node2와 node6의 bound가 current best solution보다 크므로 node7만 새로운 탐색 대상으로 queue에 넣어준다.

 

6. 우선순위가 가장 높은 node4를 다음 탐색 대상으로 잡아서 item4를 담았을 때와 담지 않았을 때로 노드를 확장한다.

node9와 node10의 bound를 구해야하는데 node9의 current weight가 최대 무게인 16보다 무거워져서 탐색 대상이 아니므로 node10의 bound만 구해준다.

이때, current best solution은 $90이 된다. queue에 남아있는 node2와 node6의 bound값이 각각 $80, $82로 current best solution보다 작으므로 해당 노드들로부터 더이상 확장하지 않는다.

 

7. 최종 state-space tree는  위의 사진과 같다.