Branch-and-Bound with the 0-1 Knapsack problem (Best-First Search)(0-1 배낭문제-최고우선탐색)

Basic Concepts

---

In general, the breadth-first search strategy has no advantage over a depth-first search (backtracking).

• 🔗 Backtracking with the 0-1 Knapsack problem (Depth-First Search)
• 🔗 Branch-and-Bound with the 0-1 Knapsack problem (Breadth-First Search)

However, we can improve our search by using our bound to do more than just determine whether a node is promising. After visiting all the children of a given node, we can look at all the promising, unexpanded nodes and expand beyond the one with the best bound. Recall that a node is promising if its bound is better than the value of the best solution found so far. In this way, we often arrive at an optimal solution more quickly than if we simply proceeded blindly in a predetermined order. The example that follows illustrates this method.

 

👉 0-1 배낭 문제에 최고우선탐색을 적용하기에 앞서 깊이우선탐색(백트래킹)과 너비우선탐색으로 해결하는 법을 살펴봤다. 일반적으로 너비우선탐색은 깊이우선탐색보다 좋은 점이 없었다. 하지만 최고우선탐색에서는 bound 값을 노드의 유망성 여부를 판단하는 것 외에 추가적으로 활용하여 알고리즘의 효율을 향상시킨다.

최고우선탐색은 특정 노드의 모든 자식노드를 방문한 후 유망하면서 미확장된 노드 모두를 살펴보고 그 중 bound 값이 가장 좋은 노드를 우선으로 확장한다. 지금까지 찾은 최고의 해답보다 그 bound 값이 더 좋다면 그 노드는 유망하다. 이렇게 하면 미리 결정된 순서(깊이우선탐색, 너비우선탐색)대로 탐색을 진행하는 것보다 더 빨리 최적의 해를 찾게된다.

 

Example Suppose that n = 4, W = 16, and we have the following:

i	$p_i$	$w_i$	$p_i/w_i$
1	$40	2	$20
2	$30	5	$6
3	$50	10	$5
4	$10	5	$2

 

The pruned state space tree produced using best-first search in above Example. Stored at each node from top to bottom are the total profit of the items stolen up to that node, their total weight, and the bound on the total profit that could be obtained by expanding beyond the node. The node shaded in color is the one at which an optimal solution is found.

 

Step 1 Visit node (0, 0) (the root).

(a) Set its profit and weight to ＄0 and 0.

(b) Compute its bound to be ＄115.

(c) Set maxprofit to 0.

profit = 0
weight = 0
bound = 115(= 40 + 30 + (16 - 7) x 50/10)
maxprofit = 0

 

Step 2 Visit node (1, 1).

(a) Compute its profit and weight to be ＄40 and 2.

(b) Because its weight 2 is less than or equal to 16, the value of W, and its profit ＄40 is greater than ＄0, the value of maxprofit, set maxprofit to ＄40.

(c) Compute its bound to be ＄115.

profit = 40 
weight = 2 
bound = 115

(2 <= 16(W)) && (40 > 0(=current maxprofit)) → maxprofit = 40

 

Step 3 Visit node (1, 2).

(a) Compute its profit and weight to be ＄0 and 0.

(b) Compute its bound to be ＄82

profit = 0 
weight = 0 
bound = 82(= 30 + 50 + (16 - 15) x 10/5)

(0 <= 16(W)) && (0 > 40(=current maxprofit)) → false

 

Step 4 Determine promising, unexpanded node with the greatest bound.
(a) Because node (1, 1) has a bound of ＄115 and node (1, 2) has a bound of ＄82, node (1, 1) is the promising, unexpanded node with the greatest bound. We visit its children next.

// 아직 확장하지 않은 노드 중에서 가장 큰 bound 값을 가진 유망한 노드를 찾는다. 
// 노드(1,1)의 bound = 115 > 노드(1,2)의 bound = 82 이므로, 
// 노드(1,1)의 bound 값이 가장 크면서 유망하고 확장하지 않은 노드이다. 
// 따라서 그 노드의 자식노드(2,1)를 다음으로 방문한다.

 

