0-1 Knapsack Problem - 깊이 우선 검색을 사용한 한정분기 (Branch and Bound)

0-1 Knapsack Problem

깊이 우선 검색을 사용한 한정분기 (Branch and Bound)

---

서론

한정 분기 전략의 동기 : 되추적의 비효율되추적의 탐색 과정에서 Valid가 적용되더라도 여전히 상당한 비율의 정점을 방문하지 않아도 됨을 발견

 

되추적의 비효율 해결책 : 각 노드를 방문할 때마다 한계치(bound)를 계산

한계치(Bound) : 해당 노드로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계 값

 

0/1 Knapsack Problem의 깊이 우선 검색을 사용한 한정분기(Branch and Bound) 전략

bound 계산식

1. 그 노드의 profit과 weight를 계산한다.

2. 그 노드의 bound를 계산한다.

3. 현재 노드의 profit이 maxprofit보다 크면 maxprofit 값을 경신한다.

4. (weight < M) && (bound > maxprofit)이면, 유망하다고 보고 가지를 뻗어(Branch) 나간다.

4-1. 즉, 무게가 초과하지 않았고, 향후 가치가 최대 가치보다 큼

4-2. 그렇지 않으면 유망하지 않다고 보고, 되추적(Backtraking)한다.

---

본론

0-1 Knapsack Problem에서 배낭의 한계 무게가 13 (즉 𝑀 = 13)이고, 보석 아이템이 아래 표와 같이 주어질 때, 깊이 우선 검색을 사용한 한정 분기(Branch and Bound)에 대한 상태 공간 트리를 제시하고, 상태 공간 트리 내에서 방문한 전체 노드 수를 비교하시오.

보석 아이템 표

---

우선 하나의 예제를 통해 깊이 우선 탐색의 상태 공간트리 진행 방식을 설명드리고자 합니다.

제가 처음 예제를 보며 궁금했던 점은 어떻게 (1, 2)의 maxprofit = 90 일까? 였습니다.

깊이 우선 탐색이라는 점을 아예 간과하고 문제를 풀었던 것입니다 ㅠ

탐색을 이 순서로 하는게 아니라,

이 순서로 하는겁니다. 너무나도 당연한 소리시죠 다들?

혹여나 저 같으신 분이 있을까 봐 적어드립니다. 죄송합니다..

그래서 (1, 2) 에서 maxprofit = 90 인 이유는 maxprofit 은 전역 변수기 때문에, 탐색을 하면서 계속 갱신됩니다!

줄로 그어놓은 순서대로 보시면 maxprofit 이 계속 새롭게 갱신되는 모습을 볼 수 있습니다.

이러한 이유로 (1, 2) 이후로는 탐색을 안해도 되고, 같은 원리로 탐색 횟수를 줄일 수 있는 겁니다.

---

(0,0)

1) (0,0)에서 profit = 0, weight = 0 이므로, maxprofit = 0입니다.

2) (0,0) 에서 bound 값을 구해보겠습니다.

2 + 5 + 7 = 14 이고, 14 > 13(W의 값)이므로, 3번째 아이템을 취하면 무게의 합이 W를 넘습니다. 따라서 k = 3 이고, totweight 와 bound 는 다음과 같이 계산합니다.

(0, 0) 에서 bound 값

3) (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 0 < 13 ) && ( 80 > 0 ) 즉 조건을 만족하므로, (1, 1)로 방문합니다.

(0,0)에 방문한 그래프 모습

 

(1,1)

1. (1,1)에서 profit = 20, weight = 2 이므로, maxprofit = 20 입니다.

2. (1,1)에서 bound 값을 구해보겠습니다.

2 + 5 + 7 = 14 이고, 14 > 13(W의 값)이므로, 3번째 아이템을 취하면 무게의 합이 W를 넘습니다. 따라서 k = 3 이고,

 totweight 와 bound 는 다음과 같이 계산합니다.

(1, 1) 에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 2 < 13 ) && ( 80 > 20 ) 즉 조건을 만족하므로, (2,1)로 방문합니다.

(1,1)에 방문한 그래프 모습

 

(2,1)

1. (2,1)에서 profit = 50, weight = 7 이므로, maxprofit = 50 입니다.

2. (2,1) 에서 bound 값을 구해보겠습니다.

2 + 5 + 7 = 14 이고, 14 > 13(W의 값)이므로, 3번째 아이템을 취하면 무게의 합이 W를 넘습니다. 따라서 k = 3 이고,

 totweight 와 bound 는 다음과 같이 계산합니다.

