8 and 15 questions
-,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 (p.x> = 1)
{
Stepnode node = new step node ();
To (this, node);
Position P1 = New Position (P.X-1, P.Y); AddChild (Node, P, P1);
}
}
// 0 Digital down
Private void movedown (position P)
{
IF (p.x <= text_v.length-2)
{
Stepnode node = new step node ();
To (this, node);
POSITION P1 = New Position (p.x 1, p.y);
AddChild (Node, P, P1);
}
}
// 0 Digital left shift
Private Void MoveLeft (position P)
{
IF (p.y> = 1)
{
Stepnode node = new step node ();
To (this, node);
Position P1 = New Position (p.x, p.y-1);
AddChild (Node, P, P1);
}
}
// 0 Digital right shift
Private void Moveright (position P)
{
IF (p.y <= text_v.length-2)
{
Stepnode node = new step node ();
To (this, node);
Position P1 = new position (p.x, p.y 1);
AddChild (Node, P, P1);
}
}
/ / Calculate the value of the inspiration function of the node
Private void computegeuristicgeneval ()
{
INT geneval = this.height;
INT g = 0; // Inspiration Factor Each data reaches the minimum number of steps that you need to pass
For (int i = 0; i { For (int J = 0; j { Position P1 = getPosition (Text_V [I] [J]); Position P2 = getPosition (AIM [i, j]); INT xd = p1.x> p2.x? p1.x - p2.x: p2.x - p1.x; INT YD = p1.y> p2.y? p1.y - p2.y: p2.y - p1.y; G = XD YD; } } Geneval = g; THISHEURISTIC_GENE = Geneval; } // HEURISTIC_15NUM_SEARCH class // Core algorithm implementation // loop search match Private void loopsearch (stepnode node) { While (Openarr.count> 0) { Node = (stepnode) Openarr [0]; Openarr.Remove (Node); // If it is a target node, stop searching IF (node.isaim ()) { SetPath (Node); Return; } Else { // Generate a child node. Node.createChildren (); / / Check each child node FOREACH (StepNode I in node.children) { // If it is not in the Open and Close tables. IF (Contain (Closedarr, I) == - 1 && Contain (Openarr, i) == - 1) { Openarr.Add (i); } // If in the OPEN table Else IF (Contain (Openarr, I)! = - 1) { 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 { n.heuristic_gene = 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 node Openarr.sort (new mycomparer ()); } } // This is theoretically impossible 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 From the above results, due to the use of heuristic search procedures, the speed of the search is greatly accelerated, and the least path is as quickly as possible to reach the target state. Since the 8 count is relatively simple, therefore the search speed is faster, and 15 The complexity of several issues is increased. When the random number is close to 100, the search time is slower, the algorithm still needs to be improved, mainly because the data in the Openarr and Closearr is rapidly expanded as the depth is deepened. Considering the selectability of the number of states in the OpenARR table, for example, each time the data in the Openarr can be sorted, it can delete the last few worst states, so that the speed is improved to a certain extent, but also reduces it. This chance to find the optimal solution is that this reduction is very small, because the exclusible is the worst case. Please advise, I want to source email me.
