The article directories

      • What is backtracking
      • The efficiency of backtracking
      • Problems solved by retrospective Method (Five types of questions)
      • How to understand backtracking
      • Backtracking template
      • conclusion

Although the backtracking method is difficult, the backtracking method is the violent solution + pruning operation backtracking is the brute force cracking, the core competitiveness of a good backtracking algorithm lies in pruning operation, constantly optimize the efficiency of the whole brute force cracking

What is backtracking

Backtracking can also be called backtracking search, which is a way of searching.

We’ve talked about backtracking more than once in the binary tree series, for example, binary trees: the idea of using recursion is to hide backtracking.

Backtracking is a by-product of recursion, and as long as there is recursion there will be backtracking.

So in the following lectures, backtracking functions, also known as recursive functions, refer to the same function.

The efficiency of backtracking

What is the performance of backtracking? Here I want to make it clear to you that “although backtracking is difficult and difficult to understand, it is not an efficient algorithm”.

“Because the essence of backtracking is exhaustion, exhaustion of all possibilities, and then choose the answer we want.” If you want to make backtracking more efficient, you can add some pruning operations, but it cannot change the essence of backtracking is exhaustion.

So why use backtracking if it’s not efficient?

Because there is no choice, some problems can be found out by violence is good, dead and then prune, there is no more efficient solution. At this time we should be curious, what are the problems, so cattle force, can only be violent search.

Problems solved by retrospective Method (Five types of questions)

Retrospective method can generally solve the following problems:

  1. Combination problem: N numbers in accordance with certain rules to find the set of k numbers
  2. Slicing problem: A string can be sliced in several ways according to certain rules
  3. Subset problem: how many subsets of a set of N numbers are eligible
  4. Permutation problem: N number permutation according to certain rules, there are several permutations
  5. Checkerboard problems: N queen, solving sudoku and so on

“I believe that after looking at these, you will find that every problem is not simple!”

In addition, some students may be confused about what is a combination, what is permutation?

“Composition does not emphasize the order of elements; permutation emphasizes the order of elements.”

For example, {1, 2} and {2, 1} are sets in combination, because order is not emphasized, and {1, 2} and {2, 1} are two sets in permutation.

Remember to mix out of order, arrange in order, that’s it.

How to understand backtracking

“All problems solved by backtracking can be abstracted into a tree structure.” Yes, I mean all backtracking problems can be abstracted into a tree structure!

Since backtracking is all about recursively finding subsets in a set, “the size of the set constitutes the width of the tree, and the depth of the recursion constitutes the depth of the tree”.

Recursion must have termination conditions, so it must be a tree of finite height (n-fork tree).

This might be a little bit confusing for beginners, but I’m going to emphasize this and draw some examples for all of the problems that the backtracking algorithm solves, just to give you an idea.

Backtracking template

The backtracking algorithm template is as follows:

In the recursion of binary trees, we talked about the recursion trilogy, and I’m going to give you the back trilogy.

First, traceback the function template return values and parameters (as in the first of the three recursive steps)

In the backtracking algorithm, my habit is to call the function backtracking, which is arbitrary.

In the backtracking algorithm, the return value of the function is usually void.

Parameters: Because the parameters required by backtracking algorithm are not as easy to determine as the binary tree recursion, it is generally written logic first, and then fill in whatever parameters are needed.

But as we go back to the problem, just to make it easier for you to understand, I’m going to help you define the parameters at the beginning.

The pseudocode of the traceback function is as follows:

Void Backtracking (parameter)Copy the code

Second, the termination condition of the backtrace function (as in the second of the previous three recursive steps)

And since it’s a tree, when we were doing recursion for binary trees, we knew that traversing a tree must have termination conditions.

So backtracking also has termination conditions.

When the termination condition is reached, you can see from the tree that, in general, you’ve found a leaf node, you’ve found an answer that satisfies the condition, you store that answer, and you end the recursion at this level.

So the termination condition pseudocode of the backtracking function is as follows:

if(Termination condition) {Store result;return;
}
Copy the code

Third, the traversal process of backtracking search (the same as the second step in the previous three recursive steps) was mentioned above, backtracking usually recurses in the set, the size of the set constitutes the width of the tree, and the depth of the recursion constitutes the depth of the tree.

As shown in figure:

Notice that IN this picture, I specifically gave the example that the collection size is equal to the number of children!

The pseudo-code of the backtracking function traversal process is as follows:

for(Select: elements in this layer's collection (the number of children of nodes in the tree is the size of the collection)) {process nodes; Backtracking (path, select list); // undo the result of recursive backtracking}Copy the code

A for loop is a loop that iterates through the set interval, and you can understand that the for loop is executed as many times as the number of children a node has. Backtracking is just calling itself, doing the recursion.

As you can see from the graph, “for loop can be understood as horizontal traversal, backtracking is vertical traversal,” so that the tree is completely traversed. In general, searching for leaf nodes is one of the results.

After analyzing the process, the template framework of backtracking algorithm is as follows:

Void backtracking(parameter) {if(Termination condition) {Store result;return;
    }

    for(Select: elements in this layer's collection (the number of children of nodes in the tree is the size of the collection)) {process nodes; Backtracking (path, select list); // Recursive backtrace, undo result}}Copy the code

“This template is very important, the title of the backtracking method all depends on it!”

If you have never learned the backtracking algorithm, you will be a little confused when you see this, and you will be better off when you start to explain specific problems. If you have done the backtracking problem, you will feel empathy when you see this.

conclusion

In this video, we looked at what a backtracking algorithm is, and we saw that backtracking and recursion go hand in hand.

Then mentioned the efficiency of backtracking method, backtracking method is actually a violent search, is not an efficient algorithm.

Then it lists several kinds of problems that can be solved by backtracking method. It can be seen that each kind of problem is not simple.

Finally, we said that all the problems solved by backtracking method can be abstracted into tree structure (n-fork tree), and gave the template of backtracking method.

Today is the first day of backtracking algorithm, according to the convention is to outline a wave first, and then to explain the specific topic at the beginning, students who have not been exposed to backtracking method at the beginning of a little confused is normal, and later combined with the specific topic will be better.