Problem description

A salesperson wants to sell goods in four cities. The distance between cities is known, as shown in the right figure.

How should he choose a route starting from city 1, passing through each city and finally returning to city 1, so as to minimize the total travel distance?
Train of thought analysis
Determine the solution space of the problem and express the problem first
 First of all, you must save the input data. For the diagram, use the twodimensional matrix here! Then the traversal starts from the adjacency matrix!
 When we use the tree structure to traverse the graph, it is easy to find that the repeated points do not need to be traversed, and only the first point needs to be traversed repeatedly!
 Therefore, in general, two structures are needed:
 Adjacency matrix to save the corresponding graph structure
 One dimensional matrix to record whether each point is accessed.
According to the requirements of the topic, determine the constraint function and upper bound function

Constraint function: records all the accessed nodes. It is necessary to determine whether the current state is the accessed node!

Upper limit function: determines whether the value of the current status has exceeded the value of the corresponding current completion!
Implementation code and analysis
Using program language representation
Definition of constraint function and upper bound function
//Save the currently known shortest path. Here, first define a maximum value. Once it is smaller than this value, it will be replaced with a smaller value int minPath = 99; //Save the path corresponding to the current state. There are four nodes in total, and you only need to walk four times in total int path[4]; /* Description: the constraint function and upper bound function of travel sales problem ensure that the path is not repeated and the value of the path is the smallest Parameter: m indicates the state of the current problem, which is also the number of layers recursively, and records the location node of M choices pathValue: Indicates the value of the path corresponding to the current state Return: true: indicates that the current node meets the corresponding conditions false: Indicates that the current node does not meet the corresponding conditions Principle: traverse the existing array to see if it will be repeated Compare the saved maximum value for judgment */ bool constrainAndBound(int m,int pathValue){ //Constraint function to check whether the current decision conforms to the status for (int i = 0; i < m; ++i) { if (path[m] == path[i]) { return false; } } //The upper bound function determines whether the current path value is the shortest //If you do not reach the target path, it is longer than the original path. You can exit directly if (m < 3) { pathValue > minPath; return false; } return true; }
Retrospective algorithm review
 Define the solution space of the problem and all cases of the problem, including the optimal solution.
 Determine the solution space structure that is easy to search:
 Subset tree
 Permutation tree
 Determine the constraint function or bound function
 Depth traversal search solution space from root node
Implementation source code
 This problem is a little different, that is, the default is to start from the first node, specify the initial starting point, and formulate a complete cycle. There are five nodes, so the termination condition of traversal should be at the fifth layer.
//The following is the code of travel sales problem //Save the currently known shortest path. Here, first define a maximum value. Once it is smaller than this value, it will be replaced with a smaller value int minPath = 99; //Save the path corresponding to the current state. There are four nodes in total, and you only need to walk four times in total int path[5] = { 0 }; //Define a number of points int placeNum = 4; /* Description: the constraint function and upper bound function of travel sales problem ensure that the path is not repeated and the value of the path is the smallest Parameter: m indicates the state of the current problem, which is also the number of layers recursively, and records the location node of M choices pathValue: Indicates the value of the path corresponding to the current state Return: true: indicates that the current node meets the corresponding conditions false: Indicates that the current node does not meet the corresponding conditions Principle: traverse the existing array to see if it will be repeated Compare the saved maximum value for judgment */ bool constrainAndBound(int m, int pathValue) { //Constraint function to check whether the current decision conforms to the status //Limit the position of node 0 if (m != 4 && path[m] == 0) return false; for (int i = 1; i < m; ++i) { //Restrictions cannot be repeated if (path[m] == path[i]) return false; } //The upper bound function determines whether the current path value is the shortest //Before reaching the key point, it is longer than the shortest path, so it is meaningless if (pathValue > minPath) return false; return true; } /* Description: specific implementation of travel sales problem Parameter: m indicates the depth of corresponding recursion matrix A twodimensional matrix that represents the shape of the corresponding matrix pathValue Indicates the current path length Return: no return value, recursive call Principle: in the process of recursion, generate a tree and traverse the corresponding tree */ void SellPath(int m, int Matrix[4][4], int pathValue) { //The fourth goal is to reach the end of recursion first if (m == 5) { //When the bottom line is reached, directly compare the corresponding length if (pathValue < minPath) minPath = pathValue; //Cout < < the shortest path is: < < minpath < < endl; } else { //If it is not satisfied, it will be traversed recursively, traversing the adjacent points of each location for (int i = 0; i < placeNum; ++i) { //If you traverse to the current state, you should traverse to the node corresponding to the current state //Locate the corresponding row in the twodimensional matrix and traverse to find the node of the current target. if (Matrix[path[m  1]][i] != 0) { //Accumulate the distance pathValue += Matrix[path[m  1]][i]; //Select status to determine whether the current status is legal path[m] = i; int temp = path[m]; //Constraint conditions for judgment if (constrainAndBound(m, pathValue)) { //If the recursion condition is met, recursion will be carried out, and recursion will be carried out in the next direction SellPath(m + 1, Matrix, pathValue); } //If the conditions are not met, the current path is subtracted pathValue = Matrix[path[m1]][i]; } } } } int main(){ cout << "Display of tourism sales problems" << endl; cout << "There are four nodes in total, namely 1, 2, 3 and 4" << endl; cout << "There are 6 sides in total, which are 4, 5, 6, 10, 20 and 30 from low to high" << endl; //Initialize adjacency matrix int nodeNum = 4; int Matrix[4][4]; int pathValue = 0; for (int i = 0; i < nodeNum; ++i) { for (int j = 0; j < nodeNum; ++j) { Matrix[i][j] = 0; } } Matrix[0][1] = 30; Matrix[0][2] = 6; Matrix[0][3] = 4; Matrix[1][0] = 30; Matrix[1][2] = 5; Matrix[1][3] = 10; Matrix[2][0] = 6; Matrix[2][1] = 5; Matrix[2][3] = 20; Matrix[3][0] = 4; Matrix[3][1] = 10; Matrix[3][2] = 20; cout << "The output matrix is as follows:" << endl; for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { cout << Matrix[i][j] << " "; } cout << endl; } SellPath(1, Matrix, pathValue); cout << "The final result is:" << minPath << endl; cout << endl; return 0; }
Problems arising
When traversing, it jumps horizontally between node 1 and node 2 once, so that the final target node can not be found at last
 At the beginning, the first node is node 0 by default, and the last node is node 0 by default. Therefore, it is necessary to add corresponding judgment conditions to the constraint function to limit the location and selection of node 0!
Although there are four nodes here, you have to go through five nodes, starting from 1 and finally returning to 1!
 Therefore, the array recording the recursive state is a onedimensional array with a length of 5, but the traversal starts from the second node, and the first node is 0 by default!
Two things are mainly used, onedimensional matrix to save recursive state and twodimensional matrix to save array information
 Note: the relationship between the above two is different by one state. The recursion option of m state is determined by the recursion option of m1 state
Analysis and summary
 This question has been entangled for a long time, thought a lot, and found many different places! The key is that this problem requires a deep understanding of the problemsolving process and the backtracking process! Because he has many differences, many variants! You should set different conditions to judge according to the situation!
 This question really makes me gain a lot, but my code is not very goodlooking, at least in my opinion, it is messy! And the quality is not high, it should be modified! However, I have invested a lot of time in thinking about the solution, so I don't have time to modify it!
 Please buckle if you have something to do! 651378276! We can learn and make progress together!