-,Problem Description
A number of 8 or 15 issues is the same problem, which is a randomly arranged 8 or 15 numbers to move to a specified target state in a squares grid. Since there is only one space, only the chess pieces near the space can be moved.
Second, the algorithm description
F algorithm selection
This problem requires exhaustion of all possible paths, but due to the increase in the height of the tree, the increase in the increase in the increase in the bullish drama, so it is unrealistic to all sub-nodes. The comparison of the current state and the target state can be used to evaluate the quality of the current state. Here we choose a * algorithm to solve, a * algorithm is a preferred algorithm. F '(n) = g' (n) h '(n), f' (n) is a valuation function, g '(n) is the shortest path value of the starting point to the end point, which means the height of the tree, h' (n) is the inspiration value of the maximum path of N to the target, which is compared to the currently generated state and the evaluation function value of the previous state, and select the minimum evaluation function to continue the next step. Here I choose H '(n) inspiration value for each lattice to reach the minimum number of steps required to pass.
F algorithm description
Requirently needed:
1. Use Openarr to represent the list of initial nodes (to be expanded, this is a dynamic array)
2. Closedarr saves the node that has been accessed
3. The algorithm first needs to give an initial state. Since the status of random production is not necessarily possible to go to the target state, this is used from the standard state to generate an invisible random state, so that it can be guaranteed.
Algorithm implementation:
1. Openarr placement initial node
2. If Openarr is empty set, exit and give failed signals
3. N is taken as the first node of Openarr and remove node N from Openarr n
4. If n is the target node, exit and give a successful signal
5. Otherwise, the n child node will be generated, and each sub-node n 'of N is performed as follows:
1) If n 'is not in Openarr and Closedarr table, put n' into the Openarr table.
2) Otherwise, if the evaluation value is calculated in the Openarr table, and if the value of the evaluation function in the table is small, the evaluation value in the table is the current value.
3) Otherwise, if the evaluation value is calculated in the CloseDarr table, and if the value of the evaluation function in the table is small, the evaluation value in the table is updated to the current value, and the node is removed from the table, and Add this node in the OpenARR table.
6, add N n to Closedarr
7. Sort Openarr (depending on the evaluation function from small to large), and go to 2.
Third, program design
The algorithm is implemented using the C # language. The procedure is mainly implemented in accordance with the description of the breadth priority algorithm provided above. There are four classes in the program:
STEPNODE class, used to describe the properties and methods of each of the resulting nodes, etc.
Heuristic_15num_search class, algorithm implementation class
The Form1 class is the class of interface design.
Here, the solution is provided with a number of problems of the number of numbers. And shows the various state metastasis experienced
The following mainly describes the program implementation of several core algorithms.
// StepNode class The following methods are mainly moving on the left and right movements of the lattice.
// 0 digit
Private void moveup (position p) {if (px> = 1) {step node = new step (); to (this, node); position p1 = new position; addchild (node, p, P1);}} // 0 Digital Double Move PRIVATE VOID MOVEDOWN (PX <= text_v.length-2) {Stepnode Node = New StepNode (); To (this, node); position p1 = new Position (P.X 1, PY); AddChild (Node, P, P1);}}
// 0 Digital left shift private void move (position p) {if (py> = 1) {step node = new stepnode (); to (this, node); position p1 = new position (px, py-1); AddChild (Node, P, P1);}}
// 0 Digital right shift private void Moveright (position p) {if (py <= text_v.length-2) {step node = new step (); to (this, node); position p1 = new position (px, p .y 1); AddChild (Node, P, P1);}}
/ / Calculate the value of the inspiration function of the node private void computegealthGeneval () {int geneval = this.Height; int g = 0; // Inspiration Factor Each data reaches the minimum number of steps that need to go
For (int i = 0; i ) {for (int J = 0; j
// Core algorithm implementation
// loop search match
Private void loopsearch (stepnode node) {while (Openarr.count> 0) {node = (stepnode) Openarr [0]; Openarrr.Remove (Node);
// If the target node stops searching if (node.isaim ()) {setpath (node);} else {// generates a child node. Node.createChildren (); // Check for each child node (StepNode I in node.children) {// If not in the Open and Close tables. IF (Contain (Closedarr, I) == - 1 && Contain (Openarr, i) == - 1) {Openarr.Add (i);
// If Else IF (Contain (Openarr, I)! = - 1) in the OPEN table (Stepnode N = (Stepnode) Openarr [Contain (Openarr, I)];
/ / If the estimate of i is smaller than the estimated value in the Open table, the estimate of the table is replaced.
IF (i.heuristic_gene // If you are in a close. Else {StepNode N = (StepNode) Closedarr [Contain (CloseDarr, I)]; / / If the estimate value of i is less than the estimated value in the closed table, the estimate in the table is replaced. IF (i.heuristic_gene {N.heuristic_gene = i.heuristic_gene; CloseDarr.Removeat (Contain (Openarr, i)); Openarr.Add (n);}}}} // node is added to the Closed table indicates that has been accessed. Closedarr.add (node); // Sort the node Openarr.Sort (new mycomparer ());}} // This is not possible in theory Path = "Not Found @!"; Return;} Fourth, test results 1) 8 countless search paths are shown below Generate is used to randomly generate an initial state (46) indicating a random initial state generated after a random 46 from a standard state. Here 46 is a random number, and since the maximum leaves are far from the target, the searches are more complex, and the random number is controlled between 0-100. 3 Represents the square of the 3, that is, 8 count problems, 4 indicates that the square is a number of problems. 2) 15 number issues search paths as follows
