5/12 알고리즘 - Branch and Bound

여러분들 대면 강의 하는 게 중만 주거우사까지 하면 3주 4주 저쯤 되는 것 같은데 그렇죠 아 하튼 그 기간 동안에 온라인 강의를 통해서 챕터 5까지 이제 진행을 했고 오늘 챕터 6에 대해서 살펴볼 텐데 이 챕터 6은 6장에 있는 내용은 너희 교회에서 다루고 있는 알 볼 때 설계 기법 중에 마지막 챕터의 라고

We have looked at different algorithms and methods of developing the different methods. Divide and count cloud, Dynamic Programming, Gridial Approach, and Backtracking. The third step is the branch and bound.

책에서 마지막으로 다루고 있는 우리는 설계 기법 유형 중에 하나에 대해서 오늘 살펴보도록 하죠

덥나요? 에어컨 켤까요? 더워요?

여기 6장에 브랜치 앤 바운드라는 기법에 대해서 살펴본다고 되어 있는데 브랜치 앤 바운드라는 이 알고리즘의 설계 기법은 어떤 것이냐 정리를 해야 될 텐데 일단 기본적으로 바로 우리가 전장에 5장에서 살펴본 백 트래킹과 유사한 점도 있고 또 조금 다른 점도 있고 그래서 다른 점이 있으니까 또 다른 이름이 붙었을 텐데 이 챕터의 구성이 대부분 전장에서 다룬 것과 그다음장에서 다룬 것들이 나름대로 비슷한 점도 있고 또 좀 다른 점도 있고 그래서 그런 것들을 쭉 이렇게 순서하고

- Mm-hmm.

문서대로 이렇게 살펴봤는데 이 브랜치 앤 바운드라는 거는 전장에서 살펴본 오대에서 살펴본 백 트래킹과 비슷한 점이 있는데 어떤 면에서 비슷하냐면 백 트래킹은 문제를 풀어날 때 어떻게 했어요? 뭘 이용을 했어요? 스페이스 트릭 문제가 풀어지는 과정에서 그 상태, 상태 공간을 트리의 형태로 표현하고 트리를 탐색하는 그런 방식으로 탐색도 기본적으로

Back to First Search를 이용하는 그런 방식으로 문제를 풀어나가는 것이었죠. 그래서 이렇게 상태 공간 Tree, State Space Tree 라는 것을 이용한다는 점에서 Backtracking과 유사해요. 저 닮아있어요. 자, 근데 다른 점은 뭐냐? Backtracking하고 다른 점은 뭐냐? 몇 가지 측면에서 다른데 일단 기본적으로 Backtracking 하는 것은 Search 방식이 상태 공간을 탐색을 하는 방식이 기본적으로 Depth Search, Depth Research였어요.

그래서 이렇게 한 브랜치로 쭉 따라서 가고다가 그 밑으로 내놓을 필요가 없다고 하면 다시 구모로 트리 상에서 구모로 들어와서 다른 브랜치를 가보는 그런 방식, 데프트 포르스를 치죠. 그거를 이용을 하는 그런 방식이었는데 관해서 이 브랜치 앤 바운드라는 것은 그런 특정한 하나의 방식으로 이렇게 고정시켜 놓지는 않는 트리 탐색하는 방식을 하나의 데프트 포르스트,

그런 식으로 하나를 고정시켰지 않는 그 외에 다른 여러가지 방법들이 다 적용이 가능한 그런 탐색 기법을 사용을 한다는 점에서 백트랙과 다른 방식과 또 다른 점이 있는데 이 branch and bound라는 것은 기본적으로 optimization 문제, 즉 최적화 문제 즉 해가 여러 개 있을 수 있을 때 그 중에 제일 좋은 해, 최적의 해를 구하는

이런 용도로 사용하는 알고리즘 설계 방법이에요. Backtracking은 뭐예요? 최적의 해만을 구하는 그런 것이 아니라 있을 수 있는 여러 가지 해들 다 찾는 경우 이런 데 사용할 수 있는 알고리즘이죠. 예를 들어서 N-Quinn's-Prowl에서 N-Quinn을 서로 어택하지 않는 포지션에 갖다 놓는다 라고 했을 때 그거는 뭐 어택하지 않는 포지션이면 어떤 것인지 다 솔루션이 될 수 있고 그런 방법들을 다 찾아내는 설치를 통해서

그런데 사용을 하는, 그래서 솔루션이 여러 개 있을 수 있을 때 그것이 어떤 솔루션이 다른 솔루션보다 좋다 나쁘다라는 것을 판단하기 어려운 경우도 있고 판단할 수 있는 경우도 있겠지만 아무튼 그런 솔루션들을 찾는 데 사용을 하는데 이 branch and bound라는 것은 그 솔루션이 만약에 여러 개가 있다면 그 중에 제일 베스트 솔루션을 찾는 데 목적을 두고 있는 그런 아브리튼 설계 방법이라는 것이죠. 그래서 기본적으로 어떤 특정한 state space tree의 탐색 방법에 국한되지 않는다는 점이

백조에킹과 다르고 또 두 번째로 옵티미제이션 문제에만 적용이 가능한 그런 방식이다 라는 거죠. 옵티미제이션이라는 것은 최적이니까 발견할 수 있는 해의 조건을 만족하는 어떤 해든지 있을 수 있을 텐데 그 중에 제일 좋은 해를 찾고 끝내는 그런 알고리즘이다라는 거예요. 그래서 우리가 앞에서 본 여러 가지 옵티미제이션 문제를 해결하는데 최적화 문제를 해결하는데

브랜치 앤 바운드 알버드면 이제 쓸 수 있다는 거죠. 그래서 여기 브랜치라고 하는 것은 트리에서의 어떤 가지를 따라서 갈 것인지 브랜치를 얘기를 하는 거고 이게 지금 상태 공간 트리 를 사용한다고 했으니까 바운드라는 것은 베스트 솔드 를 찾기 위해서 그리고 찾는 과정에서 효율적으로 모든 공간에 있는 트리에 있는 노드를 다 살펴보고 찾는 것 그런 것은 전수 조사에 해당하는 것이라서 효율성에 측면에서 보면은 의미가 없습니까? 가능하면은

적게 찾으면서도 또 best solution을 또 빨리 찾을 수 있는 그런 방법으로서 이 bound라는 것을 이용을 해요. 그래서 이 branch라는 것, 주위에서의 branch를 얘기하는 거고 bound라는 것, 그리고 최적 해를 찾기 위해서는 값, bound 값이다 라는 거죠. 그래서 bound라는 값을 이용해서 여태까지 찾아 놓은 것이 앞으로 여기 더 찾아보는 것에 비해서 좋냐, 나쁘냐를 따져서 bound 계산을 해서

살펴볼 건지 아닐지 그거를 결정을 계속 반복적으로 해나가는 그런 방식의 알고리즘이 될 텐데 최적화라는 것이 최적의 해니까 이거를 수치 값으로 따졌을 때 최대의 값을 갖는 것이 최적의 해일 수도 있고 또 어떤 문제의 경우에는 최소의 값을 갖는 것이 최적의 값일 수도 있고 뭐 그렇겠죠 그래서 이 bound가 최소 값을 찾는 것을 목표로 하는 그런 알고리즘이냐 최 대 값을 찾는 것을

그러는 알고리즘에 따라서 upper bound, lower bound 이런 것들을 계산을 해서 그래서 upper bound, lower bound라는 것이 문제는 실제 문제 푸는데 어떻게 활용되는지를 문제의 예를 들어서 보도록 하죠. 그래서 branch and bound라는 방식은 여태까지 우리가 배웠던 다른 알고 있는 설계 방법과 마찬가지로 일반적으로 다른 절차들이, 단계들이 있는데 스텝 1 첫 번째 단계는

일단, 기본적으로 탐색을 통해서, 그 상태오프트리에서의 탐색을 통해서 최적의 행을 찾는 방식인데 찾는 과정에서 어떤 노드가, 저 트리에 있는 노드가 프라미싱인지 아닌지를 판단을 하고 그에 따라서 프라미싱하다라면 그 노드부터의 서브트리 를 더 탐색을 하는 그런 일을 하는 거고, 그렇지 않으면