(2, 1) 에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 7 < 13 ) && ( 80 > 50 ) 즉 조건을 만족하므로, (3,1)로 방문합니다.

(2,1)에 방문한 그래프 모습

 

(3,1)

1. (3,1)에서 profit = 85, weight = 14 입니다. M = 13 < weight = 14 이므로 무게를 초과하였습니다.

2. weight를 초과하였으므로 maxprofit, bound 를 구하지 않습니다.

3. 다음 가지로 뻗어나가지 않고, (2,1)로 돌아가 다음 순서인 오른쪽 정점 (3,2)를 방문합니다.

(3,1)에 방문한 그래프 모습

 

(3,2)

1. (3,2)에서 profit = 50, weight = 7 이므로, maxprofit = 50 입니다.

2. (3,2) 에서 bound 값을 구해보겠습니다.

2 + 5 + 3 + 1 = 11 입니다. 즉, 3번째 아이템을 제외하고 모든 아이템을 더해도 합이 W를 초과하지 않습니다.

따라서 k=6이고, bound 는 다음과 같이 계산합니다.

이미 끝까지(k=6) 도달하였기 때문에, 가정을 통해 totweight을 구할 필요가 없습니다.

(3, 2) 에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 7 < 13 ) && ( 65 > 50 ) 즉 조건을 만족하므로, (4,1)로 방문합니다.

(3,2)에 방문한 그래프 모습

 

(4,1)

1. (4,1)에서 profit = 62, weight = 10 이므로, maxprofit = 62 입니다.

2. (4,1) 에서 bound 값을 구해보겠습니다.

2 + 5 + 3 + 1 = 11 입니다. 즉, 3번째 아이템을 제외하고 모든 아이템을 더해도 합이 W를 초과하지 않습니다.

따라서 k=6이고, bound 는 다음과 같이 계산합니다.

이미 끝까지(k=6) 도달하였기 때문에, 가정을 통해 totweight을 구할 필요가 없습니다.

(4, 1) 에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 10 < 13 ) && ( 65 > 62 ) 즉 조건을 만족하므로, (5,1)로 방문합니다.

(4,1)에 방문한 그래프 모습

 

(5,1)

1. (5,1)에서 profit = 65, weight = 11 이므로, maxprofit = 65 입니다.

2. (5,1) 에서 bound 값을 구해보겠습니다.

2 + 5 + 3 + 1 = 11 입니다. 즉, 3번째 아이템을 제외하고 모든 아이템을 더해도 합이 W를 초과하지 않습니다.

따라서 k=6이고, j=6이기 때문에 bound 는 profit 과 같습니다.

(5,1)에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 11 < 13 ) && ( 65 == 65 ) 조건을 만족하지 않으므로,

다음 가지로 뻗어나가지 않고, (4,1)로 돌아가 다음 순서인 오른쪽 정점 (5,2)를 방문합니다.

(5,1)에 방문한 그래프 모습

 

(5,2)

1. (5,2)에서 profit = 62, weight = 10 이고, maxprofit 은 (5,1)에서 구한 65입니다. 

2. (5,2) 에서 j=6이기 때문에 bound 는 profit 과 같습니다.

(5,2)에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 10 < 13 ) && ( 62 < 65 ) 조건을 만족하지 않으므로,

다음 가지로 뻗어나가지 않고, (4,1)->(3,2)로 돌아가 다음 순서인 오른쪽 정점 (4,2)를 방문합니다.

(5,2)에 방문한 그래프 모습

 

(4,2)

1. (4,2)에서 profit = 50, weight = 7 이고, maxprofit 은 (5,1)에서 구한 65입니다. 

2. (4,2) 에서 j=6이기 때문에 bound 는 profit 과 같습니다.

(4,2)에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 7 < 13 ) && ( 53 < 65 ) 조건을 만족하지 않으므로,

다음 가지로 뻗어나가지 않고, (3,2)->(2,1)->(1,1)로 돌아가 다음 순서인 오른쪽 정점 (2,2)를 방문합니다.

(4,2)에 방문한 그래프 모습

 

(2,2)

1. (2,2)에서 profit = 20, weight = 2 이고, maxprofit 은 (5,1)에서 구한 65입니다. 

2. (2,2) 에서 bound 는 다음과 같습니다.

(2,2)에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 2 < 13 ) && ( 70 > 65 ) 조건을 만족하므로, (3,3)에 방문합니다.

(2,2)에 방문한 그래프 모습

 

(3,3)