Step 5 Visit node (2, 1).

(a) Compute its profit and weight to be ＄70 and 7.

(b) Because its weight 7 is less than or equal to 16, the value of W , and its profit ＄70 is greater than ＄40, the value of maxprofit, set maxprofit to ＄70.

(c) Compute its bound to be ＄115.

profit = 70 
weight = 7 
bound = 115

(7 <= 16(W)) && (70 > 40(=current maxprofit)) → maxprofit = 70

 

Step 6 Visit node (2, 2).

(a) Compute its profit and weight to be ＄40 and 2.

(b) Compute its bound to be ＄98.

profit = 40
weight = 2
bound = 98(= 40 + 50 + (16 - 12) x 10/5)

(2 <= 16(W)) && (40 > 70(=current maxprofit)) → false

 

Step 7 Determine promising, unexpanded node with the greatest bound.

(a) That node is node (2, 1). We visit its children next.

// 아직 확장하지 않은 노드 중에서 가장 큰 bound 값을 가진 유망한 노드를 찾는다. 
// 노드(2,1)의 bound = 115 > 노드(2,2)의 bound = 98 > 노드(1,2)의 bound = 82 이므로 
// 노드(2,1)의 자식노드인 (3,1)를 다음으로 방문한다.

 

Step 8 Visit node (3, 1).

(a) Compute its profit and weight to be ＄120 and 17.

(b) Determine that it is nonpromising because its weight 17 is greater than or equal to 16, the value of W. We make it nonpromising by setting its bound to ＄0.

profit = 120
weight = 17 
bound = 0

(17 <= 16(W)) && (120 > 70(=current maxprofit)) → false
// weight가 W를 초과했으므로 bound 값을 0으로 놓아 유망하지 않다고 표시한다.

 

Step 9 Visit node (3, 2).
(a) Compute its profit and weight to be ＄70 and 7.
(b) Compute its bound to be ＄80.

profit = 70 
weight = 7 
bound = 80(= 40 + 30 + 10)

(7 <= 16(W)) && (70 > 70(=current maxprofit)) → false

 

Step 10 Determine promising, unexpanded node with the greatest bound.
(a) That node is node (2, 2). We visit its children next.

// 아직 확장하지 않은 노드 중에서 가장 큰 bound 값을 가진 유망한 노드를 찾는다. 
// 노드(2,2)의 bound = 98 > 노드(1,2)의 bound = 82 > 노드(3,2)의 bound = 80 이므로 
// 노드(2,2)의 자식노드인 (3,3)을 다음으로 방문한다.

 

Step 11 Visit node (3, 3).
(a) Compute its profit and weight to be ＄90 and 12.
(b) Because its weight 12 is less than or equal to 16, the value of W, and its profit ＄90 is greater than ＄70, the value of maxprofit, set maxprofit to ＄90.

(c) At this point, nodes (1, 2) and (3, 2) become nonpromising because their bounds, ＄82 and ＄80 respectively, are less than or equal to ＄90, the new value of maxprofit.

(d) Compute its bound to be ＄98.

profit = 90
weight = 12
bound = 98(= 40 + 50 + (16 - 12) x 10/5)

(12 <= 16(w)) && (90 > 70(current maxprofit)) → maxprofit = 90
// 82(=노드(1,2)의 bound) <= 90 → 이 시점에서 노드(1,2)는 유망하지 않다고 결정된다.
// 80(=노드(3,2)의 bound) <= 90 → 이 시점에서 노드(3,2)는 유망하지 않다고 결정된다.

 

Step 12 Visit node (3, 4).
(a) Compute its profit and weight to be ＄40 and 2.

(b) Compute its bound to be ＄50.

(c) Determine that it is nonpromising because its bound ＄50 is less than or equal to ＄90, the value of maxprofit