이 밑에서 주위에 있는 노드들, 다른 상태들을 이렇게 쭉 더 찾아보더라도 거기서는 솔루션이 나올, 베스트 솔루션이 나올 가능성이 전혀 없다라고 판단이 된다면 그러면 더 이상 거기 내려가지 않는 그런 방식으로 이 프라미스, 프라미스 이라는 이런 개념을 이용을 해서 이 트리를 탐색을 해요. 이제 크루 프라미스 하냐 안 하느냐 라는 것을 따지는데 이 바운드라는 것을 계산을 해서 확인한다는 거죠. 이 노드에서 밑으로 더 서브 주위로 내려가서 감상을 했을 때 얻을 수 있는 죄

상의 값, 이게 최대가 될 수도 있고 최소가 될 수도 있는데 아무튼 제일 얻을 수 있는 제일 좋은 값이 뭔지 예상의 값을 계산을 하는 것, 그걸 이제 바운드라고 하죠 바운드의 개념은 이 앞에서도 모자리에서도 백트랙을 쓸 때 넵셋 문제 같은 거 해결할 때 바운드까지 따지는 그런 것들을 했었죠 그래서 프라미싱한지 안한지 따질 때 이거 했는데 그런 바운드라는 개념을 여기서 사용을 해요 그래서 바운드라는 거

노드에서 계산되는 값인데 노드를 더 익스팬드를 했을 때 익스팬드를 확장한다는 것은 그 노드로부터 시작하면서 주위를 만들어본다는 그런 탐색을 해본다는 의미일텐데 그 탐색을 했을 때 얻을 수 있는 솔루션의 값, 그렇죠? 예상 값이죠. 예상 값. 그 값을 바운드라고 한다. 바운드가 몇 가지 찾아 나온 솔루션

알고 있는, 찾아 놓은 솔루션에 비해서 베스트 솔루션에 비해서 좋으냐 나쁜 냐에 따라서 이제 더 탐색을 해 볼지 아닌지를 결정해 나가는 방침이다. 그래서 바운드에 대해서 바운드를 계산하는 일 그거를 이제 매번 설치를 할 때마다 가까이 노드에 대해서 해요. 그래서 이 바운드 값이 여태까지 찾아 놓은 베스트 솔루션이죠. 현재까지 탐색을 하는 과정에서 찾아 놓은 현재까지의 제일 중요한 솔루션 보다 더 낫지 않다면 또

밑으로 더 내려가서 탐색을 해 왔을 때 이것보다 더 좋은 솔루션을 얻을 수 있는 가능성이 없다 라고 판단을 된다면 그 노드는 non-promise가다 라는 거죠. promise 하지 않다. best 솔루션을 이 아래에서 노드 아래에서 얻을 가능성이 전혀 없다. 그렇게 판단하고 탐색의 입장에서는 그 노드는 더 이상 밑으로 탐색을 하지 않는 거죠. 그 노드에 대한 확장을 해서 담사하지 않는 그런 일을 하는 거죠.

그래서 어떤 노드가 프러미싱한지 안한지를 판단하는 일들은 앞에 백 트래킹에서도 했었어요. Song of Success에서도 어떤 노드가 프러미싱한지 안한지, 또 5원 램션 문제에서도 프러미싱한지 안한지 다 따져보고 했었죠. 아무튼 그 바운드의 개념이 여기서도 그대로 사용이 된다. 그래서 브랜치 앤 바운드가

옵티미제이션 문제, 최적화의 문제를 해결하는 데 사용될 수 있도록 했는데 최적화의 문제로서 우리가 앞에서 한번 살펴봤던 O원 랩색 문제, 이 문제는 여러 번 등장했죠. 아이템에 profit이 있고 무게가 있는데 그것들을 어떤 제한된 용량에 랩색에 담는다고 했을 때 담아진 것들로부터 취할 수 있는 최대의 이득을 얻고자 하는 문제, 그죠? 용량의학

그 냅세기 용량을 초과하지 않는 범위에서 담을 수 있는 만큼 담아서 취할 수 있는 최대의 이득을 얻는 문제 그러니까 이거는 최적화 문제인데 최대화의 문제죠 얻을 수 있는 이득을 제일 맥시마이자는 최대화하는 문제죠 제일 그런 것을 베스트로 생각하는 그런 것이니까 이때 그 바운드가 어떻게 사용이 되는지 한번 봐야 되겠죠 자 그래서 여기 Branch & Bound가 기본적으로

어떤 유형의 서치 방식이건 적용이 될 수 있다 라고 했는데 breath force건 또 다른 방식은 간에 트리를 탐색하는 방법 또는 breath를 탐색하는 방법에서 쓸 수 있는 그런 탐색 기법들을 다 적용할 수 있는데 우리가 생각할 수 있는 아주 간단한 그 트리의 탐색 방법으로서 breath for search 너비 우선 탐색 혹은 한번 생각해보죠 너비우선탐색을 적용하는데

브랜치 앤 바운드 한 알고리즘인, 그렇죠? 그런 방식입니다. 자, 그래서 이제 O1 랩셋 문제에 적용을 해볼 텐데 우리가 앞에서 사용했던 동일한 예를 가지고 O1 랩셋 문제에 어떤 식으로 이 브랜치 앤 바운드가 이루어지는지 브랜트 버스 설치를 했을 때 그거를 한번 보려고 해요. 그래서 아이템이 4개가 있고 아이템이 주는 프로필, 웨이트, 무게 이렇게 이제 갖고 있겠죠? 그 다음에 이거를

5월 그때 다이나믹 프로그래밍 사정에 성장이었나요. 그리디어 프로치 사정에서. 또 5월 협상 문제는 그리디한 그런 방식으로 쉽게 풀리지 않는다 라고 했었어요. 그렇죠? 그리디한 방식으로 불가능하다는 것은 아니지만 그거를 불가능하다고 증명을 한 사람도 일단은 없고 그게 가능한지 안하는지 사실은 몰라요. 근데 뭐 여태까지 생각해본 것들 가지고는 참 잘 안돼요. 최적이 되요. 잘 보면은.

5번 넵색 문제 말고 이 Fractional 넵색 문제라는 것을 우리가 생각을 정의해 볼 수 있다고 했는데 Fractional 넵색 문제는 뭐였어요? 그 아이템이 1 또는 0 즉 전적으로 전체가 다 들어가거나 아니면은 다 못 들어가거나 이런 상태가 아니라 그 넣을 수 있는 아이템을 남은 그 용량만큼 무게만큼 쪼개가지고 꽉 채워서 넣을 수 있는 그런 방법으로서의 문제라고 생각을 한다면은 그러면은 항상 가능하다면은

넵셉을 꽉 채워서 용량에 딱 맞게 채울 수 있는 방법이 있을 거고 그러면 그것으로부터 얻을 수 있는 최대 이득을 취하려면 어떻게 하면 되냐고 했을 때 단위 무게상 profit 그것이 큰 것부터 이렇게 하나씩 넣어가는 그런 방식으로 해서 어떤 순간에 넣을 수 있는 것은 통째로 다 1만큼 넣고 100% 넣고 이득도 100% 취하고 하는 형태로 하다가 어느 순간

그 단위 무게당 프로필 순서 내려갔다가 어느 순간에 그거를 통째로 넣으려다 보니까 어 이거는 다 안 들어간다 라고 한다면은 최대의 이득을 얻으려면은 그거를 들어갈 만큼만 쪼개가지고 그 프랙션을 넣는 방식으로 해서 그 이득도 프로필 도 그거 들어간 프랙션만큼만 취하도록 저 원래 있는 100% 이득이 아니라 그 프랙션만큼만 취하도록 하면은 그런 방식으로 해서 greedy하게 넣는 식으로 하면

그거는 fractional 랩성 문제에서의 optimal solution을 찾을 수 있다 라고 했죠 그건 대충 명이 가능하다라고 했는데 그래서 여기서 그러면 fractional 랩성 문제에서의 optimal solution 실제 fractional 랩성 문제로 얻을 수 있는 그 이득은 실제로는 o1 랩성 문제로 생각을 하면 취할 수 없는 이득일 수 있죠 부분을 넣는 것이 불가능한 것이 o1 랩성 문제니까 fractional 랩성 문제로 예를 들어서 100만큼의 이득을 이 아이템들을 가지고 넣어서 얻을 수 있다 라고 했을 때 실제로는 o1 랩성 문제로 생각을 해보면 100만큼의 이득을 얻을 수는 없는 경우

