0-1 배낭채우기 알고리즘(되추적알고리즘,분기한정법 알고리즘)

소개글

0-1 배낭채우기 알고리즘(되추적알고리즘,분기한정법 알고리즘)에 대한 보고서 자료입니다.

목차

1. Backtracking 알고리즘(되추적 알고리즘)

2. Best-first seach를 이용한
Branch and Bound(분기한정법) 알고리즘
(우선순위 큐의 일종인 max heap 이용)

3. 두 알고리즘 비교/평가

본문내용

ight
<< setw(8) << u.bound << endl;
count++; //검색한 노드수
//-----------------------//
/***************************************/
/* 노드 u를 배낭에 안포함 */
/***************************************/
u.weight = v.weight;
u.profit = v.profit;
u.bound = bound(u);
u.includ = 0; //0: 현재아이템 배낭에 포함을 의미
if (u.bound > *maxprofit)
insert(u, &pq_rear);
//-----------------------------------//
include[u.level] = 0;//w[u.level]포함
//현재노드 상태트리에 추가
state_space_tree_save(u.level, ++no[u.level]);
cout<<" ("< << setw(8) << u.profit
<< setw(8) << u.weight
<< setw(8) << u.bound << endl;
count++; //검색한 노드수
//-----------------------------------//
}
}
}
//상태공간트리 노드 만듬
void state_space_tree_save(int i, int yn)
{
state_space_tree[count][0]=i;
state_space_tree[count][1]=yn;
}
//bound계산
float bound(node u)
{
int j, k; //k: k번째 아이템을 배낭에 넣으면 무게가 넘치다.
int totweight;
float result;
if (u.weight >= W) //자식마디에서 쓸 공간이 있어야됨
return 0;
else
{
result = (float)u.profit;
j = u.level + 1;
totweight = u.weight;
while(j <= n && totweight + w[j] <= W) //n: 아이템의 수
{ //가능한 많은 아이템을 취한다.
totweight = totweight + w[j];
result = result + p[j];
j++;
}
k=j;
if (k<=n)
{//k번째 아이템을 일부분 취한다.
result = result + (W - totweight) * p[k]/w[k];
}
return result;
}
}
//히프(우선순위 큐)에 삽입
void insert(node item, int *n)
{
int i;
if(*n == MAX-1)
cout << "The Priority Queue is full." << endl;
i=++(*n);
while ((i!=1) && (item.bound > PQ[i/2].bound))
{
PQ[i] = PQ[i/2]; //부모노드에 있는 값을 현재 노드에 가져옴
i/=2;
}
PQ[i] = item;
}
//히프(우선순위 큐)에서 삭제
node remove(int *n)
{
int parent, child;
node item, temp;
if(*n == 0)
cout << "The Priority Queue is empty\n";
item = PQ[1];
temp = PQ[(*n)--];
parent = 1;
child = 2;
while(child<=*n)
{
if((child < *n) && (PQ[child].bound < PQ[child+1].bound))
child++;
if(temp.bound >= PQ[child].bound) break;
PQ[parent] = PQ[child];
parent = child;
child *= 2;
}
PQ[parent] = temp;
return item;
}
▶테스트 (파일명: item.txt)
=> Backtracking 알고리즘과 테스트파일 동일하다. 그래야 서로 비교 가능하다.
▶실행결과
3. Backtracking, Best-first seach 두 알고리즘 비교/평가
▶ 비교
Backtracking
Best-first seach
검색한 노드수
13
11
배낭에 들어간 아이템
1, 3
1, 3
최고 이익
$90
$90
=> 검색한 노드수를 비교해보면 Backtracking 알고리즘이 Best-first search 알고리즘보다 2개의 노드를 더 많이 검색한다. 즉 Best-first search(최고우선검색) 알고리즘이 더 좋다.
물론 배낭에 들어간 아이템이나, 최고이익은 같다.
검사하는 마디수를 2개 절략하는 것은 별로 인상적이지 않지만, 큰 상태공간 트리에서 최고우선검색으로 최적 해를 빨리 찾는 경우 차이는 꽤 심각할 수 있다.
① Backtracking 알고리즘
- 이 알고리즘이 점검하는 노드의 수
: 즉 최악의 경우 각 노드가 2개의 child 노드를 가지기 때문이다.
- 전략
깊이 우선순위로 각 노드를 방문하여 다음을 수행:
a. 그 노드의 profit 와 weight를 계산
b. 그 노드의 bound를 계산
c. (weightmaxprofit) 이면, 검색을 계속.
그렇지 않으면 되추적(부모노드로 되돌아감)한다.
- 고찰: 최선이라고 여겼던 노드를 선택했다고 해서 실제로 그 노드로부터 최적 해가 항상 나온다는 보장은 없음.
② Best-first seach를 이용한 Branch and Bound 알고리즘
- 전략
a. 주어진 노드의 모든 자식노드를 검색한 후,
b. 유망하면서 확장되지 않은 노드를 살펴보고,
c. 그 중에서 가장 좋은(최고의) 한계지(bound)를 가진 노드를 확장
- 고찰: 최고라고 여겨지는 마디에서 최적 해를 실제로 끌어낸다는 보장은 없다.
위의 2번 bestfirst.cpp 프로그램에서 (2,1)이 (2,2)보다 더 좋은 것으로 보였지만, 마디(2,2)가 최적의 해를 이끌어 냈다. 일반적으로, 최고우선검색으로도 어떤 사례에 대해서는 상태공간트리 전체를 거의 또는 모두 구축할 수 밖에 없다.

키워드

배낭채우기,   되추적,   분기한정법,   backtracking,   branch and bound