1. (3,3)에서 profit = 55, weight = 9 이고, maxprofit 은 (5,1)에서 구한 65입니다. 

2. (3,3) 에서 bound 는 다음과 같습니다.

(3,3)에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 9 < 13 ) && ( 70 > 65 ) 조건을 만족하므로, (4,3)에 방문합니다.

(3,3)에 방문한 그래프 모습

 

(3,3)

1. (3,3)에서 profit = 55, weight = 9 이고, maxprofit 은 (5,1)에서 구한 65입니다. 

2. (3,3) 에서 bound 는 다음과 같습니다.

(3,3)에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 9 < 13 ) && ( 70 > 65 ) 조건을 만족하므로, (4,3)에 방문합니다.

(3,3)에 방문한 그래프 모습

 

(4,3)

1. (4,3)에서 profit = 67, weight = 12 이고, maxprofit 은 67입니다. 

2. (4,3) 에서 bound 는 다음과 같습니다.

(4,3)에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 12 < 13 ) && ( 70 > 67 ) 조건을 만족하므로, (5,3)에 방문합니다.

(4,3)에 방문한 그래프 모습

 

(5,3)

1. (5,3)에서 profit = 70, weight = 13 이고, maxprofit 은 70입니다. 

2. (5,3) 에서 bound 는 다음과 같습니다.

(5,3)에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 13 = 13 ) && ( 70 = 70 ) 조건을 만족하지 않으므로,

다음 가지로 뻗어나가지 않고, (4,3)로 돌아가 다음 순서인 오른쪽 정점 (5,4)를 방문합니다.

(5,3)에 방문한 그래프 모습

 

(5,4)

1. (5,4)에서 profit = 67, weight = 12 이고, maxprofit 은 (5,3)에서 구한 70입니다. 

2. (5,4) 에서 bound 는 다음과 같습니다.

(5,4)에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 12 < 13 ) && ( 67 < 70 ) 조건을 만족하지 않으므로,

다음 가지로 뻗어나가지 않고, (4,3) -> (3,3)로 돌아가 다음 순서인 오른쪽 정점 (3,4)를 방문합니다.

(5,4)에 방문한 그래프 모습

 

(4,4)

1. (4,4)에서 profit = 55, weight = 9 이고, maxprofit 은 (5,3)에서 구한 70입니다. 

2. (4,4) 에서 bound 는 다음과 같습니다.

(4,4)에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 9 < 13 ) && ( 58 < 70 ) 조건을 만족하지 않으므로,

다음 가지로 뻗어나가지 않고, (3,3) -> (2,2)로 돌아가 다음 순서인 오른쪽 정점 (3,4)를 방문합니다.

(4,4)에 방문한 그래프 모습

 

(3,4)

1. (3,4)에서 profit = 20, weight = 2 이고, maxprofit 은 (5,3)에서 구한 70입니다. 

2. (3,4) 에서 bound 는 다음과 같습니다.

(3,4)에서 bound 값

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 2 < 13 ) && ( 35 < 70 ) 조건을 만족하지 않으므로,

다음 가지로 뻗어나가지 않고, (2,2) -> (1,1) -> (0,0)로 돌아가 다음 순서인 오른쪽 정점 (1,2)를 방문합니다.

(3,4)에 방문한 그래프 모습

 

(1,2)

1. (1,2)에서 profit = 0, weight = 0 이고, maxprofit 은 (5,3)에서 구한 70입니다. 

2. (1,2) 에서 bound 는 다음과 같습니다.

3. (weight < M) && (bound > maxprofit) 이면, 유망하다고 보고 가지를 뻗어나갑니다.

( 0 < 13 ) && ( 69 < 70 ) 조건을 만족하지 않으므로, 다음 가지로 뻗어나가지 않습니다.

---

 

결론

깊이 우선 검색을 사용한 한정 분기(Branch and Bound) 전략을 통해

최종적으로 완성된 상태 공간 트리는 다음과 같습니다.

깊이 우선 탐색을 사용하여 한정 분기 전략을 사용하였을 때, 전체 방문 노드 수는 17개 입니다. 

 

위 방법을 통해 구한 0-1 Knapsack Problem의 최적해는 아이템 1, 3, 4, 5를 가방에 넣는 것이고, 그 때의 가방의 weight는 13이고 profit은 70입니다.

 

깊이 우선 검색을 사용한 한정 분기(Branch and Bound) 전략을 통해 상태 공간 트리의 탐색을 이해하고, 한정 분기의 작동 원리를 깨닫는 시간을 가졌습니다.