보다 적은 것이 최대 값이 되는 그런 경우가 아마 많을 거예요. 그렇죠? 통째로 다 들어가거나 안 들어가거나 한다면 통째로 넣지 못하고 그 다음 들어갈 수 있는 것을 넣는 방식으로 그래서 프로필이 작아지는 그런 식으로 넣을 수밖에 없기 때문에 아니면 다 원하면서도 못 넣거나 실제 프랙셔널 랩션 문제에서 얻을 수 있는 그 테스트 솔루션이 오원 랩션 문제에 얻을 수 있는 그 솔루션보단 항상

크거나 같겠죠 작지는 않을 거예요 그렇죠 크거나 같을 거예요 그래서 그 크거나 같다 라는 그것을 바운드로 이용을 하려고 해요 즉 O1 넵상 문제로서 얻을 수 있는 것이 최대의 값이 뭐 얼마큼이든지 있을 텐데 Fraction of 넵상 문제로 환산을 한다면은 항상 그것보다는 크거나 같을 수 있는 값을 얻는 것이 가능할 수 있기 때문에 그것을 바운드로 생각을 하자 라는 거죠.

그래서 실제 이 매치미제이션 문제에 대해서는 upper bound를 이용을 해요 실제 얻을 수 있는 이득보다 항상 크거나 같은 그런 upper bound 위에서 이렇게 bound하는 그런 값을 바운드로 사용을 한다는 거죠 최대화의 문제에서는 일단 브랫풀 서치라는 것을 어떤 식으로 브랜치의 바운드를 이용을 해서 적용을 할 수 있는지 볼텐데

일단은 전체에 얻을 수 있는 full stay space tree에요. 아이템이 4개가 있을 때 아무것도 없는 첫번째 mt 상태에 비어있는 약속이 비어있는 상태에서 아이템1을 넣는다 안 넣는다. 아이템1의 입장에서 넣거나 빼거나 두가지 상태를 고려를 할 수 있고 아이템1이 일단 들어간 상태면 아이템2에 대해서 넣거나 빼거나 넣거나 빼거나 넣거나 빼거나 그렇죠?

여기까지죠 아이템 2면은 아이템 3에 대해서 또 이것들이 정해졌을 때 너컨을 빼거나 아이템 4에 대해서 너컨을 빼거나 이렇게 해서 데프트 4까지 내려가는 여기 이제 Full State Space Tree가 되겠죠 이 샘플이 주어졌을 때 그러면은 뭐 여기서 베스트 솔루션이 뭐냐 그러면 이제 여기 앱 세게 얼마만큼 이득으로 들어갔는지 그거를 좀 점수 조사를 한다면 여기 다 찾아가지고 베스트 요 동량을 초과하지 않는 범위 내에서 얻을 수 있는 베스트 솔루션을 찾을 수 있을 텐데

요거를 다 이렇게 찾아보지 않고 branch and bound 요거를 이용해서 요거의 일부만 찾아보고도 best solution을 찾을 수 있는 방법을 생각을 해보자 그 과정에서 이제 이 bound라는 걸 이용을 해보자 라는 거죠

그래서 전체 트리가 아까 앞에처럼 있다고 했을 때 이제 루트부터 시작을 할 거예요. 그렇죠? 그럼 루트는 지금 현재 루트 노드의 상태라는 거는 이 세 가지 값으로 정하는데 이거는 맨 처음에 이 노드가 나타내는 랩색의 상태 아이템이 어떤 것이 들어가 있고 안 들어가 있고 그것이 있는 현재 상태에서 취할 수 있는 이득 루트 투 프로필이 첫 번째 값이고 두 번째가 현재 그 아이템들 들어가 있는 아이템들로 취할 수 있는 무게 구성되는 무게

그 다음에 제일 밑에 값은 실제 그 요리에서 이거는 예를 들어서 루트니까 아무것도 안 넣으면 되죠. 그러니까 profit 0일 거고 무게도 0일 텐데 그러면 여기서 아이템 1부터 시작해서 넣을까 말까 결정하고 2 넣을까 말까 결정하고 해가지고 쭉 그런 일을 한다면 얻을 수 있을 것 같은 최대의 이득이 얼마일까? 그걸 한번 생각을 해보는 거죠. 이 아이템들의

그런 값들이 다 지금 있는데 얻을 수 있을 것 같은 최대 이득은 얼마일까 근데 좀 최대 값이라고 했으니까 그거를 보고 바운드 계산을 한 거를 보고 현재까지 찾아 놓은 탐색을 하는 과정에서 찾아 놓은 최대 이득보다 그 바운드가 더 크면은 더 밑에 내려가 보면 내가 여태까지 찾은 것보다 더 큰 값을 얻을지도 모르겠다 라는 희망을 주는 건데 만약에 그것보다 작다, 바운드에 계산한 것이

그렇다면 바운드 그러고 그 값이 바운드라는 것이 아무리 해도 이것보다 크지는 않다는 그런 바운드라면 밑에서 내려가서 얻을 수 있는 게 최대의 값이 요 값인데 예를 들어서 여기 뭐 어떤 다른 현재까지 얻어놓은 그런 값이 105보다 큰 값으로 찾아 놓은 게 있다면 그러면은 뭐 이거는 밑에 요 값을 통해서 밑에 만약에 선을 치를 계속한다면 얻을 수 있을 것 같은

최대의 프로필 값, 이득의 값인데 그런데 그것이 실제에서 찾아온 것보다 더 작다라면 사실은 해 볼 필요가 없는 거죠, 찾아볼 필요가. 그게 확실하다면, 최대의 이득이 이것을 넘어가지 않는다는 것이 확실하다면 찾아볼 필요가 없어요. 왜냐하면 이미 찾아온 것이 여기 밑에 내려가서 막 감사를 다 해서 얻을 수 있는 그 최대의 값보다 더 크니까 굳이 그 일을 할 필요가 없는 거죠.

그래서 이 바운드 값, 이거 지금 175라는 거는 놓아요. 우리 앞에 5장에 5번 납선 문제 100초 이렇게 할 때도 나오듯이 이거 넣고 이거 통째로 들어가고, 용량이 16이니까, 그렇죠? 이거 두 개 다 통째로 들어갈 거고, 이 순서로 했을 때 지금 7만큼 들어가 있는 상태여서 이거를 통째로 넣으려면 아이템 2가 10이라서 통째로 안 들어가죠? 그렇죠? 그래서 통째로 못 넣고 지금 7만큼 넣고 여기서 부분을 그만큼 취하면은

그러면 합이 16이 될 테니까 90% 요거에 10분의 9만큼 프랙션을 취해서 요거에 이득도 무게가 10분의 1만큼 된 거니까 이득도 10분의 9만큼 되도록 이렇게 만들면 그러면 40 더하기 30 더하기 50 곱하기 10분의 9 쭉 45 이렇게 해가지고 그 값이 3개 더한 값이 15로 나오죠 요 값이었어요. 그렇죠? 5장에 여러분들도 생각을 해보면은 그래서 노드 zero, 거주금 경우 이렇게 계산한 건 그래서 115가 나온다. 즉 아무것도 안 나온 상태에 맨 처음에

그 부분에 대해서 바운드를 계산하면 그 노드는 바운드 값이 프랙셔널 랩셋 문제로 만들었을 때 취할 수 있는 최대의 이득 요거를 지금 바운드 값으로 삼았는데 115죠. 그렇죠? 그러면 5원 랩셋으로 했을 때는 분명히 이거보다는 큰 값은 얻을 수는 없을 거예요. 요거보다 작으면 작았지, 작거나 같을 테니까 요거보다 더 큰 값을 얻지는 못하겠다 그런 것을 빌려주는 거죠. 일단 지금 이거는 현재 상태에서 찾아온 best solution