profit = 40 
weight = 2 
bound = 50(= 40 + 10)

(2 <= 16(W)) && (40 > 90(current maxprofit)) → false
// 50(=노드(3,4)의 bound) <= 90 → 노드(3,4)는 유망하지 않다고 결정된다.

 

Step 13 Determine promising, unexpanded node with the greatest bound.

(a) The only unexpanded, promising node is node (3, 3). We visit its children next.

// 아직 확장하지 않은 노드 중에서 가장 큰 bound를 가진 유망한 노드를 찾는다. 
// 유일하게 확장되지 않고 남은 유망한 노드는 (3,3)이다. 
// 그 노드의 자식노드인 (4,1)을 다음으로 방문한다.

 

Step 14 Visit node (4, 1).

(a) Compute its profit and weight to be ＄100 and 17.

(b) Determine that it is nonpromising because its weight 17 is greater than or equal to 16, the value of W. We set its bound to ＄0.

profit = 100 
weight = 17 
bound = 0

(17 <= 16(W)) && (100 > 90(current maxprofit)) → false
// weight가 W를 초과했으므로 bound 값을 0으로 놓아 유망하지 않다고 표시한다.

 

Step 15 Visit node (4, 2).

(a) Compute its profit and weight to be ＄90 and 12.

(b) Compute its bound to be ＄90.

(c) Determine that it is nonpromising because its bound ＄90 is less than or equal to ＄90, the value of maxprofit. Leaves in the state space tree are automatically nonpromising because their bounds cannot exceed maxprofit.

profit = 90
weight = 12 
bound = 90(= 40 + 50)

(12 <= 16(W)) && (90 > 90(current maxprofit)) → false
// 90(=노드(4,2)의 bound) <= 90 → 노드(4,2)는 유망하지 않다고 결정한다.

 

Step16 Because there are now no promising, unexpanded nodes, we are done.

// 상태공간트리에서 잎노드들은 그 bound 값이 maxprofit을 넘을 수 없으므로 
// 자동으로 유망하지 않게 된다. 유망하면서 미확장된 노드가 없으므로 알고리즘이 종료된다.

 

It must be stressed, however, that there is no guarantee that the node that appears to be best will actually lead to an optimal solution. In Example, node (2,1) appears to be better than node (2,2), but node (2,2) leads to the optimal solution. In general, best-first search can still end up creating most or all of the state space tree for some instances.

 

👉 위의 예제에서 노드(2,1)이 노드(2,2)보다 더 좋아보였지만 노드(2,2)가 해답을 이끌어낸다. 즉, 최고라고 여겨지는 노드에서 최적의 해가 나온다는 보장은 없다.

 

 

The Best-First Search with Branch-and-Bound Pruning Algorithm for the 0-1 Knapsack Problem

---

Algorithm Design

To determine whether the node is promising, we initialize totweight and bound to weight and profit, respectively, and then greedily grab items, adding their weights and profits to totweight and bound, until we reach an item whose weight would bring totweight above W . We grab the fraction of that item allowed by the available weight, and add the profit of that fraction to bound. In this way, bound becomes an upper bound on the amount of profit we could obtain by expanding beyond the node. If the node is at level i, and the node at level k is the one whose weight would bring the weight above W, then

$$ \begin{align} totweight &= weight + \sum_{j=i+1}^{k-1}w_j, \quad \text{and} \notag{}\\ bound &= \left(profit + \sum_{j=i+1}^{k-1}p_j\right) + (W - totweight) \times \frac{p_k}{w_k} \notag{} \end{align} $$

• profit: the sum of the profits of the items included up to the node.
• weight: the sum of the weights of those items.
• totweight: the sum of the weights could be obtained by expanding beyond that node (W를 초과할 수 없다.)
• bound: the upper bound on the profit that could be obtained by expanding beyond that node.

Recall that a node is also nonpromising if

$$ weight \le W $$

