분기한정법

알고리즘 6 분기한정법

각 노드를 방문할 때마다, 유망한지 여부를 확인하기 위해 Bound를 계산한다. 바운드= 해답치의 한계

이전까지의 최고 해답값보다 바운드가 더 좋다면 그 마디는 유망하다.

0-1 배낭채우기문제 - 깊이우선탐색 개념

바운드설정법

k = 총무게 W를 넘는 위치.

totweight = 이전까지무게 + 시그마 i+1~k-1 앞으로무게

바운드 = 이전까지금액 + 시그마~앞으로금액 + (W-totweight)*(k의 가성비)

최대이익은 현재까지금액 기준, 이를 다음의 바운드값과 비교.

유망하다면 자식노드를 계속 탐색.(재귀적)

0-1 배낭채우기문제 - 너비우선검색

(분기한정 가지치기 최고우선검색)

큐 사용 구현.

코드

if(profit(u) > maxprofit && weight < W)

   maxprofit = profit(u)

if(bound(u) > maxprofit && weight < W)

   enQueue(Q,u);

0-1 배낭채우기문제 - 개선된 너비우선탐색

유망한지 먼저 점검 후에 탐색.

if(bound(v)>maxprofit)

   if(profit(u) > maxprofit && weight < W)

      maxprofit = profit(u)

   if(bound(u) > maxprofit && weight < W)

      enQueue(Q,u);

0-1 배낭채우기문제 - 최고우선검색

우선순위 큐 사용.

TSP - BNB 기반 상태공간트리구축(최고우선)

바운드 = v1->va 이동시

va 는 (1,a) 빼고 나머지 중 최소

나머지 vx들은 (a,x)빼고 나머지중 최소

v1->va->vb이동시

vb는 (1,a,b)빼고 최소

vx는(a,b,x)빼고 최소

TSP - BFS 기반 상태공간트리구축(너비우선)