뭐예요? 아이템이 아무것도 안 들어간 상태니까 zero죠. zero. 여태까지 얻을 수 있는 최대의 기준 찾아온 거는 zero예요. 지금 현재 아무것도 안 들어간 상태고 하나로 볼 수 있는 거죠. 그래서 zero라는 값보다 115라는 바운드 값이 크니까 오케이. 위트는 더 내려가 보면 0보다는 큰 어떤 profit을 취할 수 있을지도 모르겠다. 희망이 생기는 그런 노드의 즉, promising한 노드가 되는 거죠. 그래서 이제 promising하니까 서브 줄이를 좀 탐색을 더 할 수 있도록

노드에서 노드를 확장을 하는, 익스팬드를 하는 그런 일은 하겠죠. 그러면 익스팬드를 하기 위해서 큐에다가 이렇게 넣어주자. breathful search로 탐색을 하기 위해서. 그렇죠? 자 그러면 이제 이것이 큐에 들어가 있는 상태에서 큐가 엠티가 아니니까 거기서 또 하나씩 빼가지고 그 높이를 빼가지고 차일드를 만들어 보는 거죠. 이거에 왼쪽 차에, 즉 이건 아무것도 안 넣은 상태니까

첫 번째로 아이템 1, 여기 아이템 1이라는 건 뭐예요? 단위 무게당 플라핏이 제일 큰 것이에요. 그래서 실제로 여기 아이템이 이렇게 4개가 있을 때 여기는 지금 얘 아이템 1이 단위 무게당 플라핏이 제일 크고 아이템 2가 그 다음이고 3가 그 다음이고 그래서 쭉 순서대로 단위 무게당 이득이 큰 순서대로 이렇게 큰 것부터 나아야 되어 있는 그런 형태인데 만약에 아이템 1, 2, 3, 4가 단위 무게당 플라핏을 따졌을 때 이 순서가 아니다.

아이템이 1이 세 번째로 단위 무게당 플라스틱이 크고 이랬다면 사실은 솔트를 해야 돼요. 그래서 아이템 1이라는 것이 제일 단위 무게가 큰 것이 되도록. 그 순서가 어긋난 상태로 예를 들어서 6이 먼저 있고 20이 있고 2가 있고 5가 있고 이런 순서대로 아이템 1도 있고 그냥 첫 번째 고려하고 이런 식으로 하면 이 알고리즘은 제대로 결과를 얻어주지는 못해요. 항상 보장이 되세요.

아이템 1, 2, 3, 4가 이 단위 무게단 프로필의 입장에서 이 순서가 아니면 아이템 1이 제일 크고 2가 부담되고 아니면은 실제 솔트를 해서 아이템 1이 이게 제일 큰 것이 오도록 그렇게 만들어야 된다. 그게 이제 전제가 되어 있어요. 그 장립이 알고 있는 자체가 동작을 하니까. 자 그래서 이제 이거에 대해서 일단 아이템 1 단위 무게단 프로필이 제일 큰 것부터 생각해서 데테고를 넘는 경우

왼쪽이고 안 넣는 경우 아무것도 없는데 아이템 5를 넣을까 말까 중에 안 넣기로 결정한 상태라면 뭐 이거랑 똑같겠죠 똑같은 상태겠죠 자 근데 지금 요거 이제 세 가지가 좀 두 밑에 있는 노드 상에서는 요 세 가지 값 가지고 상태를 표현한 노드의 상태를 표현하는 건데 이거는 지금 노드 원이라는 거는 아이템 1이 40이라는 프라패트를 주는 건데 이라는 무게를 갖는 거고 그거는 넣기로 결정한 상태죠 그래서 아이템 1이 랩속에 들어와 있는 상태예요

그쵸? 자 그러면은 요거 넣은 상태에서 이제 2, 3, 4를 어떤 식으로 넣느냐에 따라서 앞으로도 이득이 얼마만큼 현재 상태보다는 더 커질 수 있을지 결정이 될 텐데 이거는 지금 아이템 몇 개밖에 없다면 다 세어볼 수 있겠지만 다 따져볼 수 있겠지만 사실은 아이템이 굉장히 많은 경우에는 그거 따지는 것이 쉽지 않은 일이었기 때문에 이렇게 Fraction of Exit 값을 바운드로 사용을 한다면 115라는 값 똑같이 보급하고 똑같이 나오겠죠 이거 따질 때 아까 아이템 1이 들어간 상태로 해서 따지는 거였으니까 보급으로 될 거고

이 노드2라는 것은 아이템1을 보려를 했으나 안 넣기로 결정한 상태에서 안 넣기로 결정한 상태를 나타내는 거죠. 그러니까 사실은 비어있는 그대로 안 들어가 있는 원이 안 들어가 있는 상황이고 여기 노드와 다른 점은 뭐냐? 이제 아이템1을 이거는 넣기로 결정을 해서 실제 얻을 수 있는 fractional laps에 의해서 얻을 수 있는 가시였는데 이거는 이미 안 넣기로 결정을 한 상황에서 이제 나머지 2, 3, 4만 얻느냐 마느냐를 결정을 해야 되는 그런 상황에서 얻을 수 있는

최대 이득이에요. 그렇죠? 그러니까 그것하고는 달라지겠죠. 이거는 아이템 1을 들어가 있는 상태로 계산한 거고 이거는 5를 빼고 나머지 가지고 얻을 수 있는 최대 이득을 계산해야 되는 거니까 그래서 노드 1에 대해서는 아까 한 것처럼 똑같이 115라는 값이 이제 40은 실제 넣은 상태가 됐고 나머지 2, 풀로 놓고 3도 아까 한 것처럼 10분에 9만 넣고 다른 식으로 115, 이거와 똑같은 것은 없고 이거의 경우에는 노드 2의 경우에는 노드 1, 아이템 1으로부터 취할 수 있는 이득은 0이 되는 거니까 안 넣기 됐으니까 나머지 가지고 얻을 수 있는 최대 이득 따져보면 82

이렇게 남았다. 그쵸? 이 경우에는 이제 요거를 넣고 요거를 다 넣고 그럼 15만큼 되니까 1만큼 남은 공간에서 5분이 1만큼 되니까 이런 식이죠. 그래서 80이라는 값. 그래서 왼쪽 차이드는 항상 이 마운드 입장에서 똑같은 값을 가질 것 같고 오른쪽은 이거랑 값은 같은데 그 아이템을 안 넣기라고 보니까 마운드는 달라지고 그렇겠죠. 자 이거 이제 첫 번째

왼쪽 차이드를 생각을 했을 때 지금 이것까지 생각을 했을 때 이건 아직 지금 오른쪽은 안 만들었다고 하고 또는 고려를 안 했다고 하고 이것까지 생각했을 때 현재까지의 베스트 솔루션은 뭐예요? 찾아 놓은 베스트 솔루션 42죠 또 현재까지 이만큼 탄석하는 과정에서 알고 있는 최대의 지금 찾아 놓은 최대의 이득 값이에요 화이트하고는 하나 더 오므로 해서 얻을 수 있는 저거 밖에 찾아보지 않았습니까? 그게 지금 현재까지 알고 있는 최대의 이득이에요

탐색해보고 중에는 제일 좋은 거. 그렇죠. 또는 0이고 0이고는 가시니까 더 좋은 솔루션 있죠. 분명히. 근데 여기 바운드가 115니까 어? 여기에서 멈췄으면 40만으로 끝나는 건데 밑에서 더 탐색해보면 115까지도 얻을 수 있을 것 같으네. 라는 희망을 주는 프라미싱하다. 그렇죠? 라는 거죠. 위험하다. 밑으로 내려가 보면 혹시 이게 이거보다 더 커지진 못하겠지만 아무튼 이거에 근접한 어떤 값을 얻을 수 있을지 모르겠는데 그 값은 이거보다는 크다. 그러니까.

가지고 올 가능성이 필요가 있다는 것이죠. 여기서 좀 더 솔리션이 안 나온다라고 판단하기는 불가능한 어려운 그런 것이에요. 그 다음에 이것도 이제 이거 그러면 오케이. 그러면 이것도 랜적 소프트 리 더 탐색을 해 봐야 되니까 그럼 Q에 일단 들어가 있으나 블랙풀스 스우치를 지금 탐색하니까 노란 색깔로 표시를 해 놓은 게 Q에 들어간다는 그런 의미고 블랙풀스 스우치 방식으로 탐색을 할 수 있게 하기 위해서 그 다음에 이것도 따져보면