The implementation of best-first search consists of a simple modification to breadth-first search. Instead of using a queue, we use a priority queue. In the algorithm, insert (PQ, v) is a procedure that adds v to the priority queue PQ, whereas remove (PQ, v) is a procedure that removes the node with the best bound and assigns its value to v.

 

👉 너비우선탐색을 조금 변형하면 최고우선탐색을 구현할 수 있다. 최고의 bound 값을 가진 노드를 우선적으로 선택하기 위해 단순 큐 대신 우선순위 큐(Priority Queue)가 사용된다. insert(PQ, v)는 v값을 우선순위 큐에 추가하고, remove
(PQ, v)는 최고 bound 값을 갖는 노드를 우선순위 큐에서 제거하면서 그 값을 v에 할당한다.

 

Besides using a priority queue instead of a queue, we have added a check  following the removal of a node from the priority queue. The check determines if the bound for the node is still better than best. This is how we determine that a node has become nonpromising after visiting the node. For example, node (1, 2) in the above Exampe(Step 3) is promising at the time we visit it. In our implementation, this is when we insert it in PQ. However, it becomes nonpromising when maxprofit takes the value ＄90(Step 11). In our implementation, this is before we remove it from PQ. We learn this by comparing its bound with maxprofit after removing it from PQ. In this way, we avoid visiting children of a node that becomes nonpromising after it is visited.

 

👉 최고우선탐색은 우선순위 큐에서 노드를 제거한 뒤 특정 노드의 bound 값이 여전히 maxprofit 보다 나은지를 확인한다. 예를 들어, 앞의 예제 Step11에서 maxprofit의 값이 90이 된 후에 노드(1,2) 및 노드(3,2)가 더 이상 유망하지 않음을 확인한 것이다. 이렇게 하면 특정 노드의 방문 후 유망하지 않게 된 노드의 자식 노드를 방문하지 않아도 되어 알고리즘의 효율성이 개선된다.

 

Pseudocode

• The Best-First Search with Branch-and-Bound Pruning Algorithm for the 0-1 Knapsack Problem

// We will use the following data type in the algorithm.
struct node
{
    int level; // the node's level in the tree
    int profit;
    int weight;
    float bound;
}

// Pseudocode: The Best-First Search Branch-and-Bound Pruning Algorithm 
// for the 0-1 Knapsack problem
void knapsack3(int n, const int p[], cont int w[], int W, int &maxprofit)
// Problem: Let n items be given, where each item has a weight and a profit. 
// The weights and profits are positive integers. Furthermore, let a positive 
// integer W be given. Determine a set of items with maximum total profit, 
// under the constraint that the sum of their weights cannot exceed W.
// Inputs: positive integers n and W, arrays of positive integers w and p, 
// each indexed from 1 to n, and each of which is sorted in nonincreasing 
// order according to the values of p[i] / w[i].
// Outputs: an integer maxprofit that is the sum of the profits of 
// an optimal set.
{
	queue_of_node  PQ;  
	node u, v;

	initialize(PQ);
	v.level =0;  v.profit = 0;  v.weight = 0;  
	maxprofit = 0;
	v.bound = bound(v);
	insert (PQ, v);
	while (!empty(Q)) { // Remove nod with 
		remove(PQ, v); // best bound
		if(v.bound > maxprofit) { // Check if node is still
			u.level = v.level + 1; // promising.
			u.profit = v.profit + p[u.level];
			u.weight = v.weight + w[u.level];
			
			if ((u.weight <= W) && (u.profit > maxprofit)) 
				maxprofit = u.profit;
			u.bound = bound(u);
			if (bound(u) > maxprofit) 
				insert (PQ, u);
			u.weight = v.weight; // Set u to the child 
			u.profit = v.profit; // that does not include
			u.bound = bound(u); // the next item.
			if (u.bound > maxprofit) 
				insert (PQ, u);
		}  
	}
}
/* Function bound is the same */

 

Source Code

• knapsack_bestfs.h

