6장 Branch and bound Algorithm

chap6 Branch and bound algorithm design approach

• 0-1 knapsack 문제에 대해서 항상 앞서있지는 않지만 많은 경우의 input 에 대해 유리한 결과를 보여준다.
• tree를 탐색하는 순서를 정해두고 하지않는다.
• 오직 optimization 문제를 위해 설계된 알고리즘이다.

breadth first search = queue data structure로 구성된 level order traversal로 kanpsack 문제 해결하기.

BFS = 너비 우선 탐색

• 시작노드에서 시작하여 가까운 노드부터 우선적으로 탐색하는 알고리즘
• recursive function을 사용x

BFS 동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. queue가 빌 때까지 반복한다(더 이상 2번을 반복하지 못할 때 까지)

• queue가 빌때까지 반복하며 dequeue하여 값을 읽어들이고 promising하다면 node의 자식 노드 둘을 enqueue하는 방식.
• 최대 weight를 넘으면 bound를 0으로 초기화 해서 걸러줌.
• breadth first search도 depth first search와 마찬가지로 미리 결정한 순서를 탐색하기에 크게 다를게 없다.
• parent node에 방문해서 그당시에는 maxprofit과 bound의 비교에서 살아남아 child node들을 enqueue했지만 children node에 방문 했을때 maxprofit이 바뀌기 때문에 낭비가 생긴다는 단점이 있다

best first search = double check한다.

1. root 방문 후 root 의 자식 노드들을 방문한다.
2. bound가 더 큰 유망한 노드를 선택한다.
3. 선택된 노드의 자식 노드들을 방문한다.
4. 2~3 반복

• 즉, bound 값이 maxprofit 보다 여전히 좋은지 결정하는 검사를 추가한것.
• worst case는 마찬가지로 2^n이다.