냅색 알고리즘은 여러가지 방법으로 해결할 수 있다. 완전탐색, BFS, Bestfit, DP 까지..
1. 완전탐색
가능한 모든 경우의 수를 살펴보는 것이다.
2. 분기한정
분기한정이란, 완전탐색에서 가지치기를 하는 것이라 생각하면 된다. 그러나 가지치기가 탈출조건을 걸어 여러번 탈출하는거라면, 분기한정이란 아직 자식을 확장하기 전에 이 자식이 진짜 '유망'한가를 확인한 다음 유망한 자식들만 확장하는 것이다. 즉, 유망하지 않은 자식은 확장하지 않는다.
그렇다면, 이 자식이 유망한지 안한지를 확인할 수 있는 방법이 있어야하지 않는가? 맞다. 필요하다. 냅색 알고리즘에선 Greedy 방식으로 이 자식이 유망한지를 확인한다.
Greedy 방식으로 냅색 알고리즘이 유망한지 판단하는 방법은 다음과 같다.
물건의 가치를 무게로 나눈다. 그리고 이 결과대로 정렬을 한다. 그리고 처음부터 순서대로 담는다. 이 뜻은 즉, '정답이 될 가치가 높은 놈들을 먼저 담아본다.' 근데 이 Greedy 방식에선 특별한게 하나 더 있다. 원래 냅색의 0-1 방식에서 물건을 쪼개 들 수 없다. 그러나 Greedy로 할 땐 물건을 쪼갠다.
휴리스틱이란 개념인데, 문제의 조건을 느슨하게 풀어 최대한 얻을 수 있는 가치를 크게 만든 다음에 비교해보자. 란 의미의 함수다.
예를 들어, 물건의 가치와 무게가 아래와 같다고 가정해보자
| 물건 | A | B | C | D |
| 가치 | 50 | 65 | 15 | 30 |
| 무게 | 5 | 5 | 1 | 6 |
| 가치/무게 | 10 | 13 | 15 | 5 |
이 물건을 가치/무게로 정렬하면 아래와 같다.
| 물건 | C | B | A | D |
| 가치 | 15 | 65 | 50 | 30 |
| 무게 | 1 | 5 | 5 | 6 |
| 가치/무게 | 15 | 13 | 10 | 5 |
만약 가방이 들 수 있는 최대 무게가 10이다. 그러면 일단 이 '가치/무게'가 높은 물건을 순서대로 담는다.
[C, B] 를 담고 A를 담으려고 보니까 A까지 담으면 총 무게가 11이 된다.
어. 그러면 못담네?
아니다. 유망한지를 확인하는 Greedy 함수는, 정답을 구하려는 문제가 아니라 자식이 유망한지? 에 대한 여부를 확인하는 문제다. 따라서, 실질적인 문제보다는 조금 더 느슨한 조건을 사용한다. 어떻게? 물건을 쪼개서라도 담는다.
최대 10까지 들 수 있는 가방에 [C, B]를 담고 남은 무게가 4이니까 A는 4만큼만 담는다. 따라서, 식은 아래와 같다.
- 가방에 넣는 물건 : 무게 1의 C + 무게 5의 B + 무게 4의 A
- 얻을 수 있는 최대 가치 : 15+65+(50*4/5)
A는 무게 5를 다 넣은게 아니라 4키로 만큼의 A만 넣은거니까 그 물건의 가치도 원래 가치의 4/5 만큼만 가진다.
이렇게 하여 휴리스틱 함수를 구했고, 이를 유망한지? 에 대한 여부를 판단하는 척도로 사용할 것이다.
2.1. 분기한정 BFS
트리는 곧 그래프이기 때문에 DFS로도 표현할 수 있고, BFS로도 표현이 가능하다. 둘 다 가능하고 성능도 비슷하다. 우리는 여기서 BFS 방법을 살펴볼 예정인데, 그 이유로는 추후 Bestfit를 배우기 위해선 BFS로 살펴보는 것이 용이하기 때문이다.
냅색 알고리즘은 주어진 무게 내에서 가치를 최대로 만들기 위해 어떤 아이템을 넣을까에 대한 고민이라고 볼 수 있다. 따라서 이 아이템을 넣는 경우와 넣지 않는 경우를 하나의 결정트리로 표현할 수 있다.
자식이 왼쪽으로 뻗을 땐 아이템을 선택하는 것이고, 오른쪽으로 뻗을 땐 선택하지 않는다고 생각해보자. 아래와 같은 트리가 만들어질 수 있다.
우리는 분기한정에 하기 위해 노드에 몇가지 정보를 담아야 한다.
- 현재까지의 가치, 현재까지의 무게, 앞으로 담을 수 있는 최대 가치(유망한 가치)
자, 이제 문제를 보면서 이해를 해보자. 아이템을 가치/무게의 값 순서대로 오름차순 정렬을 한 결과다. 가방에 담을 수 있는 무게는 최대 16이다.
| 아이템 | 1 | 2 | 3 | 4 |
| 가치 | 40 | 30 | 50 | 10 |
| 무게 | 2 | 5 | 10 | 5 |
| 가치/무게 | 20 | 6 | 5 | 2 |
맨 처음의 시작은 아무것도 담지 않는 가방이다. 즉, 초기상태의 가방 안에 담긴 무게는 0, 가치도 0이다.
아무것도 제외한 것도 포함한 것도 없으니 Greedy로 '가치/무게'가 큰 순서대로 담아보자. [1, 2] 까지 담고 3을 담으려고 보니 무게가 2+5+10 = 17로, 담을 수 있는 최대 무게 16을 넘는다. 그러면 아이템 3을 쪼개서 9만큼의 무게만 넣자.
- 가방에 넣는 물건 : 아이템 1번(무게 2) + 아이템 2번(무게 5) + 아이템 3번(무게 9)
- 얻을 수 있는 최대 가치 : 40 + 30 + 50 * (9/10) = 115
그럼 초기상태에 필요한 값은 모두 세팅 되었다. 가치, 무게, 유망한가치 순으로 0, 0, 115 값을 가진다.
그리고 이제 그 다음으로 넘어가서, 아이템 1을 가방에 넣을지 말지를 결정해야 한다.
아이템 1을 넣는 경우, [가치, 무게, 유망한 값]은 [40, 2, 115]다. 여기서 왜 115인지 이해가 안된다면, 위에서 우리가 유망한 가치를 구할 때 넣은 아이템들이 무엇 무엇이었는지 생각해보자.
- 아이템 1 몽땅 + 아이템 2 몽땅 + 아이템 3의 9/10 만큼
아이템 1은 이미 유망한 값에 포함이 되어있기 때문에 이미 계산된 값이다. 그리고 이 노드를 왼쪽 노드로 뻗자.
그리고 끝내기 전! 노드를 한번 살펴보자. 노드의 가치가 40이다. 이는 현재까지 나온 가치 중 가장 높은 가치다. 따라서 현재까지 나온 최대 MAX 값을 40으로 둔다.
그 다음, 해당 노드의 유망한 가치도 살펴본다. 앞으로 이 노드에서 뻗어나간 다면 최대 115라는 가치를 얻을 수도 있다. 이는 현재까지 나온 MAX 값인 40보다 큰 수이니 이 노드는 아직 확장을 시켜볼 만하다.
그럼, 만약 이 가방에 아이템 1을 담지 않는 경우는 어떻게 표현될 수 있을까?
아무것도 담지 않았던 가방에, 아이템 1도 담지 않는다면 현재 가치도 무게도 당연히 [ 0, 0 ]이다.
그럼 유망한 값은 어떻게 될까? 우리는 분명 위에서 유명한 값을 구할 때 (아이템 1몽땅 + 아이템 2 몽땅 + 아이템 3의 9/10 만큼)을 넣었었다.
그러나 아이템 1을 넣지 않을거니까 여기에서도 아이템 1을 빼서 다시 계산을 한다.
(아이템 1몽땅 + 아이템 2 몽땅 + 아이템 3의 9/10 만큼). 아이템 1을 빼니까 아이템 1의 무게였던 2를 담을 필요가 없어진다. 그러면 가방에 넣는 아이템의 가치는 아래와 같아진다.
- 가방에 넣는 물건 : 아이템 2번 (무게 5) + 아이템 3 (무게 10) + 아이템 4 (무게1)
- 얻을 수 있는 최대 가치 : 30 + 50 + 10 * (1/5) = 82
즉, 아이템 1을 넣지 않는 경우의 각 값은 [0 , 0, 82] 라고 표현할 수 있고 이를 오른쪽 트리로 표현한다.
끝내기 전에 노드를 살펴보자. 노드의 가치는 0이다. 이는 MAX 값보다 작으니 MAX는 여전히 40으로 남는다.
또한, 해당 노드의 유망한 가치도 살펴본다. 앞으로 이 노드에서 뻗어나간 다면 최대 82라는 가치를 얻을 수도 있다. 이는 40보다 큰 수이니 이 노드는 아직 확장을 시켜볼 가치가 있다.
자 이제 아이템 2를 선택할지 말지의 여부를 결정해보자.
가장 오른쪽의 노드부터 순서대로 살펴보겠다.
아이템을 1을 선택한 후, 아이템 2를 선택할 경우
- 현재가치 : [40+30]
- 현재무게 : [2+5]
- 유망가치 : [115]
현재가치가 70이다. 이는 현재까지 나온 최대 가치 MAX보다 큰 값이기 때문에 MAX는 70이 된다.
아이템을 1을 선택한 후, 아이템 2를 선택하지 않을 경우
- 현재가치 : [40]
- 현재무게 : [2]
- 유망가치 : [40+50+10*4/5 = 98]
아이템을 1을 선택하지 않은 후, 아이템 1를 선택할 경우
- 현재가치 : [30]
- 현재무게 : [5]
- 유망가치 : [30+50+10*1/5 = 92]
아이템을 1을 선택하지 않은 후, 아이템 2를 선택하지 않을 경우
- 현재가치 : [0]
- 현재무게 : [0]
- 유망가치 : [50+10 = 60]
이걸 주목하자. 현재 이 노드의 유망가치는 60이다. 앞으로 애는 아무리~~~ 노력하고 애쓰려고 해봐도 60 이상의 값은 가질 수 없다. 그러나 현재까지 알려진 값 중 최대 MAX 값은 70이다. 따라서, 이 노드는 아무리 확장을 해봐도 유망하지 않다. 따라서 가지를 쳐버린다.
이런식으로 아이템을 선택할지 말지에 대한 여부에 따라 가지를 확장을 해나가고, 그 여부에 따라 확장 노드에 담는 현재가치, 현재무게, 유망가치를 결정한다. 그리고 확장을 해 나가기 전에 무조건 적으로 "유망가치 > 현재까지 나온 최대가치" 인지를 확인하자. 그렇지 않다면 해당 노드는 탐험하지 않고 잘라버리면 된다.
최종적으로 이 단계를 거치면 아래와 같이 완성된다.
이게 BFS 방식의 분기한정의 개념이다. 이러한 분기한정의 속도를 높이기 위해서 중요한 요인이 두가지가 있다.
- 얼마나 많이 유망하지 않은 가지를 잘라내느냐
- 얼마나 빨리 유망하지 않은 가지를 잘라내느냐
1번 얼마나 많이 유망하지 않은 가지를 잘라내는지에 대한 여부는, 유망가치를 결정하는 함수가 얼마나 잘 짜여졌는지에 따라 달려있다. 2번 얼마나 빨리 유망하지 않은 가지를 잘라내는지에 대한 여부는, 노드를 방문하는 순서에 따라 달려있다.
그러면 이 문제에서 '2번'을 적용하려면 어떡해야 할가? 우선순위 큐를 이용한 방식이 있다.
우선 순위큐를 MaxHeap으로 구현한 다음, 유망가치가 가장 큰 노드부터 방문을 하면 가장 유망한 자식들을 먼저 관찰할 수 있어서 MAX 값을 빠르게 찾아낼 수 있다는 장점이 있다.
BFS 방식으로 문제를 해결했을 때는 총 8번만의 방문을 통해 최대 값을 찾아낼 수 있다.
이번엔 유망한가치가 가장 큰 순서대로 방문을 했을 때의 그림은 아래와 같다.
고작 세번의 차이라고 생각할 수 있지만, 퍼센티지로 따진다면 거의 50% 만큼의 탐색을 더 했다고 생각할 수 있다.
따라서, 어떤 것을 더 먼저 방문하냐에 따라서 분기한정의 속도를 더 빨라지게 할 수 있다는 것을 배웠다 .. !
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
from queue import PrioirtyQueue
class SSTNode:
//하나의 노드 생성 및 초기화
def __init__(self, level, profit, weight):
self.level = level
self.profit = profit
self.weight = weight
self.bound = 0
def bound(u, p, w):
n = len(p) - 1
if(u.weight >= W):
return 0
else:
result = u.profit
j = u.level+1
totweight = u.weight
while(j <= n and totweight + w[j] <= W):
totweight += w[j]
result += p[j]
j+= 1
k = j
if(k<=n):
result += (W - totweight) * p[k] / w[k]
return result
// 냅색 알고리즘(가치, 무게, 총무게제한)
def knapsack (p, w, W):
PQ = PrioirtyQueue()
// maxValue = 현재까지 발견된 모든가치 중 가장 높은 가치
// bound (v,p,w) = 유망가치를 구하는 함수
//초기값 설정
v = SSTNode(0, 0, 0)
maxValue = 0
v.bound = bound(v, p, w)
PQ.put((-v.bound, v))
//본격적으로 탐색트리 만들기 시작함
while(not PQ.empty()):
v = PQ.get()[1]
// 현재 노드의 유망가치 > maxValue면 탐색을 진행
if(v.bound > maxValue):
//이 아이템을 챙겼을 때의 무게가 무게제한에 걸리지 않고, maxValue보다 높다면 maxValue 값 갱신
level = v.level + 1
weight = v.weight+w[level]
profit = v.profit+p[level]
u = SSTNode(level, profit, weight)
if(u.weight <= W and u.profit > maxVelue):
maxValue = u.profit
//이 아이템을 챙겼을 때의 유망가치가 maxValue 보다 높다면, 이 노드의 자식은 탐색해보아야 함
u.bound = bound(u, p, w)
if(u.bound > maxValue):
PQ.put((-u.bound, u))
//이 아이템을 챙기지 않았을 때의 유망가치가 maxValue보다 높다면, 이 노드의 자식은 탐색해보아야 함
u = SSTNode(level, v.profit, v.weight)
u.bound = bound(u, p, w)
if(u.bound > maxVlue):
PQ.put((-u.bound, u))
return maxValue;
|
cs |