// File: knapsack_bestfs.h
#ifndef KNAPSACK_BESTFS_H
#define KNAPSACK_BESTFS_H
#include "pqueue.h"  // Provides priority_queue
using namespace data_structures; // for node

namespace algorithms
{
  void knapsack3(int n, const int p[ ], const int w[ ], int W, int& maxprofit);
  // Problem: Let n items be given, where each item has a weight and
  // a profit. The weights and profits are positive integers. Furthermore,
  // let a positive integer W be given. Determine a set of items with
  // maximum total profit, under the constraint that the sum of their
  // weights cannot exceed W .
  // Inputs: positive integers n and W , arrays of positive integers
  // w and p, each indexed from 1 to n, and each of which is sorted in
  // nonincreasing order according to the values of p[i] / w [i].
  // Outputs: an integer maxprofit that is the sum of the profits in an
  // optimal set.

  float bound(node u, int n, const int p[ ], const int w[ ], int W);
}

#endif

 

• knapsack_bestfs.cpp

// File: knapsack_bestfs.cpp
#include <cassert> // Provides assert
#include <iostream> // Provides cout and endl
#include <iomanip>
#include "knapsack_bestfs.h"
using namespace std;

namespace algorithms
{
  void knapsack3(int n, const int p[ ], const int w[ ], int W, int& maxprofit)
  {
    int prm_node_cnt = 0; // The number of promising nodes
    int nprm_node_cnt = 0; // The number of non-promising nodes
    priority_queue PQ;
    node u, v;

    assert(PQ.is_empty( )); // Initialize PQ to be empty.
    v.level = 0; v.profit = 0; v.weight = 0; // Initialize v to be the root.
    maxprofit = 0;
    v.bound = bound(v, n, p, w, W);
    PQ.insert(v);

    while (!PQ.is_empty( ))
    {
      v = PQ.get_front( ); // Remove node with best bound.

      cout << "level: "  << setw(1) << v.level  << setw(10)
           << "profit: " << setw(2) << v.profit << setw(10)
           << "weight: " << setw(2) << v.weight << setw(10)
           << "bound: "  << setw(2) << v.bound  << endl;

      if (v.bound > maxprofit) // Check if node is still promising.
      {
        // Set u to the child that includes the next item.
        u.level = v.level + 1;
        u.weight = v.weight + w[u.level];
        u.profit = v.profit + p[u.level];

        if (u.weight <= W && u.profit > maxprofit)
          maxprofit = u.profit;

        u.bound = bound(u, n, p, w, W);

        if (u.bound > maxprofit)
          PQ.insert(u);
        else
        {
          // Count the number of non-promising nodes
          ++nprm_node_cnt;
        }

        // Set u to the child that does not include the next item.
        u.weight = v.weight;          
        u.profit = v.profit;            
        u.bound = bound(u, n, p, w, W);

        if (u.bound > maxprofit)
          PQ.insert(u);
        else
        {
          // Count the number of non-promising nodes
          ++nprm_node_cnt;
        }

        // Count the number of promising nodes
        ++prm_node_cnt;   
      }
      else
      {
        // Count the number of non-promising nodes
        ++nprm_node_cnt;
      }
    }
    cout << endl << "The number of promising node: " << prm_node_cnt << endl;
    cout << "The number of non-promising node: " << nprm_node_cnt << endl;
  }

  float bound(node u, int n, const int p[ ], const int w[ ], int W)
  {
    int j, 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)
      {
        // Grab as many items as possible.
        totweight = totweight + w[j];
        result = result + p[j];
        ++j;
      }
      k = j; // Use k for consistency with formula in text.
      if (k <= n) // Grab fraction of kth item.
        result = result + (W - totweight) * (p[k] / w[k]);

      return result;
    }
  }
}

 

• maxtotprofit.cpp

// File: maxtotprofit.cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "knapsack_bestfs.h"
using namespace std;
using namespace algorithms;

