This article has participated in the third “topic writing” track of the Denver Creators Training Camp. For details, check out: Digg Project | Creators Training Camp third is ongoing, “write” to make a personal impact.
Similar to backtracking algorithm, it is also an algorithm to search the solution of the problem on the solution space tree T, but in general, the branch node demarcation algorithm and backtracking algorithm have different solving objectives. The solution of the backtracking method is to find all the solutions in T that satisfy the constraints, while the solution goal of the branch bound method is to find a solution that satisfies the constraints, or to find the solution that reaches the maximum or minimum value of a certain objective function, that is, the optimal solution in a certain sense.
The so-called “branch” is to adopt the breadth-first strategy, search all branches of e-node at one time, namely adjacent nodes, discard the nodes that do not meet the constraint conditions, and add the remaining nodes to the live node table. Then select the node from the table as the next e-node and continue the search.
There are several different branch search methods depending on how a node is selected:
- FIFO search
- LIFO search
- Priority queue search
The basic idea
Because of the different objective of solution, the search methods of branch bound method and backtracking method in solution space tree T are different. The backtracking method searches the space tree T in a depth-first manner, while the branch-bound rule searches the solution space tree T in a breadth-advance or minimum-consumption first manner.
The branch-bound method searches the solution space tree of the problem in a breadth-first or minimum-cost (maximum-benefit) -first way. The spatial tree of a problem is a word order tree which represents the solution space of a problem, including subset tree and sorting tree. When searching the solution space tree of the problem, the branch bound method and the backtracking method use different ways to expand the current node. In the branch-bound method, each live node has only one chance to become an extended node. Once an active node becomes an extended node, all of its children are created at once. Among these child nodes, which lead to the feasible solution or the sub-optimal solution is discarded, and the remaining child nodes are added to the live node. After that, the next node is removed from the active node to become the extension node of the current node, and the above node expansion process is repeated. This process continues consistently until the solution is found or the table of live nodes is empty.
When searching for a node to estimate the target solution, in determining whether can search down (select node to search the minimum loss) on the branch node, respectively to estimate in advance each son along its node down the path of the search, the objective function may obtain boundaries, then it must save node and they may obtain boundary to the son in a node list, Then select the smallest or largest node from the table to search down, generally using the priority queue to maintain this table.
Case analysis
There are 5 goods, the weight is 8,16,21,17,12 and the value is 8,14,16,11,7. The carrying weight of the backpack is 37. As shown in the following table:
| * * * * items | Weight (W) | Value (v) | Value/Weight (V/W) |
|---|---|---|---|
| 1 | 8 | 8 | 1 |
| 2 | 16 | 14 | 0.875 |
| 3 | 21 | 16 | 0.762 |
| 4 | 17 | 11 | 0.64 |
| 5 | 12 | 7 | 0.583 |
Problem analysis
First, the input data is preprocessed to rank items in order of their value per unit weight. In the priority queue branch bound method described below, the priority of the node is the sum of the value of the bagged item plus the value of the remaining maximum unit weight value of the item filled with remaining capacity.
The algorithm first checks the feasibility of the left son of the current extension node. If the left son node is a viable node, it is added to the subset tree and the slip-node priority queue. The right son of the current extension node must be a feasible node. Only when the right son satisfies the upper bound constraint can it be added to the subset tree and the priority queue of the active node. Is the optimal value of the problem when extended to leaf nodes.
Code implementation
package cn.zhengsh.t;
import java.util.PriorityQueue;
// Define the parameters in the node and the priority setting object
class ThingNode implements Comparable<ThingNode> {
int weight;// The current weight of the node in the backpack
double value;// The current total value of this node in the backpack
double upProfit;// The upper bound on the value that this node can achieve
int left; // Whether this node belongs to the left node (used to construct the optimal solution eventually)
int level; // This object is a selection of items
ThingNode father; // The parent of this node
public int compareTo(ThingNode node) {
return Double.compare(node.upProfit, this.upProfit);
}
public ThingNode(a) {}public ThingNode(int weight, double value, double upProfit, int left, int level, ThingNode father) {
this.weight = weight;
this.value = value;
this.upProfit = upProfit;
this.left = left;
this.level = level;
this.father = father; }}public class Bag01 {
int n = 5;
int capacity = 37;
// It has been sorted by value
int[] weight = {8.16.21.17.12};
double[] value = {8.14.16.11.7};
int maxValue = 0;
int[] bestWay = new int[n];
public void getMaxValue(a) {
PriorityQueue<ThingNode> pq = new PriorityQueue<>();
// Construct an initialization node, belonging to layer -1
ThingNode initial = new ThingNode();
initial.level = -1;
initial.upProfit = 26;
pq.add(initial);
while(! pq.isEmpty()) { ThingNode fatherNode = pq.poll();// When a leaf node has been searched
if (fatherNode.level == n - 1) {
if (fatherNode.value > maxValue) {
maxValue = (int) fatherNode.value;
for (int i = n - 1; i >= 0; i--) { bestWay[i] = fatherNode.left; fatherNode = fatherNode.father; }}}else {
// Collect information about the left node to determine whether the node is added to the queue.
if (weight[fatherNode.level + 1] + fatherNode.weight <= capacity) {
ThingNode newNode = new ThingNode();
newNode.level = fatherNode.level + 1;
newNode.value = fatherNode.value + value[fatherNode.level + 1];
newNode.weight = weight[fatherNode.level + 1] + fatherNode.weight;
newNode.upProfit = bound(newNode);
newNode.father = fatherNode;
newNode.left = 1;
if (newNode.upProfit > maxValue)
pq.add(newNode);
}
// Search for the right node and subtract the value of this layer item from the upper bound of the parent node.
if ((fatherNode.upProfit - value[fatherNode.level + 1]) > maxValue) {
ThingNode newNode2 = new ThingNode();
newNode2.level = fatherNode.level + 1;
newNode2.value = fatherNode.value;
newNode2.weight = fatherNode.weight;
newNode2.father = fatherNode;
newNode2.upProfit = fatherNode.upProfit - value[fatherNode.level + 1];
newNode2.left = 0; pq.add(newNode2); }}}}// Used to calculate the upper bound of the maximum value of this node
public double bound(ThingNode node) {
double maxLeft = node.value;
int leftWeight = capacity - node.weight;
int templevel = node.level;
// Try to pack the rest in order of value per unit weight
while (templevel <= n - 1 && leftWeight > weight[templevel]) {
leftWeight -= weight[templevel];
maxLeft += value[templevel];
templevel++;
}
// If not, use the unit weight value of the next item to convert to the remaining space.
if (templevel <= n - 1) {
maxLeft += value[templevel] / weight[templevel] * leftWeight;
}
return maxLeft;
}
public static void main(String[] args) {
Bag01 b = new Bag01();
b.getMaxValue();
System.out.println("The maximum value that can be obtained from the backpack is :" + b.maxValue);
System.out.println("The method of removal is :");
for (int i : b.bestWay)
System.out.print(i + ""); }}Copy the codeCommon scenarios
- 0/1 knapsack problem
- Single source shortest path problem
- Optimal loading problem
- Single source shortest path problem
- Maximum clique problem
- Travel agent problem
- Circuit board arrangement problem
Refer to the link
- zhuanlan.zhihu.com/p/72734494
- www.jianshu.com/p/c738c8262…
- www.kancloud.cn/qiaodong/da…
- itpcb.com/a/67759