Backtracking method is the solution space tree of depth first strategy traversal problem. Branch threshold method by breadth-first strategy solution space tree traversal problems, in the process of traversal for processing each node according to estimate the possible value of target function is cohesive function, choose the target function to extreme value (maximum or minimum) node priority of breadth-first search, so as to constantly adjust the search direction, find the problem as soon as possible.

An overview of the

Dynamic search of solution space tree

Branch bound method firstly determines a reasonable limit function, and then determines the boundary [down,up] of the objective function according to the limit function. Then, according to the breadth-first strategy, the solution space tree of the problem is traversed. On the branch node, all the child nodes of the node are searched once, and the possible values of the objective function of these child nodes are estimated respectively. If the objective function of a child node is likely to obtain a value beyond the bounds of the objective function, it is discarded because the solution generated from a node will not be better than the one already obtained; Otherwise, add it to the table of nodes to be processed (PT for short). The node that causes the value of the objective function to obtain the extreme value is selected from the table PT in turn as the current extension node, and the above process is repeated until the optimal solution is found.

The branch bound method is used to solve the 0/1 problem

  1. Sort items from most to least value per unit weight
  2. Objective function: UB = V + (W-W)*(vi+1/ WI +1), representing the upper limit of value
  3. Starting from item 1, continuously select items to put into the backpack, and check whether the space is appropriate. If the space is appropriate, calculate the objective function and put the node into PT together. Then select the node with the largest objective function from PT and continue selecting items until the result is calculated.

The design idea of branch bound method

Suppose we solve the maximization problem, and the solution vector is X=(x1,x2… , xn), among them, the scope of the xi for a finite set of Si, | Si | = ri (1 < = I < = n). When the branch bound method is used to search the solution space tree of the problem, the bound [down,up] of the objective function is estimated according to the bound function, and then r1 child nodes of the root node are extended from the root node to form r1 possible value modes of the component x1. Bound (x1) = 1 bound(x1) = 1 bound(x1) = 1 bound(x1) = 1 bound(x1) = 1 bound(x1) = 1 bound(x1)

Bound (x1) > = bound (x1, x2) > =… > = bound (x1, x2,… ,xn)

