Article directory
- How to understand “backtracking algorithm”?
- Classic applications of two backtracking algorithms
-
- 0-1 backpack
- regular expression
How to understand “backtracking algorithm”?
Generally speaking, backtracking algorithms are often used in problems such as “search”. However, the search mentioned here does not refer in a narrow sense to the graph search algorithm we talked about before, but to search for a solution that meets expectations among a set of possible solutions.
The processing idea of backtracking is somewhat similar to enumeration search. We enumerate all solutions and find the one that satisfies our expectations. In order to regularly enumerate all possible solutions and avoid omissions and duplications, we divide the problem-solving process into multiple stages. At each stage, we will face a fork in the road. We first choose a path at random. When we find that this path does not work (does not meet the expected solution), we go back to the previous fork in the road and choose another path. Keep walking.
Theoretical stuff is still too abstract and old-fashioned, so I’ll give an example. Let me give you a classic example of backtracking. I think you may have guessed it, which is the Eight Queens problem.
We have an 8×8 chessboard, and we want to put 8 chess pieces (queens) on it. Each chess piece cannot have another chess piece in the row, column, or diagonal. You can look at the pictures I drew. The first picture is a method that meets the conditions, and the second picture does not meet the conditions. The Eight Queens Problem is to find all ways to place chess pieces that meet this requirement.
We divide this problem into 8 stages, and place the 8 chess pieces on the first row, the second row, the third row… and the eighth row. During the placement process, we constantly check whether the current method meets the requirements. If it is satisfied, jump to the next line and continue placing the pieces; if it is not satisfied, then try another method and continue trying.
The backtracking algorithm is very suitable to be implemented with recursive code, so I translated the Eight Queens algorithm into code. I have added detailed comments to the code, you can compare it. If you have not come across the Eight Queens problem before, it is recommended that you implement it yourself in a familiar programming language. This is very helpful for you to understand the idea of backtracking.
int[] result = new int[8];//Global or member variable, the subscript indicates the row, and the value indicates which column the queen is stored in
public void cal8queens(int row) {<!-- --> // Calling method: cal8queens(0);
if (row == 8) {<!-- --> // All 8 chess pieces are placed, print the result
printQueens(result);
return; // 8 rows of chess pieces have been placed, and there is no way to recurse further, so return
}
for (int column = 0; column < 8; + + column) {<!-- --> // Each row has 8 middle placement methods
if (isOk(row, column)) {<!-- --> // Some placement methods do not meet the requirements
result[row] = column; //The chess piece in row row is placed in column column
cal8queens(row + 1); // Examine the next row
}
}
}
private boolean isOk(int row, int column) {<!-- -->// Determine whether the placement of row column is appropriate
int leftup = column - 1, rightup = column + 1;
for (int i = row-1; i >= 0; --i) {<!-- --> // Examine each row up row by row
if (result[i] == column) return false; // Is there a chess piece in column of row i?
if (leftup >= 0) {<!-- --> // Examine the upper left diagonal: Are there chess pieces in row i and column leftup?
if (result[i] == leftup) return false;
}
if (rightup < 8) {<!-- --> // Examine the upper right diagonal: Are there chess pieces in row i and rightup column?
if (result[i] == rightup) return false;
}
--leftup; + + rightup;
}
return true;
}
private void printQueens(int[] result) {<!-- --> // Print out a two-dimensional matrix
for (int row = 0; row < 8; + + row) {<!-- -->
for (int column = 0; column < 8; + + column) {<!-- -->
if (result[row] == column) System.out.print("Q ");
else System.out.print("* ");
}
System.out.println();
}
System.out.println();
}
Classic applications of two backtracking algorithms
The theoretical knowledge of backtracking algorithms is easy to understand. However, for novices, the more difficult thing is to implement it using recursion. Therefore, let us practice the application and implementation of the backtracking algorithm through two more examples.
0-1 Backpack
0-1 knapsack is a very classic algorithm problem, and many scenarios can be abstracted into this problem model. The classic solution to this problem is dynamic programming, but there is also a simple but less efficient solution, which is the backtracking algorithm we are talking about today.
There are many variations of the 0-1 knapsack problem, and I will introduce a more basic one here. We have a backpack, and the total carrying weight of the backpack is Wkg. Now we have n items, each of which has a different weight and is indivisible. We now want to select a few items and load them into our backpack. How to maximize the total weight of items in a backpack without exceeding the weight that the backpack can carry?
In fact, we have already talked about the knapsack problem in the greedy algorithm section, but the items mentioned there can be divided, and I can put part of an item into the backpack. In the knapsack problem we are talking about today, items are inseparable and can either be loaded or not, so it is called the 0-1 knapsack problem. Obviously, this problem cannot be solved by greedy algorithm. Let’s now take a look at how to solve it using the backtracking algorithm.
For each item, there are two options, put it in the backpack or not put it in the backpack. For n items, there are 2n ways of loading them. Remove those with a total weight exceeding Wkg, and select the one with a total weight closest to Wkg from the remaining loading methods. However, how can we exhaustively enumerate these 2n ways of pretending without repetition?
Here you can use the backtracking method. We can arrange the items in order, and the whole problem is decomposed into n stages, and each stage corresponds to how to choose an item. Process the first item first, choose to load it or not, and then process the remaining items recursively. It’s difficult to describe. If we look at the code directly, it will be clearer.
A little search pruning technique is also used here, that is, when we find that the weight of the selected item exceeds Wkg, we stop continuing to detect the remaining items. You can see the specific code I wrote.
public int maxW = Integer.MIN_VALUE; //Storage the maximum value of the total weight of items in the backpack
// cw represents the sum of the weights of the items currently loaded; i represents which item has been inspected;
// w backpack weight; items represents the weight of each item; n represents the number of items
// Assume that the backpack can bear a weight of 100, the number of items is 10, and the weight of the items is stored in the array a, then the function can be called like this:
// f(0, 0, a, 10, 100)
public void f(int i, int cw, int[] items, int n, int w) {<!-- -->
if (cw == w || i == n) {<!-- --> // cw==w means full; i==n means all items have been inspected
if (cw > maxW) maxW = cw;
return;
}
f(i + 1, cw, items, n, w);
if (cw + items[i] <= w) {<!-- -->// When the weight has exceeded the weight that the backpack can bear, don’t load it anymore
f(i + 1,cw + items[i], items, n, w);
}
}
Regular expression
Among regular expressions, the most important thing is wildcards. Wildcards combined together can express very rich semantics. For the convenience of explanation, I assume that the regular expression only contains the two wildcard characters “” and “?”, and slightly change the semantics of these two wildcard characters. Among them, “” matches any number of (greater than or equal to 0) any characters, “?” matches zero or one any character. Based on the above background assumptions, let’s see how to use the backtracking algorithm to determine whether a given text matches a given regular expression?
We examine each character in the regular expression in turn. When it is a non-wildcard character, we directly match the characters of the text. If they are the same, we continue processing; if they are different, we backtrack.
If we encounter special characters, we have a variety of processing methods, which are so-called forks in the road. For example, “*” has multiple matching schemes that can match any character in the text string. We will choose randomly first. A matching scheme and then continue looking at the remaining characters. If we find that we can no longer match, we will return to this fork in the road, choose a new matching scheme, and then continue to match the remaining characters.
With the previous foundation, will this problem become much easier to understand? I have translated this process into code. You can read it together, which should help you understand.
public class Pattern {<!-- -->
private boolean matched = false;
private char[] pattern; // regular expression
private int plen; //regular expression length
public Pattern(char[] pattern, int plen) {<!-- -->
this.pattern = pattern;
this.plen = plen;
}
public boolean match(char[] text, int tlen) {<!-- --> // Text string and length
matched = false;
rmatch(0, 0, text, tlen);
return matched;
}
private void rmatch(int ti, int pj, char[] text, int tlen) {<!-- -->
if (matched) return; // If it has been matched, do not continue the recursion
if (pj == plen) {<!-- --> // The regular expression has reached the end
if (ti == tlen) matched = true; // The text string has also come to the end
return;
}
if (pattern[pj] == '*') {<!-- --> // * matches any number of characters
for (int k = 0; k <= tlen-ti; + + k) {<!-- -->
rmatch(ti + k, pj + 1, text, tlen);
}
} else if (pattern[pj] == '?') {<!-- --> // ? matches 0 or 1 characters
rmatch(ti, pj + 1, text, tlen);
rmatch(ti + 1, pj + 1, text, tlen);
} else if (ti < tlen & amp; & amp; pattern[pj] == text[ti]) {<!-- --> // Only pure character matching will work
rmatch(ti + 1, pj + 1, text, tlen);
}
}
}