이거는 지금 40이라는 것이 베스트 솔루션으로 현재까지 발견된 상황에서 또 이거 계산해보니까 이거 자체로서는 그거보다는 더 못하지만은 40보다는 못하지만 밑으로 더 내려가보면 80이라는 값까지도 얻을 가능성은 있다 그렇죠? 그런 거니까 아 그러면 80이라는 값이 40보다는 크니까 그쪽으로 탐승을 한번 더 해볼 필요는 있겠다 여기서 40보다 더 높은 것을 얻을 수 없어라는 것이

확실한 그런 상황은 아니니까 그것을 얻을 가능성은 있으니까 오케이 이것도 탐색을 써보기로 만들어서 탐색을 더 해볼 필요가 있겠다 확장을 해볼 수 있겠다 라는 거죠 그래서 이렇게 두 개가 다 이제 Q에 삽입이 돼요 이거는 Q에 있다가 빠져나온 거고 Child를 두 개 만들면서 Child가 각각의 bound가 현재까지 찾아온 best solution보다 좋으냐 나쁘냐에 따라서 Q에 들어가서 두 자식들을 더 만들어볼지 즉 여기 두 개를 더 확장을 해볼지

이는 아는거죠. 그래서 여태까지 하여튼 끝까지 찾았을 때 지금 현재 요거 아이템 1으로 하나만 들어가서 얻을 수 있는 요 이득이 현재까지 찾아온 최대의 최대의 이득이에요. 현재 살펴본 것 중에서는 제일 제일 좋은 이소를 줄 것. 둘 다 밑으로 더 내려가면 그것보다 큰 이득을 줄 가능성이 지금 그것보다 크니까 또 탐색을 더 해보자는 거죠. 그 탐색을 브라이드 프로 슬치 방식으로 하기 위해서 Q라는 걸 이용하는 거고요.

그러면 여기 두 개가 들어가 있는데 규호에 여기가 먼저 들어왔으니까 이거를 또 브라이트 플러스로 치니까 확장을 하겠죠. 자식을 왼쪽으로 있죠. 이거 입장에서는 아이템 1까지는 넣는 걸 해놨는데 아이템 2를 넣을 거냐 넣을 거냐. 왼쪽 오른쪽 잘 들어서 이렇게 하는 거죠. 그러면 왼쪽 아이템 2를 통제로 다 지금 이만큼만 찾으니까 7이라는 무게 다 통제로 들어가더라도 16보다 작으니까 거기다 통제로 넣어서 얻을 수 있죠. 그래서 아이템 1, 2가 둘 다 들어가 있는 상황.

그 때 얻는 이득은 70이에요. 1+2 아이템 두 개로 얻을 수 있는 이 이득. 그리고 이 프라프트에 대한 밑으로 더 내려갔을 때 얻을 수 있는 최대 이득이 뭐냐? 바운드 계산하면 이거랑 똑같죠. 1, 2 그대로 100% 들여갔고 3를 또 통제로 못 넣으니까 10분의 5만큼 넣고 해서 얻을 수 있는 이득이에요. 그러면 115가 이 70이라는 현재까지 차단은 스포로우션 보다 크니까 오케이 이것도 밑에

더 내려가서 탐색해보면 70보다 더 좋은 값이 얻어질 수 있겠구나 라고 해서 또 브랫폴스를 치러 오다 확장할 수 있기 위해서 주에다가 넣는거죠 그 다음에 또 요거 보니까 요거는 40이지만 요거 바운드 계산했을때 98이니까 아이템 2를 1만 넣은 상태에서 2는 안 넣기로 결정하는 그 상황에서 바운드 계산해보면 5는 98로 나와요 이렇게 계산 되는거죠 2는 안 넣고 5는 지금 입이 들어간 상태고

그러면 통째로 들어갈 수 있을 거고 4는 또 5분에 4만큼 들어갈 거고 그렇죠? 그래서 전체에 16이라는 것을 딱 맞게 넣을 수가 있겠죠 그러면 98이에요 자 그러면 이 98도 여태까지 찾아 나온 뱃서 솔로즈 역과에 탐색하면서 찾아 넣은 그것보다는 크니까 어? 이거보다 더 큰가 없어져요 혹시 내려가 놓을 수도 있을지 모르겠네 희망 우주는 모두죠 스프러스 해서 큐에 넣었죠 그렇죠? 자 그러면 이제 여기 depth 0, 1, 2에 2에서 왼쪽 두 개 이렇게 한 거고 그 다음에

또 요거에 Child 두개를 만들어서 다섯 해보는거죠. 자 그러면 이제 여기서 Item1을 안 넣기로 한 상황에서 2를 넣느냐 마느냐. 두가지 갈래가 있으니까. 브랜치가 있으니까. 그거를 왼쪽 오른쪽 Child를 하면은 또 똑같이 계산할 수 있겠죠. 이제 안 들어간 상태에서 2만 들어가서 얻을 수 있는 30 무게 5억 또 profit 82도 거랑 똑같이 된다고 했고

2마저 아이템 1도 안 넣었는데 2마저 안 넣겠다고 결정을 했으면 그러면 이제 나머지 얻을 수 있는 최대의 이득은 3하고 4에서 얻을 수 있는 최대의 프랙셔널 랩스에서의 최대의 이득이죠 60의 경우 3, 4를 통째로 다 넣어도 15니까 16보다 작으니까 50 더하고 10해서 60이죠 자 그러면 일단 보면은 이거 이렇게 계산한다는 거고 80이라는 값이 지금 현재까지 얻어놓은 베스트 솔루션 이렇게까지 탐색하면서 베스트 솔루션 요거까지 다 고려해서

70보다 크죠. 그러니까 이쪽에서 더 탐색을 진행을 한다면 혹시 70보다 더 큰 소루션을 쓸지도 모르겠다. 찾을 수 있을지도 모르겠다는 희망을 해주는 프라미스이라는 노트죠. 그래서 오케이. 그러면은 Q에 들어가서 탐색이 더 진행될 수 있도록 나중에 차일드 만들어 볼 수 있도록 해준다. 그런데 이거를 보니까 바운드가 60이에요. 그런데 60은 뭐예요. 이미

찾아 나온 베스트 솔루션, 현재까지 찾아 나온 베스트 솔루션 70보다도 작아요. 그렇죠? 흑십이라는 게 여기 밑에서 내려가서 얻을 수 있는 최대의 이득인데 그렇죠? 그거를 실제로 얻을지도 모르면 그거보다는 더 적거나 같은 그런 것일 텐데 아무튼 그 최대 이득이 이것만 좀 못하니까, 더 작으니까 사실은 여기 밑에서 뭐 일을 더 탐색을 해서 일을 할 필요가 없는 거죠. 이미 여기서 더 좋은 게 있는데 굳이 더 적은 것을 찾기 위해서 확장하고 탐색하고

전혀 불필요하다. 그러니까 프라미싱하지 않는 거죠. 이것보다 더 솔루션을 줄 수 있다는 보장이 없는 노제. 즉 탐색을 안 해봐도 되는 것이죠. 그래서 레벌에서는 이것들만 Q에 들어가게 되겠죠. 만들어진 자식들 중에 현재까지 찾아 놓은 솔루션보다 좋으냐, 좋으냐, 좋으냐, 나쁘냐에 따라서 따라서 좀

들어갈건지 말건지 귀에 넣을건지 말건지 즉 그 노드를 더 확장하는 일을 해볼건지 말건지를 결정하는데 이렇게 좋은 것들만 넣죠. 현재까지 차단으로 베스트 솔루션 보다 더 좋은 것들만 넣었을 때 이렇게 3,4,5라고 본다면은 그것들이 들어가 있는 상태가 되고 현재까지 차단으로 단계까지 끝났을 때 현재까지 찾아온 베스트 솔루션은 70입니다. 그렇죠? 그래서 아직 다 70보다 더 큰 것들이 이렇게 들어가 있는 거니까 그거를 또