If the objective function value of a child node exceeds the boundary of the objective function, the child node is discarded. Otherwise, save the child node in the pending node table PT. Select the node from table PT that achieves the maximum value of the objective function as the root node of the next expansion, repeat the above process, and get a feasible solution X=(x1,x2… Bound (x1,x2… , xn). If bound (x1, x2,… Select * from PT where x1,x2… ,xn) is the maximum value of the problem, (x1,x2… ,xn) is the optimal solution of the problem; If bound (x1, x2,… ,xn) is not the upper bound of bound(x1,x2… , xn). So, use bound(x1,x2… Down =bound(x1,x2… ,xn), and delete the nodes in the table PT that exceed the lower bound of the objective function down. Then, select the node whose objective function value reaches the maximum value as the root node of the next expansion, and continue the search until the objective function value of a leaf node reaches the maximum value in the table PT.

This design idea tells the essence of branch bound method, you must fully understand.

The key problems of applying branch-bound method are:

  1. How to determine the appropriate bounding function

    The branch bound method estimates the possible value of the objective function of a node according to the bound function in the traversal process, and must design a good bound function.

  2. How do I organize the list of nodes to be processed

    Table PT can be in the form of a heap or a priority queue

  3. How to determine the components of the optimal solution

    • For each extension node, save the path from the root node to that node
    • In the process of search, a tree structure is constructed after the search, and when the optimal solution is obtained, each component of the optimal solution is determined by constantly backtracking from the leaf node to the root node.

Branch bound method in graph problem

The TSP problem

The TSP problem refers to that the traveler has to travel n cities, and is required to experience each city only once, and then return to the starting city, and is required to travel the shortest distance.In general, for a path being generated, assume that the established set of vertices U=(R1, R2… ,rk), that is, k vertices have been determined on the path. In this case, the objective function value decomposed in this part can be calculated as follows:

So the lower limit of lb ((1 + 3) + (3 + 6) + (1 + 2) + (3 + 4) + (2 + 3)) / 2 = 14, ceiling using greedy method, calculates the numerical value is 16, so the threshold function is bound to [dec 14].

Why does the bounding function look like this, because

  1. And it’s easy to calculate, because every point has one out and one in, and when you do it you double it and divide it, it’s easy to calculate
  2. You can figure out the lower bound, if you have an edge (1,3), then the distance between 1 and 3 is fixed, but 1 needs to have an edge that goes out and an edge that comes back, so the lower bound is the smallest other edge, other than the distance to 3.

The problem solving process and pseudocode are as follows:

  1. 107. Hierarchical Traversal of binary Trees II – Simple Code This is the simplest breadth-first traversal, with no bound functions

The shortest path problem of multisegment graph

Let G=(V,E) be a weighted directed connected graph. If the set of vertices V is divided into k disjoint subsets Vi(2<=k<=n,1<= I <=k), such that any edge (u, V) in E must belong to Vi, and V must belong to Vi+ M (1<= I <k,1< I +m<=k), then G is called a multi-segment graph. Say s belongs to V1 as the source point and T belongs to Vk as the end point.

  1. 2+4+5+3=14. The greedy method 0->2->5->8->9 is used in the upper bound. The path cost is 18, so the objective function bound is [14,18].

  2. Suppose segment I has been determined and its path is (R1, R2… ,ri,ri+1), then the limiting function:

The formula means adding up all the links that have been determined, finding the shortest link for the next link, and then adding up each group of shortest edges after that. For example, if the walk (0,1) has been determined, then the objective function is 4(the determined edge)+8(the shortest edge from 1 to 4, 5)+5(the third smallest edge)+3(the fourth smallest edge)

  1. Every time the edge is selected, if the LB exceeds 18, it will be discarded; if it is within the range, it will be put into the minimum heap structure at the lb position. The minimum lb node will be selected each time for breadth-first traversal until the final result is obtained.

Examples:

  1. 815. Bus Routes – Difficulty Code This problem also does not use a bounding function and can be implemented using either depth-first or breadth-first

Branch-bound method in combinatorial problems

Task assignment problem

Task allocation problem requires n tasks to be assigned to N individuals, and the cost of each task is different for each individual. It requires the allocation of the optimal allocation case with the minimum total cost.

  1. The lower bound is the minimum value of each line 2+3+1+4=10. The upper bound uses greedy method to calculate 2+3+5+4=14, so the range is [10,14].

  2. Limit function: Suppose that the task has been assigned to personnel 1~ I and the cost v has been obtained, then the limit function can be defined as:

3. Use breadth-first traversal to calculate the LB. If the LB exceeds the upper bound, it is discarded. If the LB is within the range, it is placed in the smallest heap and the smallest LB is selected for breadth-first traversal each time until all values are calculated.

sample

  1. 690. Importance of Employees – Simple Code This problem also doesn’t use bounding functions or heap sorting. There are fewer examples

Batch job scheduling problems

Given a set of n jobs J={J1,J2… Jn}, each job has 3 tasks to be completed on 3 machines respectively. The processing time of job Ji for machine J is tij(1<= I <=n,1<=j<=3). Each job must be processed by machine 1 first, then by machine 2, and finally by machine 3. The batch job scheduling problem requires the determination of the optimal processing order for the n jobs, so that the minimum time is needed from the beginning of the first job on machine 1 to the end of the optimal job on machine 3.

As an implementation example, execute in order (J2,J3,J1,J4) with a total completion time of 54

In addition, let’s consider a problem. If we start processing with Ji, the shortest estimated processing time is:

This formula is actually very easy to understand, machine 1 starts working, it takes ti1 time, and then machine 2 can do J1, and machine 2 is not idle, it takes the shortest time, and when all the tasks are done on machine 2, the last tasks are done on machine 3. So the shortest time is made up of these three segments.

And if you know that, it’s easy to understand the value of the target function.

For a set of scheduled jobs M is {1,2… , n} subset, | | M = k, which has been arranged for k, set sum1 [k] said machine 1 to complete assignments k processing time, sum2 [k] said machine 2 k the processing time of operation, to deal with the homework now k + 1, at this point, the lower bound for the decomposition of the objective function value calculation method is as follows:

The search process of branch bound method is as follows:

  1. 207. Class Schedule – Medium code

conclusion

Branch bound method also has routine, first confirm the upper and lower bounds, then find out the reasonable limit function, and finally use the breadth-first traversal, sort according to the value calculated by the limit function, and select the minimum/maximum value for the next breadth-first traversal.

Very few of the buckle problems require the use of bounding functions, but some require more skill. The questions in this chapter you can contact, medium difficulty questions are not much of a problem.

The last

If you like my article, you can follow my public account (Programmer Malatang)

My personal blog is shidawuhen.github. IO /

Review of previous articles:

algorithm

  1. Algorithmic learning plan
  2. A brute force method
  3. Divide and conquer method
  4. Reduction treatment
  5. Dynamic programming method
  6. Greedy method
  7. backtracking
  8. Branch bound method
  9. Algorithm is summarized

technology

  1. Service framework and registry for microservices
  2. Beego framework use
  3. Discussion on Micro-service
  4. TCP Performance Optimization
  5. Current limiting implementation 1
  6. Redis implements distributed locking
  7. Golang source BUG tracking
  8. The implementation principle of atomicity, consistency and persistence of transactions
  9. CDN request process details
  10. The story of how blogging services were crushed
  11. Common Cache tips
  12. How to effectively connect with third-party payment
  13. Gin framework concise version
  14. InnoDB locks and transactions

Reading notes

  1. Agile revolution
  2. How to exercise your memory
  3. Simple Logic – After reading
  4. Hot Wind – After reading
  5. Analects of Confucius – After reading
  6. Sun Tzu’s Art of War – Reflections from reading

thinking

  1. Some thoughts on project management
  2. Some thoughts on product manager
  3. Thinking about programmer career development
  4. Thinking about code review
  5. Markdown editor recommends – Typora