Author: Steven
Copyright notice: the copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source
preface
This paper introduces a classical algorithm backtracking method, which can be used as a solution to the maze problem. The following is the main body of this article, including the introduction of the algorithm, the application of the algorithm (maze problem), the algorithm flow and the implementation of C + + code.
Note: the content of this paper refers to graphical algorithm C + +, and integrates some of my own understanding and experience.
1, Introduction to backtracking method
Backtracking is a kind of enumeration method, which can find all or part of the general algorithm and effectively avoid the wrong solution of enumeration. When it is found that the direction of a solution is inaccurate, it will not continue to go down, but go back to the upper layer to reduce the running time of the algorithm. It is commonly known as "go back and change the way if you can't get through". The feature is to find the solution of the problem in the search process. Once it is found that the conditions are not met, it will go back and continue to search other paths to improve efficiency.
2, Algorithm application (maze problem)
1. Problem description
Maze problem is an application of backtracking method. The description of the maze problem is: suppose that the subject (human, animal or aircraft) is placed at the entrance of a maze map, and there are many walls in the maze, so that most of the paths are blocked. The subject can reach the exit by traversing all possible paths to the exit. When the main body takes the wrong path, it is necessary to record the wrong path to avoid taking the repeated path next time until the exit is found. The main body shall follow the following three principles:
- You can only walk one grid at a time;
- When the path is blocked, step back until another path is found to be feasible;
- Record the path you have taken, and you won't take it again.
2. Problem solving ideas
First, create a maze diagram. For example, use a two-dimensional array to artificially define MAZE[row][col]. When MAZE[i][j]=1, it means there is a wall that cannot pass through, and when MAZE[i][j]=0, it means it is feasible. Assuming MAZE[1][1] is the entrance and MAZE[8][10] is the exit, create the following initial maze diagram:
Fig. 1 initial maze
When the main body moves forward in the maze, there are four directions to choose from: Southeast, Northwest (i.e. lower right and upper left), as shown in the following figure:
Fig. 2 # direction diagram
Depending on the situation, not all positions can move up, down, left and right. You can only go where MAZE[i][j]=0. Record the passing position through the linked list, mark it as 2, put the information of this position on the stack, and then select the next direction. If you come to a dead end and don't reach the end, go back to the previous fork and choose another direction to continue. Since the newly added position is at the top of the stack each time, the grid number pointed to by the pointer at the top of the stack is the position of the current subject. Repeat until you reach the exit of the maze.
The maze mentioned in this paper is only a simple version of the maze. For more complex maze problems, we can expand based on this idea or adopt other algorithms.
3, Algorithm flow
Based on the solution idea of maze problem in the second part, the algorithm logic is: start, input the initial entrance position; When the current position x and y are less than the exit x and y, continue to move forward; Judge the feasible direction of southeast, northwest and northwest, and put the stepping position information into the stack of moving path; Check whether it reaches the exit; If the path is blocked, step back (i.e. pop a position from the stack) and check whether there are other paths to go; When the current position x or Y is greater than the exit x and y, the traversal ends and the result is output.
The algorithm flow chart is as follows:
Figure 3 # algorithm flow chart of solving maze problem by backtracking method
4, C + + code implementation
#include < iostream >
// In a two-dimensional array [x][y], X represents a row and Y represents a column
#define EAST MAZE[x][y+1] / / East
#define WEST MAZE[x][y-1] / / west direction
#define SOUTH MAZE[x+1][y] / / South
#define NORTH MAZE[x-1][y] / / North
using namespace std;
const int ExitX = 8; // Exit x coordinate
const int ExitY = 10; // Exit y coordinate
struct list
{
int x, y;
struct list *next;
};
typedef struct list node;
typedef node* link;
int MAZE[10][12] = { 1,1,1,1,1,1,1,1,1,1,1,1, // Maze definition
1,0,0,0,1,1,1,1,1,1,1,1,
1,1,1,0,1,1,0,0,0,0,1,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,1,1,0,0,0,0,1,1,0,1,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,1,1,0,0,0,0,0,1,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1
};
link push(link path, int x, int y);
link pop(link path, int *x, int *y);
int chkExit(int x, int y, int ex, int ey);
link push(link path, int x, int y)
{
link newnode;
newnode = new node;
if (!newnode)
{
cout << "Error:Memory allocation failed!" << endl;
return NULL;
}
newnode->x = x;
newnode->y = y;
newnode->next = path;
path = newnode;
return path;
}
link pop(link path, int *x, int *y)
{
link top;
if (path != NULL)
{
top = path;
path = path->next;
*x = top->x;
*y = top->y;
delete top;
return path;
}
else
*x -= 1;
return path;
}
int chkExit(int x, int y, int ex, int ey)
{
if ((x == ex) && (y = ey))
{
if (NORTH == 1 || SOUTH == 1 || WEST == 1 || EAST == 2)
return 1;
if (NORTH == 1 || SOUTH == 1 || WEST == 2 || EAST == 1)
return 1;
if (NORTH == 1 || SOUTH == 2 || WEST == 1 || EAST == 1)
return 1;
if (NORTH == 2 || SOUTH == 1 || WEST == 1 || EAST == 1)
return 1;
}
return 0;
}
int main(void)
{
cout << endl << endl;
int i, j;
link path = NULL;
int x = 1; // Entrance x coordinate
int y = 1; // Entrance y coordinate
cout << " "<<"Maze diagram (the position of 0 is walkable, and the position of 1 is wall):\n" << endl; // Display map
for (i = 0; i < 10; i++)
{
for (j = 0; j < 12; j++)
cout << " " << MAZE[i][j] << " ";
cout << endl;
}
cout << endl << endl;
// Start the maze
while (x <= ExitX && y <= ExitY)
{
MAZE[x][y] = 2;
if (NORTH == 0)
{
x -= 1;
path = push(path, x, y);
}
else if (SOUTH == 0)
{
x += 1;
path = push(path, x, y);
}
else if (WEST == 0)
{
y -= 1;
path = push(path, x, y);
}
else if (EAST == 0)
{
y += 1;
path = push(path, x, y);
}
else if (chkExit(x, y, ExitX, ExitY) == 1)
break;
else
{
MAZE[x][y] = 2;
path = pop(path, &x, &y);
}
}
cout << "Maze completion diagram (position 0 is not taken, position 1 is the wall, and position 2 is taken):\n" << endl; // Display map
for (i = 0; i < 10; i++)
{
for (j = 0; j < 12; j++)
cout << " " << MAZE[i][j] << " ";
cout << endl;
}
return 0;
}design sketch:
Fig. 4 Effect Drawing
5, Expand
In the 16th Chinese postgraduate mathematical modeling competition of "Huawei Cup" in 2019, the title of F is "rapid path planning of intelligent aircraft under multiple constraints". This problem is similar to a complex maze problem with many constraints, which requires to find an optimal path that meets the constraints. At that time, our team designed a new maze algorithm based on the thinking of constraints and maze algorithm. The algorithm is simply to traverse all feasible paths and judge when reaching the node. If the linear distance from the node to the end plus the distance traveled is less than the shortest feasible path distance found before, Then the path behind the node does not need to go and pass directly. Because of this, the optimal solution process of the algorithm can converge quickly. In the later stage of calculation, it may be known that this path does not meet the requirements before it reaches half. Other teams calculate for hours, while our algorithm takes only half a minute.
The third question is that the probability is not very good. In addition, the energy is poor all night at the end of the game. When recording the data, I made a careless mistake. It's a pity to only take the third grade of the country. Originally, five of the six answers were right and two were carelessly written wrong...
The data of this modeling paper are shared with you: https://download.csdn.net/download/zhaitianbao/16817729
Study hard together, come on. The paper contains matlab code, which is for reference only. The parameter naming is a little messy. Hope Haihan.
summary
The above is the content of this paper. It briefly introduces the backtracking method and a practical application of this method - maze problem, including the problem-solving logic of maze examples and the implementation of C + + code.