실제 작만 이것에 가까운 값들을 저 실수보다 큰 값이 있는 값들을 볼 수 있는지 보는 거죠 그러면 여기 드라이큐에 3개 들어있으니까 그중에 맨 첫 번째 들어있던 이것을 브라이트 프로젝트에 치니까 또 꺼내서 자식을 또 만드는 거죠 확장을 해요 그것들을 익스팬드를 하죠 이건 그래서 현재 이 상태가 여기까지 레벨 2까지 탐색이 진행된 상태고 노드 요 3개가 큐에 들어있는 상황이에요 그렇죠? 그리고 현재까지까지 솔루션이 70이고

그러면 이제 이것을 꺼내서 자식을 또 Q에서 제거한 다음에 자식부터 만들어주는 거예요 아이템 1, 2를 고려한 것이었으니까 3를 1, 2가 어떤 식으로 들어있든지 결정이 된 상황에서 3를 넣느냐 맞느냐예요 그러면 이거는 아이템 1 들어가 있고 2도 들어가 있고 3도 통째로 다 넣은 상황에 앱셋을 얘기를 하는 건데

그러면 뭐 그냥 세 개가 통째로 다 들어간다는 120이 되겠죠. 40, 70 해가지고 그 다음에 얻을 수 있는 그 이득, 그렇죠? 50까지 더해서 120이 될 텐데 근데 그거는 무게가 17이 되죠. 이 세 개, 처음에 세 개를 그대로 다 넣는다고 하면 17이에요. 근데 그거는 내 세계의 역량을 초과하는 거니까 실제로 이 120이라는 이 이득은 취할 수 없는, 실현 불가능한 이득이죠 그렇죠 여기 있어요

현재까지 찾아온 제일 좋은 솔루션보다는 크긴 하지만 요 조건 때문에 솔루션이 되지는 못해요. 그렇죠? 오버웨이트니까. 그래서 요거는 더 좋은 솔루션이라고 볼 수 없는 거죠. 솔루션 자체가 안 되는 거니까. 요거는 안 되고. 즉, non-promise입니다. 그렇죠? 그래서 1, 2, 3 해서 이제 4를 넣을까 말까 만약에 더 확장을 한다면 그거 고려할 수 있을 텐데 이미 오버레이트니까 저 바운드가 0

좀 내려가고 있잖아. 조금 순이 안 된다. 이거는 안 들어가겠죠. 그 다음에 그러면은 아이템 3를 안 넣기로 결정을 하는 경우 그럼 이제 1, 2는 들어갔는데 통째로 다 들어갔는데 안 넣기로 결정하는 게 보니까 뭐요? 70, 이거 그대로 순이지만 이 바운드가 이제 바뀌겠죠. 3가 안 들어간 상태로 해석해서 해야 되는 바운드니까 - 저 사람? - 저거.

그리고 오버워이트 되는 거 그거는 뭐 참여하고 그 다음에 이거 줄이를 안 넣게 됐으면 그거에 대한 이득은 0일 테니까 4를 넣는 경우로까지 따져가지고 얻을 수 있는 4이득 80배 그러면 이것도 아직까지 찾아온 베스트 솔루션 요구보다는 큰 값이니까 오케이 밑으로 내려온 혹시 80을 얻을지도 모르겠다 80에 가까운 값을 그런 거니까 이거는 또 확장할 필요가 있으니까 규에다가 넣어두자

그 다음에 몇가지 했고 또 이거 2개 남았으니까 이거 권해서 또 왼쪽 오른쪽 차이등 아이템 3를 넣을 거냐 안 거냐 하는 거죠. 아이템 3를 이 경우 넣기로 결정한 왼쪽 브랜치를 생각을 해보면 그럼 뭐예요. 여기에서 아이템 3가 통째로 들어가는 경우죠. 이만큼 있었으니까 10이라는 무게를 갖는 거를 넣으면 무게의 10이 프로필이 50 더해지니까 사회에서 쏘고 싶다는 90, 그렇죠?

그러면 이것이 여태까지 찾아온 베스트 솔루션이에요. 이것은 70이었는데 이것은 실현 가능한 솔루션이죠. 이미 이렇게 넣기로 했으면 이렇게 된다는 걸 알았으니까 그러면 베스트 솔루션이 70에서 90으로 업데이트가 되어야 될 거고 현재 여기까지 할 때는 70보다 큰 값이면 들어갔는데 이제는 90으로 업데이트가 됐으니까 여기 보는 중간에 그거보다 바운드가 더 커였지만 아, 이거 밑으로 더 내려가서

필요가 있구나 생각할 수 있는 거고 90에 비해서 큰 바운드인 경우에 넣어요 그래서 이거 98이라는 바운드 값이 나오는데 이런 식으로 대사를 해서 나오는데 90보다 크니까 OK Q에 들어가죠 그래서 여기 똑같이 Q에 70인 상태에서 80이니까 Q에 들어가는 거였고 이거 할 때는 90으로 업데이트 되는데 98이 90보다 커서 되는 거예요 그러니까 똑같이 이미 들어갔으니까 그대로 있는 거고 이건 새로 들어간 상황인데

바운드 값은 뭐예요? 이거는 이거에 비해서 컸으니까 들어간 거고 이거는 이거에 비해서 4 색깔의 차장은 이거에 비해서 컸으니까 들어간 거죠. 그렇죠? 그 다음에 이 오른쪽 거는 이건 안 넣기로, 아이템 3는 안 넣기로 아이템 1은 넣고 2도 안 넣고 3도 안 넣고 원만 들어가 있는 상황인 거죠. 그러니까 그러면 바운드 개선에 보면 50이에요. 그럼 이거는 90보다 당연히 못한 값이니까 밑으로 갈 필요가 없는 거죠.

노란색 큐에 들어가는 상황은 아닌 Non-Premising Mode라고 판단을 하는 것이죠. 여기까지 했으면 이렇게 된다라는 것이고 그 다음에 또 큐에 남아있는 것이 노로드가 있으니까 그쪽으로 왼쪽으로 쳐야 해요. 일단 보면 왼쪽에 아이템들을 넣기로 해서 이득 50만큼 취하고 무게 10만큼 더해지고 해서 이 80이라는 것이죠. 실제로 얻을 수 있는 상태가 됐는데 그건 뺏어 놓고 있는 것이죠.

베스트 솔루션 90만 90보다 못하죠. 현재까지 알고 있는 베스트 솔루션은 90이에요. 근데 계산을 해보니까 바운드가 82에요. 그것은 여기까지 사전은 92라는 실제 베스트 솔루션 보다 못하니까 이것도 바울드가 하지 않다. 이렇게 판단을 하겠죠. 그래서 이것도 안 들어가고. 그다음에 이거 해봤더니 30 있고 바운드 40 당연히 50보다 못하니까 이것도 안 들어가죠.

그래서 여기까지 노드 다 확장을 이건 아예 안 들어갈 수 없고 아예 Q에는 없어서 이 세 개에 대해서 꺼내서 확장해보고 꺼내서 확장해보고 꺼내서 확장해봤을 때 요거까지 끝나게 될 텐데 그때 이 두 개가 Q에 들어가 있게 되는 거죠 더 확장해볼 필요가 있는 노드로서 더 탐색해볼 필요가 있는 노드로서 그래서 노드 그거를 8, 노드 9라고 부른다면 그 두 개가 적인 상황까지 몇 가지 탐색을 했을 때 이룰 거고

아직 Q가 MT가 아니니까 이건 계속 Q가 MT가 아닐 때까지 반복을 하는 거죠 탐색을 더 해볼 필요가 있는 것이 있을 때까지 현재까지 찾아 놓은 베스트 솔루션 이거다 라는 거고 상황까지 지금 온 거예요 자 그러면 이제 이거에 대해서 이거였죠? 아까 이렇게 두 개 있던 것 중에 노드 8에 대해서 순서대로 먼저 들어왔으니까 꺼내서 제거해서 자유를 만들어 보는데