const int n = 4;
const int W = 16;
int w[n+1] = {0, 2, 5, 10, 5}; // w[0] is meaningless
int p[n+1] = {0, 40, 30, 50, 10}; // p[0] is meaningless

int main( )
{
  clock_t start, end;
  int maxprofit = 0;

  start = clock( );
  knapsack3(n, p, w, W, maxprofit);
  end = clock( );

  cout << "The answer: " << maxprofit << endl;
  double result = (double)(end-start) / CLOCKS_PER_SEC;
  cout << "Elpased time is: "<< result << " sec." << endl;

  return EXIT_SUCCESS;
}

 

 

Time Complexity Analysis

---

Worst-Case Time Complexity

$\displaystyle O(n) =  1 + 2 + 2^2 + 2^3 + … + 2^n = 2^{(n+1)} - 1 \in \Theta(2^n)$

 

👉 $w_i$를 포함시키느냐 그렇지 않느냐의 두 가지 선택이므로 상태공간트리 내 전체 노드의 수는 최대 $2^{n+1}-1$개가 된다. 최악의 경우 방문하는 노드의 수가 지수이지만, 가지치기를 통해 상태노드의 수를 줄일 수 있기 때문에 최고우선탐색 기법을 사용한 이 알고리즘의 효율은 더 좋을 수 있다.

 

 

Comparing this Algorithm with Other Techniques

Problem	Algorithm Technique	Worst-Case Time Complexity
0-1 Knapsack	Dynamic Programming	$O(min(2^n, nW))$
	Backtracking(depth-first search)	$\Theta(2^{n})$
	Branch-and-Bound(breadth-first search)	$\Theta(2^{n})$
	Branch-and-Bound(best-first search)	$\Theta(2^{n})$

 

Using best-first search, we have checked only 11 nodes, which is 6 less than the number checked using breadth-first search and 2 less than the number checked using depth-first search. A savings of 2 is not very impressive; however, in a large state space tree, the savings can be very significant when the best-first search quickly hones in on an optimal solution. 

 

👉 앞의 예제에서 최고우선탐색을 사용하여 11개의 노드만 확인했는데, 이는 너비우선탐색을 사용하여 확인한 노드 수보다 6개 적고, 깊이 우선탐색을 사용하여 확인한 노드 수보다 2개 적다. 2개의 노드를 절약하는 것은 그다지 인상적이지 않을 수도 있다. 하지만 대규모 상태공간트리에서 최고우선탐색이 최적의 해를 빠르게 찾을 때 그 효과는 매우 클 수 있다.

nW 덕분에 동적계획 알고리즘으로 문제를 해결하는게 더 좋은 것처럼 보일 수 있다. 그러나 깊이우선탐색, 너비우선탐색, 최고우선탐색 알고리즘에서 최악의 경우를 따지면 실제 방문하는 노드의 수를 얼마나 절약했는지 반영이 안되므로, 알고리즘의 상대적인 효율을 이론적으로 분석하기는 어렵다.

 

 

Exercises

---

Use The Breadth-First Search with Branch-and-Bound Pruning algorithm for the 0-1 Knapsack problem to maximize the profit for the following problem instance. Suppose that n = 5, W = 13, and we have the following:

i	$p_i$	$w_i$	$p_i/w_i$
1	$20	2	$10
2	$30	5	$6
3	$35	7	$5
4	$12	3	$4
5	$3	1	$3

 

My Answer

level: 0    profit:  0    weight:  0    bound: 80
level: 1    profit: 20    weight:  2    bound: 80
level: 2    profit: 50    weight:  7    bound: 80
level: 2    profit: 20    weight:  2    bound: 70
level: 3    profit: 55    weight:  9    bound: 70
level: 4    profit: 67    weight: 12    bound: 70
level: 1    profit:  0    weight:  0    bound: 69
level: 3    profit: 50    weight:  7    bound: 65
	
The number of promising node: 6
The number of non-promising node: 7
The answer: 70
Elpased time is: 0.045 sec.