BranchAndBound

3. Branch&Bound 분기한정법 State Space Tree활용 최적해 구하기에 적용 가능. Backtracking보다는 최적해를 구하기 위해 모든 해의 한계값(직접x)을 계산해 고려함. 각 노드에 대한 한계값bound을 계산함. 해당 노드는 bound보다 큰 값을 가질 확률이 없음. bound값이 지금까지의 최적해보다 좋은가?로 최적해 값을 업데이트하고 노드의 promising여부를 판단함. promising하지 않은 노드의 자식노드는 탐색하지 않음. 0-1 Knapsack 문제 state space tree : 왼쪽으로 가면 현재 아이템을 담지 않는 걸로, 오른쪽으로 가면 현재 아이템을 담는 걸로 함. 루트에서 리프노드까지의 모든 경로가 해답후보임 최적해를 찾는 문제이므로 전체를 다 탐색하기..