그리고 넣기로 결정을 한거. 그러면 70에다가 이거 통째로 다 들어갈 수 있는거니까 무게는 5도 이지고 프라이패스는 10도 이지고 80일. 이거는 이제 아이템 1, 2, 3, 4까지 이때부터 4까지 내려온거니까 더이상 아이템 고려해볼 건 없는거죠. 80이라는 방법을 갖추는 것이 실제로 여기서 넣어줄 수 있는 최대의 값이 더 좋아질 수는 없죠.

아무튼 더 좋은 솔리션이 이미 이 전 단계에서 찾았었으니까 당연히 Q에 안 들어갈 거고 이것도 70 이것만 못하니까 안 들어갈 거고 그렇죠? 그 다음에 이제 이것을 확장을 하겠죠 이것보다는 더 큰 값을 줄 가능성이 지금 이 바운드리를 보면 보이니까 프랑스 하니까 확장을 이렇게 해요 그러면 이제 실제 아이템 4가 고려됐을 때 넣어지는 경우

안 들어가는 경우에 넣는 경우는 뭐예요? 지금 통째로 다 들어가게 된다면 12에 무게가 5만큼 더 더해져서 그렇죠? 여기 현재까지 12였는데 무게가 5만큼 더해서 17이 되어버리니까 이것도 오버레이트죠. 솔로션이 될 수 없는, 이 프로그램에서 실제로 줄 수 없는 값이에요. 이것도 안 되고 그 다음에 안 넣기로 결정하는 경우 그거는 90, 12 똑같이 안 넣기로 됐으니까 똑같은 값을 유지할 거고 바본드가 이제 IT4가 안 들어가는 상태로서에 얻을 수 있는 최대의 이득이니까

90 부대도 되겠죠. 여기 보다는 작은 값. 이거 그대로예요. 더 이상 믿어서 고려한 것이 없으니까. 그러면 실제 90이라는 것이 이거는 지금 더 이상 Q에 있지 않는 거니까 여기까지 진행이 되면 4개까지 다 4까지의 설치를 끝냈을 때 Q가 IMT가 될 거고 그때까지 얻은 최대의 이득 이게 90이죠. 90. 베스트 솔루션. 찾아놓은 베스트 솔루션.

더 이상 데뷔 내려갈 것이 없어요. 그쵸? 데뷔와이트 4까지 언제냐, 많으냐를 다 고려한 상황이니까. 그러면 이제 프라미싱, 난 프라미싱을 따져가지고 이 전체 실제 점수로 다 따진다면 여기에 차일드 두 개 있었을 거고 여기 차일드 두 개, 두 개, 두 개 여기 또 서버출이 쭉 있었겠죠. 근데 이만큼 그 중에 이만큼 노드만 탐색하고도

90이라는 실제 얻을 수 있는 최대의 이득 그것을 또 지지 않고 얻을 수 있는 거죠 여기 있는 것들이 이런 바운드 계산했을 때 실제로는 얻을 수 없는 값이다라는 것이 확실한 그런 것들이니까 저 배수 솔루션, 여태까지의 배수 솔루션 보다는 그런 것들이니까 보지 않더라도, 찾아보지 않더라도 무시할 수 있는 그런 것들이다라는 얘기예요 여기에 이 바운드라고 하는 거, 이 바운드 계산할 때

오원 랩셋 문제에 대해서는 지금 프랙셔널 랩셋 문제로 해서 오원 랩셋 문제로서는 얻기 힘들지만 프랙셔널 랩셋 문제로 생각해서 부분적으로 넣어서 부분의 이득도 취할 수 있는 문제로 만들어준다면 오원 랩셋보다는 조금 더 클 값을 가질 수 있는 그런 것을 바운드로 삼아서 그 값이 내가 실제 얻을 수 있는 것에 비해서 더 못하다라면 내가 실제 얻을 것보다 조금 더 큰 값으로 예상을 했는데 그게 이미 찾아온 것보다 못하다면 당연히 그거는

살펴볼 필요가 없는 거죠. 그래서 이것이 이제 실제 적게 솔루션, 최대 값을 갖는 솔루션으로 찾아지면서 나머지는 검색을 안 하고도 최적대를 구하는 경우가 된다는 거죠. 그래서 이게 실제

지금 아 요거 요거는 지금 앞에 요 백 트래킹 에이에서 백 트래킹을 하는 과정에서 그때 나왔던 제 그런 그때도 프라마싱 따져 가지고 요 바운드 값 계산해서 그렇죠 요 밑으로 더 내려갈 건지 말건지 이렇게 계산하는 방식으로 해서 한거였죠 좀 그래서 이 경우에는 요 모장에 요 백 트래킹 방식으로 대축 대학 그 볼 수 있을 수는 그때도 이제 바운드 값을 이용을 한 방식이 없는데 오피지 정 문제기 때문에

이때 만들어진 최종적인 탐색 트리하고 이거를 비교를 해보면 어때요? 백트래킹 방식으로 하는 것이 그것보다 노드를 좀 더 적게 탐색을 하면서도 베스트 솔루션을 찾았다는 것을 이 사례에 대해서는 알 수 있죠. 여기 있는 사실 이렇게 왼쪽에서 베스트 솔루션이 나오고 이것을 한번 살펴보는 순간에 이것이

이 차자는 베스트 솔루션 보다 못했기 때문에 이거 난 프라이미스틱 해가지고 밑에를 다 찾아보지 않고도 설치가 끝난 상태였어요. 그렇죠? 근데 이게 오늘 어땠어요? 이거에 대해서도 이렇게 데드로 내려와서 만들다 보니까 이런 것까지 다 탐색을 하고 나서야 이게 베스트구나 라는 것을 알게 된 그런 상황이죠. 즉, 이 예제를 가지고 이거를 가지고 본다면 이 백트래킹 방식인 이것보다 탐색을 더 적게 하면서 조금 더 효율적으로 베스트 솔루션을 찾았다 라고 말할 수 있죠.

그런데 그것은 만약에 솔루션이 여기서 발견 안 되고 끝까지 와서 발견되는 그런 상황이라면 또 다른 예제라면 다를 수 있죠. 오히려 이것보다 더 많은 것을 탐색하고 발견할 가능성도 있는 그러니까 그것은 어떤 사례냐 이것은 어떤 것이냐에 따라서 달라질 수 있는 것인데 이것은 백트래킹 방식이나 Depth for Search를 탐색하면서 찾은 방식이나 이것은 기본적으로는

정해진 규칙에 따라서 하는 트리의 구조에 따라서 진행을 하는 그런 블라인드 설치 형태의 트리 탐색 방식이기 때문에 실제로는 그렇지 않은 그것보다 조금 더 효율적인 블라인드 하지 않은 그런 방식에 비해서 좀 더 많은 그런 노드들을 탐색하고 뇌스 설치를 찾을 가능성이 있다라는 거죠. 이 예에서는 백트랙킹의 브랫폼스 측에서는 조금 더 효율적으로 소식을

베스트 솔루션을 찾는 그런 대제였던 것이 없고 아무튼 일반화해서 얘기할 때 두 개의 방식, 브랫트 프로셀 깊이 우선이냐 너비 우선이냐는 이 트리의 구조에 따라서 깊이 우선은 그냥 깊이만 쭉 늘려갈 수 있는 방법이 없으면 즉 난 프라미싱한 오디에 도달하면 다시 백트랙해서 다시 깊이를 늘려가고 백편으로 가서 데프트 1만큼 줄였다가 다시 데프트 룩도 늘리는 그런 방식으로 진행하는 거고 이거는 같은 데프트에 있는 것을 일단은 다 찾아보고

그중에 프로미션 한 것만 차일들을 만들어보도록 하는 그런 방식으로 진행을 하는 그런 구조에 따라서 절치 않는 순서, 노드를 확장하는 순서가 결정이 된 그런 방식이라서 그렇지 않은, 조금 더 효율적인 구조가 아닌 실제 이 바운드 값에 의해서 결정하는 그런 방식에 비해서는 좀 더 많은 노드들을 탐색하고 끝낼 가능성이 있다. 조금 더 나은 방식, 이 다음에 나오는 베스트 퍼스트라고 하는 방식은 실제 이 두 개의 브랫 퍼스트나 데프 퍼스트나 그런 방식에 비해서 훨씬 실질적으로 적은 노드를 탐색을 하면서

