ImJay

0-1 Knapsack Problem 너비 우선 검색을 사용한 한정분기 (Branch and Bound) 서론 한정 분기 전략의 동기 : 되추적의 비효율되추적의 탐색 과정에서 Valid가 적용되더라도 여전히 상당한 비율의 정점을 방문하지 않아도 됨을 발견 되추적의 비효율 해결책 : 각 노드를 방문할 때마다 한계치(bound)를 계산 한계치(Bound) : 해당 노드로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계 값 기존 깊이 우선 검색(DFS) 기반 알고리즘은 분기한정의 특성을 제대로 활용하고 있지 못함. 그렇다면… 너비 우선 검색(BFS)을 수정하여 구현 0/1 Knapsack Problem의 너비 우선 검색을 사용한 한정분기(Branch and Bound) 전략 1. 그 노드의 p..

0-1 Knapsack Problem 깊이 우선 검색을 사용한 한정분기 (Branch and Bound) 서론 한정 분기 전략의 동기 : 되추적의 비효율되추적의 탐색 과정에서 Valid가 적용되더라도 여전히 상당한 비율의 정점을 방문하지 않아도 됨을 발견 되추적의 비효율 해결책 : 각 노드를 방문할 때마다 한계치(bound)를 계산 한계치(Bound) : 해당 노드로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계 값 0/1 Knapsack Problem의 깊이 우선 검색을 사용한 한정분기(Branch and Bound) 전략 1. 그 노드의 profit과 weight를 계산한다. 2. 그 노드의 bound를 계산한다. 3. 현재 노드의 profit이 maxprofit보다 크면 maxpr..