Knapsack Problem(2) - 근사 알고리즘 적용하기

 

 

○ 이어가는 글

https://kuck-su-labor.tistory.com/61

위 글에서 이어집니다.

 

 

○ 들어가는 글

우리는 이전 글에서 다음과 같은 의문점에 대해서 알아보았습니다.

 

순회 초반에 값을 얻었다면, 굳이 계속 순회할 필요가 있을까? 중간에 멈출 방법이 없을까?

 

그 때문에 순회를 계속 속행해야 하는지에 대한 여부를 우리는 구해야 합니다. 그렇다면 어떻게 이를 구할 수 있을까요?

우선 우리가 생각할 수 있는 것은, 순회 도중 지금까지 구한 가장 큰 가치의 값 V가 있을 때, 앞으로 구할 수 있는 최대 가치 FV가 V보다 작다면 우리는 굳이 순회를 돌 필요가 없습니다. 왜냐하면 어차피 돌아도 V보다 큰 값은 나올 수 없기 때문에, 순회를 계속해도 V의 값은 변함이 없을 겁니다.

결국 V는 지금까지 구한 값중  가장 큰 가치,  FV는 앞으로 구할 수 있는 가장 큰 가치. 만약 V>FV라면 더 이상 보다 큰 값이 나올 수는 없으므로 순회를 그만 두어도 된다. 

우리는 이전 글에서 다음과 같은 의문점에 대해서 알아보았습니다.



순회 초반에 값을 얻었다면, 굳이 계속 순회할 필요가 있을까?

중간에 멈출 방법이 없을까?



그 때문에 순회를 계속 속행해야 하는지에 대한 여부를 우리는 구해야 합니다. 그렇다면 어떻게 이를 구할 수 있을까요?

우선 우리가 생각할 수 있는 것은, 순회 도중 지금까지 구한 가장 큰 가치의 값 V가 있을 때, 앞으로 구할 수 있는 최대 가치 FV가 V보다 작다면 우리는 굳이 순회를 돌 필요가 없습니다. 왜냐하면 어차피 돌아도 V보다 큰 값은 나올 수 없기 때문에, 순회를 계속해도 V의 값은 변함이 없을 겁니다.

 

 

○ 근사 알고리즘으로 구현하는 knapsack

탐욕 알고리즘(1 - greedy 알고리즘 소개)

저번 글 이야기를 다시 해 보면, greedy 알고리즘이 항상 해를 반환해 주지는 않는 특징을 활용한 것이 근사 알고리즘이라는 것을 Greedy알고리즘 글에서 다룬 적이 있습니다. 정확한 해는 아니지만 어느정도의 근사값을 구할 수 있기 때문에 알고리즘을 개선하는데 사용하기도 합니다. 이러한 근사 알고리즘을 활용하면 근사값을 구할 수 있을 것이며, 이 근사값을 통해서 알고리즘을 개선할 것입니다. 

다시 문제로 돌아가서 생각해 봅시다. 만약 우리가 Greedy알고리즘으로 knapsack알고리즘을 구현한다면 어떨까요? 아마 가성비가 큰 순서대로 가방에 넣는다면 어쩌면 가방에 최대의 가치의 합이 되도록 담을 수도 있을지도 모릅니다. 하지만 우리는 알 것입니다. greedy 알고리즘이 항상 해를 반환해 주지는 않는다는 것을 말이죠.

가치를 무게로 나누어 1무게당의 가충치를 구하고, 가중치가 높은 순, 즉 가성비가 높은데로 정렬하였다. 

만약 나머지의 항목을 쪼개서 담는다면 어떨까요? 물론 규칙 위반입니다.. 문제의 조건에 맞지는 않습니다. 나누어서 담는다니요. 하지만 이렇게 한다면 적어도 우리가 담을 수 있는 최대의 값 이상이 나올 겁니다.

실제로 가방안에 넣는다고 했을때, 딱 맡게 넣는 경우는 있을지라도 공간을 넘게 넣을 수는 없어서 보통은 남는 공간이 생기기 마련이다. 우리는 이 남는 공간에 쪼개 넣음으로 극한까지 최대값을 만들어 본다. 적어도 이를 넘게 담는 방법은 없을 것이다. 

본래 가방에 물건을 넣을 때는 대부분의 경우 공간이 남습니다. 이를 억지로 분리해서 가방에 넣었다는 말은(그것도 가성비가 큰 순서대로!) 적어도 이 이상 더 담아서 최대 가치를 만들 수 있는 방법은 없다는 말입니다. 때문에 이렇게 항목을 분리해서 가방에 넣는 방법은 비록 knapsack알고리즘의 해는 될 수 없지만, 순회를 계속할지 판단할 수 있는 지표가 될 것입니다.

이것이 Greedy알고리즘을 근사알고리즘으로 활용하는 방법이며, 동시에 알고리즘의 연산을 줄임으로써 알고리즘의 비용을 줄이는 방법입니다. 이를 통해서 알고리즘을 개선하는 것이 가능합니다. 

이로써 요소만 알면, 적어도 극한까지 담을 수 있는 방법을 구할 수 있는 것이다. 

 

○ 알고리즘의 구성

그렇다면 우리는 이렇게 할 수 있을 것입니다.

1. 기본적으로 알고리즘은 재귀를 이용한 완전탐색을 사용합니다.

2. 이를 통해서 한 번의 노드 탐색이 끝나고, 최대로 담을 수 있는 V값을(한 번의 순회로 얻어진) 구합니다.

3. 다음 순회를 진행할지 결정하는 지표 FV를 구합니다. 이는 가성비대로 선택, 남는 공간은 분할하여 최대로 담아 얻어진, 순회로 얻을 수 있는 최대의 예상 값입니다.

4. V와 FV를 비교하여 만약 FV가 V의 값보다 작다면 ( FV < V ) 앞으로의 순회에서 FV보다 큰 값이 나올 확률이 없으므로 순회를 종료하고 V를 해로 선정합니다.

5. V와 FV를 비교하여 만약 FV가 V의 값보다 크다면 ( FV > V ) 앞으로의 순회에서 기존의 V보다 더 큰 값이 나올 수 있으므로 순회를 계속합니다. (2번으로 돌아갑니다.)

 

결국 핵심은 지금까지 구한 부분, 앞으로 남은 부분으로 나누어서, 각 부분의 최댓값을 구하고 비교해서 계속 순회를 진행할지 결정하는 것이다.  

 

 

 

 

 

다음 글에서 이어집니다....

 

 

ps. 

저번주에 올리지 못했었습니다. ㅠㅠ 펑크가 났네요,,

우선 이번주에 저번주꺼까지 해서 2개를 올리도록 하겠습니다 

 

참고: 

www.youtube.com/watch?v=H4UPhyhDyJk&list=LL&index=45