볼륨을 찾을 가능성이 높은 그런 알고보니 된다. 조금 조금 다음 시간에 해보도록 하구요. 자 그래서 일단 breadth-first-search라는 것이 어떤 식으로 문제를 풀어나가는 방식인지 딱 브랜치 앤 바운드 알고리즘이 살펴봤었는데 그거를 코드로 한번 일단 옮겨보도록 하죠. 자 그래서 넵슥벌전을 우리가 지금 문제를 푸는 알고리즘을 백트래킹 알고리즘으로 또 만들었었고 그 다음에 이 브랜치 앤 바운드를 쓰는 breadth-first-search를 만들었으니까

앱색으로서의 두번째 버전으로서 앱색2라는 함수 이름으로 만들어보죠. 그래서 기본적으로 찾아야 되는 것은 maximum profit. 앱색에 들어가서 얻을 수 있는 최대의 이득, 집. 그거를 구하는 그런 문제에 쓸 수 있는 펑션이에요. max profit을 넘겨주는 이것을 리턴하는 그런 것 처럼 질단 넘겨주는 예를 하는 거고 받는 것은 여정차 아이템 수

파핏, 웨이트, 총용량, 랩스에 모드를 받아서 하겠죠. 그리고 내부적으로 Q를 이용해서 브랫트 프로세치를 어떤 노드 순서대로 탐색할지 하는 거고 그 다음에 노드에 대해서 그것에 왼쪽 차일도 오른쪽 차일도로 계속 확장을 해 나가는 그런 방식으로 진행을 하도록 하는 거죠. 그래서 맨 처음에 Q, 이거 노드를 담을 수 있는 TREE의 노드를 담을 수 있는 Q를

초기화하고 mt 로 그 다음에 이제 루트 노드의 요거 상태죠. 잡스 영에 내 프로페스 영웅 페이트 구영 현재가의 차전원 맥스 또 영 또는 좀 더 안들어 있는 삶의 인템 그 맵 세계 상태를 나타내는 그 오드의 상황을 열어 그의 좀 주교해 놓고 그 다음에 그거는 교회다가 넣는 것부터 시작을 해서 이제 큐가 노드를 넣었다 뺐다 넣었다 뺐다 할텐데

여기엔 엠티가 될 때까지 엠티가 아닌 동안에 이걸 반복을 하도록 하는 거죠 그래서 Q에서 하나 노드 꺼내서 V라고 부르고 그 V에 이제 Child들을 만들어서 그 Child들을 U라고 부를 텐데 왼쪽 Child, 오른쪽 Child 이렇게 이제 만들어야 되겠죠? 그래서 Child Level은 부모의 Level보다 이제 이제 클 테니까 이렇게 U라는 Child에 대해서 그래서 일단 크게 만들고

왼쪽 유가 왼쪽 차일드인 경우 오른쪽 차일드인 경우 이제 그거 해서 해주면 되겠죠 두 개의 차일드 만들어서 일을 해야 되는 거니까 그래서 팔악게 돼 있는 요구만 해주면 이제 이 큐과 MT가 될 때까지 일을 진행을 하면서 탐색이 쭉 진행이 된다는 거죠 그래서 왼쪽 차일드에 대해서는 왼쪽 차일드는 뭐였어요 아까 그 그래프 상 그 트리 상에서 왼쪽은 그 아이템을 그 레벨에서 고래했을 때 넣기로 결정하는 경우에 상대 그쵸? 오른쪽 차일드는 안 넣기로 하는 경우니까 왼쪽 차일드는 이 부모의 웨이트 보다는

그 아이템이 더 들어갔으니까 그만큼 웨이트가 더 커질 거고 그래서 그거를 새로운 Child Wait를 할 거고 프로핏도 부모에서 얻을 수 있는 프로핏의 Child가 아이템을 더 하나 가진 아이템이니까 그 아이템이 들어가 있는 상태죠? 그래서 웨이트, 프로핏은 100%로 그대로 통째로 다 넣는 경우에 이득인 거고 근데 통째로 넣었을 때 두 용량을 초과하는지를 확인해야 되는 거죠 그래서 그게 작거나 같은지 확인해보고 또

우리가 찾는 것은 베스트 솔루션이니까 현재까지 찾아보는 그 프로핏보다 업데이트한 요 프로핏이 더 커지는 경우가 되는지를 봐야 될 거예요. 즉 솔루션이 가능성이 있으면서 현재까지 맥스 프로핏보다 더 큰 것이 될 것이면 그거를 당연히 맥스 프로핏, 새롭게 맥스 프로핏 찾은 걸로 업데이트를 해줘야 될 거고 그 다음에 뭐 해야 된다고 그랬어요. 바운드 계산해서 그게 맥스 프로핏보다 큰 경우라면 그거를 큐에다가 넣어야 된다라고 했죠. 그래서 꼭 계산을 해요.

그게 왼쪽에 U가 실제 V라는 자신의 부모보다 아이템을 하나 가지고 있는 경우인거고 다음에 오른쪽 샬드는 아이템을 안 넣기로 하는 경우라고 했죠. 그래서 Wt 그대로 똑같을 거고 부모 무게는 똑같을 테니까 아이템을 안 넣기로 했으니까 그래그래서 Profit도 똑같을 거고 대신 바운드 계산했을 때 Max Profit보다 큰지 그것도 확인이 돼야 될 거고 Q에 들어가지야되는 그 상황이면 들어가는 거죠. 바운드가 크면은.

그럴 때는 넣고 이렇게 해 주면 되겠다. 그래서 요각을 그런 방식으로 계산을 해서 Q에다가 요 조건이 만족이 되면 bound가 max profit, 여태까지 찾아 놓은 max profit 보다 크면 넣는 식으로 트리 를 확장을 해 나간다 라는 거죠. Q에 들어가면 일단 그 child 부분을 더 만들어 볼 수 있는 대상으로 들어가는 거니까 그렇게 하면 되겠다. 그리고 Bound 계산하는 것은 요거

전장에 있었던 이 바운드 계산 함수랑 동일해요. 프랙셔널 액셋 문제에서의 최대 이득 계산하는 함수로 정보을 수 있는 거죠. 아이템 100% 1로 넣을 수 있는 것들 다 넣고 용량이 그 다음 거 고려했을 때 100% 들어가지 않는다면 부분으로 들어갈 수 있을 만큼 꽉 채워서 부분으로 프랙셔널을 취해서 이득도 프랙셔널을 취하도록 그렇게 만드는 방식에 그만큼 비득

비율만큼 넣는 그런 방식으로 하자 라는 거죠. 자 그러면은 이제 요거 뭐 코드는 그 그거와 똑같으니까 그거는 딱 그냥 그대로 쓰면 되고요. 이렇게 해서 브랜치 앤 바운드를 하는데 브랜트 풀스 숙지를 이용하는 경우에 얘를 살펴봤어요. 주로 코드도 만들어 봤고 그래서 오늘 시간이 거의 다 되었으니까 다음 시간에는 요 브랜트 풀스 끝에 아까 처음에 얘기했듯이 요 브랜치 앤 바운드라는 거는 어떤 특정한 하나의 설치 방식에 국한되지 않는다라고 했어요.

백트릭은 'depth for search'라는 방식으로 고정되어 있는, 국한되는 방식에 대한 방식으로 'branch and bound'는 그게 아닙니다. 그러면 'breadth for search'도 국한되지 않는 방식 중 하나인데 그 말고도 또 쓸 수 있는 다른 설치 방법이 있을 수 있겠다는 거죠. 그래서 'best for search'라는 것을 다음 시간에 'branch and bound'에 대해서 어떤 식으로 쓸 수 있는지 살펴볼 텐데, 오늘 뭐 시간 다 됐으니까 동영상으로 이제 '모를' '모를' 보도록 하겠습니다.

요 부분하고 아마 tsp 문제까지도 다음 번 동영상에 들어갈 수 있을 것 같고 시간을 봐야 될 것 같은데 그래서 아마 그것까지 다 들어간다면 다음 대면 시간에는 7장의 내용을 보게 될 것 같아요