1. The question is proposed 1.1 "Huayong Road" Introduction "Hua Long Road" is an ancient Chinese intelligence game toy, in a rectangular box of 4, long 5, including a piece of chess, including a Cao Cao, Wuhu The gathering, four smalles, asks to move in the case where the individual papers do not overlap, and most will move Cao Cao from the top of the chessboard to the center as success. Since the five-member general can be placed, there are many arrangements, so it can form a very complex chess game. People also have a lot of nice names to commonly used chess bodies, such as the picture of "Horizontal Trojan" Fig.
Figure 1.1 "Horidal Tree Rapid" layout
Solving methods for this issue, there are now many articles in detail, this article is no longer described, specifically discussed against the "Parental Priority Algorithm" mode. 1.2 Scenary Priority Algorithm We know that for problems similar to "Hua Rong Road", such as maze problems, etc., can be concatenated as the traversal and shortest path problems in the map. That is, since a specific state begins as the starting point of the figure, every step of coming out of any one step as the extension of this node, as long as the state that is out is not repeated each time, it can be Traversing all states that may arrive from this original state, thereby forming a completely inverted tree, as shown below.
Figure 1.2 Schematic of state transformation
For the "Huaying Road" problem, the essence is how to quickly build a state tree map, and if the data volume is unknown, the final result is guaranteed quickly. To do this, there are many algorithms, and the breadth is preferred to be a more popular algorithm. The specific idea is: starting from the starting point, first build the node of the first layer, then build a second layer, third layer nodes, in the construction process, in order to ensure that the data does not repeat, you need to have each new node and It turns out that all nodes that have been generated are compared to ensure that they do not repeat them in the figure. The problem is therefore generated. Since the new node needs to be compared to all nodes each time it is added to ensure that this node does not repeat, with the increase of nodes, the comparison of each need is increasing, This needs a large amount of time for a comparison state to be repeated, thereby forming a bottleneck of algorithm efficiency. This is also an important reason why some people think the efficiency of breadth priority algorithms. Here's how to optimize the breadth priority algorithm to improve efficiency. 2. Optimization of the Guangsheng Priority Algorithm We now assume a shortest path from the starting point status to the final result state, then we will apparently get the following inference: every specific state from the start point to this shortest path, The path taken is the shortest path for this node state. That is, we have to find the shortest path from the starting point to the end, only can be obtained by the shortest path to each node. We now give each of the nodes, which are indicated on the minimum number of paths, forming a node status tree with path steps as the following figure.
Figure 2. 1 Status tree map with the shortest path step
In combination, we can easily get the following conclusions: in the shortest path tree map, the node connected to the node of any level N, which is inevitably between [N-1, N 1]. (Conclusion 1) Then, from the node of one level N, all of the nodes obtained, the level can only be between (N-1, N 1). Therefore, the following conclusions are obtained: whether to determine if the node generated from a node of one original level is already in the figure, only the node collection in the [N-1, N 1] level in the figure needs to have this node. That is, if not, then this node is a new node. (Conclusion 2) Please note the conclusions described above. According to the conclusions 2, only the judgment problem is repeated for the new generated node, only needs to be traced to the upper diode from the level node, without having to go back to the most Start node. In this way, we have achieved optimization purposes for the breadth priority algorithm by narrowing the scope of the newly generated node. 3, conclusion
During the search process of the breadth priority algorithm, if search according to the rules of the shortest path, then for each search generated, only the new node status is repeated, so that the new node status is repeated. To achieve the purpose of fast search. This optimization of the breadth priority algorithm can also be used for solving other similar problems, such as "eight queen problems", maze walking problem, shortest traffic route issues, etc.
