http://www.geeksforgeeks.org/branch-and-bound-set-1-introduction-with-01-knapsack/
http://www.geeksforgeeks.org/branch-and-bound-set-2-implementation-of-01-knapsack/
We can use Backtracking to optimize the Brute Force solution. In the tree representation, we can do DFS of tree. If we reach a point where a solution no longer is feasible, there is no need to continue exploring.
The backtracking based solution works better than brute force by ignoring infeasible solutions. We can do better (than backtracking) if we know the best possible solution subtree rooted with every node. If the best in subtree is worse than current best, we can simply ignore this node and its subtrees. So we compute bound (best solution) for every node and compare the bound with current best solution before exploring the node.
http://www.geeksforgeeks.org/branch-bound-set-3-8-puzzle-problem/
http://www.geeksforgeeks.org/branch-and-bound-set-2-implementation-of-01-knapsack/
Branch and bound is an algorithm design paradigm which is generally used for solving combinatorial optimization problems. These problems typically exponential in terms of time complexity and may require exploring all possible permutations in worst case. Branch and Bound solve these problems relatively quickly.
Given two integer arrays val[0..n-1] and wt[0..n-1] that represent values and weights associated with n items respectively. Find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to Knapsack capacity W.
- A Greedy approach is to pick the items in decreasing order of value per unit weight. The Greedy approach works only for fractional knapsack problem and may not produce correct result for 0/1 knapsack.
- We can use Dynamic Programming (DP) for 0/1 Knapsack problem. In DP, we use a 2D table of size n x W. The DP Solution doesn’t work if item weights are not integers.
// Returns the maximum value that can be put in a knapsack of capacity W static int knapSack(int W, int wt[], int val[], int n) { int i, w; int K[][] = new int[n+1][W+1]; // Build table K[][] in bottom up manner for (i = 0; i <= n; i++) { for (w = 0; w <= W; w++) { if (i==0 || w==0) K[i][w] = 0; else if (wt[i-1] <= w) K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); else K[i][w] = K[i-1][w]; } } return K[n][W]; } // Returns the maximum value that can be put in a knapsack of capacity W static int knapSack(int W, int wt[], int val[], int n) { // Base Case if (n == 0 || W == 0) return 0; // If weight of the nth item is more than Knapsack capacity W, then // this item cannot be included in the optimal solution if (wt[n-1] > W) return knapSack(W, wt, val, n-1); // Return the maximum of two cases: // (1) nth item included // (2) not included else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1) ); }- Since DP solution doesn’t alway work, a solution is to use Brute Force. With n items, there are 2n solutions to be generated, check each to see if they satisfy the constraint, save maximum solution that satisfies constraint. This solution can be expressed as tree.
The backtracking based solution works better than brute force by ignoring infeasible solutions. We can do better (than backtracking) if we know the best possible solution subtree rooted with every node. If the best in subtree is worse than current best, we can simply ignore this node and its subtrees. So we compute bound (best solution) for every node and compare the bound with current best solution before exploring the node.
Branch and bound is very useful technique for searching a solution but in worst case, we need to fully calculate the entire tree. At best, we only need to fully calculate one path through the tree and prune the rest of it.
http://www.geeksforgeeks.org/branch-and-bound-set-2-implementation-of-01-knapsack/
How to find bound for every node for 0/1 Knapsack?
The idea is to use the fact that the Greedy approach provides the best solution for Fractional Knapsack problem. So if we compute the solution assuming that fractions are allowed, we can get a bound using Greedy approach.
The idea is to use the fact that the Greedy approach provides the best solution for Fractional Knapsack problem. So if we compute the solution assuming that fractions are allowed, we can get a bound using Greedy approach.
Complete Algorithm:
- Sort all items in decreasing order of ratio of value per unit weight so that an upper bound can be computed using Greedy Approach.
- Initialize maximum profit, maxProfit = 0
- Create an empty queue, Q.
- Create a dummy node of decision tree and enqueue it to Q. Profit and weight of dummy node are 0.
- Do following while Q is not empty.
- Extract an item from Q. Let the extracted item be u.
- Compute profit of next level node. If the profit is more than maxProfit, then update maxProfit.
- Compute bound of next level node. If bound is more than maxProfit, then add next level node to Q.
- Consider the case when next level node is not considered as part of solution and add a node to queue with level as next, but weight and profit without considering next level nodes.
Input:
// First thing in every pair is weight of item
// and second thing is value of item
Item arr[] = {{2, 40}, {3.14, 50}, {1.98, 100},
{5, 95}, {3, 30}};
Knapsack Capacity W = 10
Output:
The maximum possible profit = 235
Below diagram shows illustration. Items are
considered sorted by value/weight.
This image is adopted from here.
// Stucture for Item which store weight and corresponding// value of Itemstruct Item{ float weight; int value;};// Node structure to store information of decision// treestruct Node{ // level --> Level of node in decision tree (or index // in arr[] // profit --> Profit of nodes on path from root to this // node (including this node) // bound ---> Upper bound of maximum profit in subtree // of this node/ int level, profit, bound; float weight;};// Comparison function to sort Item according to// val/weight ratiobool cmp(Item a, Item b){ double r1 = (double)a.value / a.weight; double r2 = (double)b.value / b.weight; return r1 > r2;}// Returns bound of profit in subtree rooted with u.// This function mainly uses Greedy solution to find// an upper bound on maximum profit.int bound(Node u, int n, int W, Item arr[]){ // if weight overcomes the knapsack capacity, return // 0 as expected bound if (u.weight >= W) return 0; // initialize bound on profit by current profit int profit_bound = u.profit; // start including items from index 1 more to current // item index int j = u.level + 1; int totweight = u.weight; // checking index condition and knapsack capacity // condition while ((j < n) && (totweight + arr[j].weight <= W)) { totweight += arr[j].weight; profit_bound += arr[j].value; j++; } // If k is not n, include last item partially for // upper bound on profit if (j < n) profit_bound += (W - totweight) * arr[j].value / arr[j].weight; return profit_bound;}// Returns maximum profit we can get with capacity Wint knapsack(int W, Item arr[], int n){ // sorting Item on basis of value per unit // weight. sort(arr, arr + n, cmp); // make a queue for traversing the node queue<Node> Q; Node u, v; // dummy node at starting u.level = -1; u.profit = u.weight = 0; Q.push(u); // One by one extract an item from decision tree // compute profit of all children of extracted item // and keep saving maxProfit int maxProfit = 0; while (!Q.empty()) { // Dequeue a node u = Q.front(); Q.pop(); // If it is starting node, assign level 0 if (u.level == -1) v.level = 0; // If there is nothing on next level if (u.level == n-1) continue; // Else if not last node, then increment level, // and compute profit of children nodes. v.level = u.level + 1; // Taking current level's item add current // level's weight and value to node u's // weight and value v.weight = u.weight + arr[v.level].weight; v.profit = u.profit + arr[v.level].value; // If cumulated weight is less than W and // profit is greater than previous profit, // update maxprofit if (v.weight <= W && v.profit > maxProfit) maxProfit = v.profit; // Get the upper bound on profit to decide // whether to add v to Q or not. v.bound = bound(v, n, W, arr); // If bound value is greater than profit, // then only push into queue for further // consideration if (v.bound > maxProfit) Q.push(v); // Do the same thing, but Without taking // the item in knapsack v.weight = u.weight; v.profit = u.profit; v.bound = bound(v, n, W, arr); if (v.bound > maxProfit) Q.push(v); } return maxProfit;}
e) tree.
In this solution, successive moves can take us away from the goal rather than bringing closer. The search of state space tree follows leftmost path from the root regardless of initial state. An answer node may never be found in this approach.
2. BFS (Brute-Force)
We can perform a Breadth-first search on state space tree. This always finds a goal state nearest to the root. But no matter what the initial state is, the algorithm attempts the same sequence of moves like DFS.
We can perform a Breadth-first search on state space tree. This always finds a goal state nearest to the root. But no matter what the initial state is, the algorithm attempts the same sequence of moves like DFS.
3. Branch and Bound
The search for an answer node can often be speeded by using an “intelligent” ranking function, also called an approximate cost function to avoid searching in sub-trees that do not contain an answer node. It is similar to backtracking technique but uses BFS-like search.
The search for an answer node can often be speeded by using an “intelligent” ranking function, also called an approximate cost function to avoid searching in sub-trees that do not contain an answer node. It is similar to backtracking technique but uses BFS-like search.
There are basically three types of nodes involved in Branch and Bound
1. Live node is a node that has been generated but whose children have not yet been generated.
2. E-node is a live node whose children are currently being explored. In other words, an E-node is a node currently being expanded.
3. Dead node is a generated node that is not to be expanded or explored any further. All children of a dead node have already been expanded.
1. Live node is a node that has been generated but whose children have not yet been generated.
2. E-node is a live node whose children are currently being explored. In other words, an E-node is a node currently being expanded.
3. Dead node is a generated node that is not to be expanded or explored any further. All children of a dead node have already been expanded.
