Branch and Bound(분기한정) -(1)The 0-1 Knapsack Problem

• Backtracking과 유사하나
  최적화문제에만 사용
• state-space tree를 사용하여 문제 해결
• backtracking은 거의 dfs로만 탐색
  bracn and bound는 여러가지 방법으로 탐색 가능

 

해결방법

1. 노드가 promising한지 아닌지 결정하기 위해 노드에 bound를 계산한다.

2. bound값이 best값보다 좋지 않으면 선택하지 않는다. 

 

 

 

The 0-1 Knapsack Problem

1. Breadth-First Search로 탐색하기

 

• 최소 횟수를 얻기위해 주로 너비우선탐색 사용
• 큐 사용

 

2. Best-First Search로 탐색하기

• 가장 시간이 적게 걸림
• 다음으로 expand 하기위해 노드를 고를때 bound를 사용
• Max 우선순위 큐 사용
• bound가 큰 순서대로 expand 됨

overweight는 큐에 담지 않음.

현재 노드의 bound가 best solution보다 커야 큐에 담음.

 

큐에서 뺀 노드의 boud가 best solution보다 작으므로 expand 되지 않음

 

<수도 코드>