0-1 Knapsack – 개선된 BFS 기반 알고리즘

Presentation on theme: "0-1 Knapsack – 개선된 BFS 기반 알고리즘"— Presentation transcript:

1 0-1 Knapsack – 개선된 BFS 기반 알고리즘
void breadth_first_branch_and_bound2 (state_space_tree T) { queue_of_node Q; node u, v; number maxprofit; initialize(Q); // Q는 빈 대기열로 초기화 v = root of T; // 루트 노드를 방문 enqueue(Q,v); maxprofit = profit(v); while(!empty(Q)) { dequeue(Q,v); if(bound(v) > maxprofit) //노드가 여전히 유망한 지 점검 for(each child u of v) { // 각 자식 노드를 방문 if(profit(u) > maxprofit && weight < W) maxprofit = profit(u); if(bound(u) > best && weight < W) enqueue(Q,u); }

2 0-1 Knapsack – 개선된 BFS 기반 상태공간트리
profit weight bound mp = 40 mp = 40 mp = 70 mp = 70 mp = 70 mp = 70 mp = 90 mp = 70 mp = 70 mp = 90 개선된 BFS 알고리즘에서 방문하지 않아도 되는 노드들 mp = 90 mp = 90

3 0-1 Knapsack –개선된 BFS 기반 큐 Queue에서의 진행모습 (1/4) Queue maxprofit=0
(0,0) $0,0 $115 maxprofit=40 (1,1) $40,2 $115 (1,2) $0,0 $82 (0,0) $0,0 $115 maxprofit=70 (1,2) $0,0 $82 (2,1) $70,7 $115 (2,2) $40,2 $98 (1,1) $40,2 $115 (0,0) $0,0 $115

4 0-1 Knapsack – 개선된 BFS 기반 큐 Queue에서의 진행모습 (2/4) No!
(2,4) $0,0 $60 No! Since $60 < $70 (best) maxprofit=70 (2,1) $70,7 $115 (2,2) $40,2 $98 (2,3) $30,5 $82 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115 (3,1) $120,17 $0 No! Since 17 > 16(=W) maxprofit=70 (2,2) $40,2 $98 (2,3) $30,5 $82 (3,2) $70,7 $80 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115

5 0-1 Knapsack – 개선된 BFS 기반 큐 Queue에서의 진행모습 (3/4) No!
(3,4) $40,2 $50 No! Since $50 < $90 (best) maxprofit=90 (2,3) $30,5 $82 (3,2) $70,7 $80 (3,3) $90,12 $98 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115 maxprofit=90 (3,3) $90,12 $98 No Branching Since $82 < $90 (best) $80 < $90 (best) (3,2) $70,7 $80 (2,3) $30,5 $82 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115

6 0-1 Knapsack – 개선된 BFS 기반 큐 Queue에서의 진행모습 (4/4) Since 17 > 16(=W)
(4,3) $100,17 $0 (4,4) $90,12 $90 Since 17 > 16(=W) $90 = $90 (best) No! maxprofit=90 Empty! (3,3) $90,12 $98 (3,2) $70,7 $80 (2,3) $30,5 $82 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115

7 0-1 Knapsack – 개선된 BFS 기반 알고리즘 분석
불필요한 Branching을 피할 수 있다. 개선된 분기한정 가지치기로 BFS를 하여 상태공간트리를 그려보면, 검색하는 노드의 개수는 13이다. 되추적 알고리즘(DFS 기반 해결책-13개 노드 검색)과 동일 기본적인 BFS 기반 알고리즘 (17개 노드 검색) 보다 좋다.

8 Best-First-Search (최고우선검색)– Concept
최적의 해답에 더 빨리 도달하기 위한 전략: 1. 주어진 노드의 모든 자식노드를 검색한 후, 2. 유망한 노드인지를 살펴보고, 3. 그 중에서 가장 좋은(최고의) 한계치(bound)를 가진 노드를 우선적으로 확장한다. (일반적으로) 최고우선검색(Best-First Search)을 사용하면, 너비우선검색에 비해서 검색 성능이 좋아짐

9 Best-First-Search – Strategy
최고의 한계를 가진 노드를 우선적으로 선택하기 위해서 우선순위 대기열(Priority Queue)을 사용한다. Top Priority: bound 값이 가장 큰 노드 우선순위 대기열은 힙(heap)을 사용하여 효과적으로 구현할 수 있다.

10 Best-FS based Branch-and-Bound Algorithm
void best_first_branch_and_bound(state_space_tree T){ priority_queue_of_node PQ; node u, v; number maxprofit; initialize(PQ); //PQ를 빈 대기열로 초기화 v = root of T; maxprofit = profit(v); insert(PQ,v); while(!empty(PQ)) { //최고 한계 값을 가진 노드를 제거 remove(PQ,v); if(bound(v) > maxprofit) //노드가 여전히 유망한 지 점검 for(each child u of v) { if(profit(u) > maxprofit && weight < W) maxprofit = profit(u); if(bound(u) > maxprofit && weight < W) insert(PQ,u); }

11 0-1 Knapsack – Best-FS 기반 상태공간트리
bound weight profit mp = 40 mp = 70 mp = 90

12 0-1 Knapsack – Best-FS 기반 우선순위큐
Priority Queue에서의 진행모습 (1/3) Priority Queue maxprofit=0 (0,0) $0,0 $115 maxprofit=40 (1,1) $40,2 $115 (1,2) $0,0 $82 (0,0) $0,0 $115 Priority queue 특성상 (2,1) 노드가 가장 앞에 위치하고 (2,2)가 그 다음에 위치함! (2,1) $70,7 $115 (0,0) $0,0 (2,2) $40,2 $98 (1,1) (1,2) $82 maxprofit=70

13 0-1 Knapsack – Best-FS 기반 우선순위큐
Priority Queue에서의 진행모습 (2/3) (3,1) $120,17 $0 No! Since 17 > 16(=W) (0,0) $0,0 $115 (1,1) $40,2 (1,2) $82 maxprofit=70 (2,2) $40,2 $98 (3,2) $70,7 $80 (2,1) $70,7 $115 (3,4) $40,2 $50 No! Since $50 < $90 (best) maxprofit=90 (3,3) $90,12 $98 (1,2) $0,0 $82 (3,2) $70,7 $80 Priority queue 특성상 (3,3) 노드가 가장 앞에 위치함! (2,2) $40,2 $98 (2,1) $70,7 $115 (1,1) $40,2 $115 (0,0) $0,0 $115

14 0-1 Knapsack – Best-FS 기반 우선순위큐
Priority Queue에서의 진행모습 (3/3) (4,1) $100,17 $0 (4,2) $90,12 $90 Since 17 < 16(=W) $90 = $90 (best) No! maxprofit(best)=90 (1,2) $0,0 $82 (3,2) $70,7 $80 (3,3) $90,12 $98 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,1) $40,2 $115 (0,0) $0,0 $115 maxprofit(best)=90 Empty! No Branching Since $82 < $90 (best) $80 < $90 (best) (3,2) $70,7 $80 (1,2) $0,0 $82 (3,3) $90,12 $98 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,1) $40,2 $115 (0,0) $0,0 $115

15 0-1 Knapsack – Best-FS 기반 분석
분기한정 가지치기로 최고우선검색을 하여 상태공간트리를 그려보면, 검색하는 노드의 개수는 11로서 가장 우수하다. 되추적 알고리즘(DFS 기반 해결책-13개 노드 검색)보다 좋다! BFS 기반 알고리즘 (17개 노드 검색) 보다 좋다. 개선된 BFS 기반 알고리즘 (13개 노드 검색) 보다 좋다.