A * algorithm implementation
First, algorithm thinking
Using heuristic information in the search, the current unscaped node is selected from the desired node based on the set estimation function value, thereby reducing the search space, gains the optimal solution faster, and improve efficiency.
Second, inspiration functions
1. Not in the number of digits, the number of digits h (n) is the number of digital numbers that are not in position. Since only one digital bit can be moved at a time, H (n) <= h * (n), and H (t) = 0 is also H (T) = 0 and is H (M, the sub-node of N is M). ) - h (n) <= 1 = COST (M, N), that is, the inspiration function satisfies the monotonic restriction condition, as long as it extends to a node, find the optimal path to the node from the initial node.
2, each digital bit and the corresponding target numeric distance and further considering the distance information of the current node and the target node, the inspiration function h (n) is the current 8 digital bits corresponding to the digital bit distance and ( Do not consider the intermediate path), the H (N) <= H * (N) is also satisfied, and H (t) = 0 is H (T) = 0 for the target, there is h (M in the sub-node of M is M). ) - h (n) <= 1 = COST (M, N) satisfies the monotonic restriction condition.
Third, specific implementation
1, node coding For 8 digital issues, each node has 8 numbers and a space, you can see the space as 0, then a total of 9 numbers, 32-bit int can represent 2 * 109, you can use an integer Indicates a node corresponding to information. Calculate the position of 0 (ie, space) in an integer time consumption, store the position of the current node 0, and store the corresponding G, H value, and which node expansion from which the node is expanded.
2, the data structure of the OPEN table represents the operation of the OPEN table, each time you need to get the node that is the smallest of the F value in the node to be extended, and you can achieve O (Log (Heapsize) time complexity. .
3. The data structure of the Closed table represents the extended relationship between the Closed table stores, mainly for the output path. Considering the operation of the node extension, the expansion of the extended point is m, which is extended by its expansion of the result of N1, N2, .... When the node m expands, it is placed in a closed table. After placing it, it does not change in the CLOSED table, and N1, N2, ... The front displacement point of the N1, N2, ... can be placed in the position in the closed table, when N1, N2, .. There is a node set to N1 to be extended to the Closed table, the front drive of N1 has just been stored. Here's below that any of the nepheses in the Closed table stores information with its pre-discrete points, considering any of the closed tables, if it is an initial node, it does not have a forward-driver, if not root node, expand the It has been recorded at the time of node. Thereby, a tree structure of the extended relationship is formed in the Closed table. Because only the subscript point of the predecessor point is required, you can use the array implementation, each node records the 8 digital pattern indicated by the integer and its previous discord point, when the output path is output, the front disband point is formed to reach the root node The chain, the recursive output.
4. Solving the Node Repeat Extension Problem For a variety of ways to reach this node, this may be added to the OPEN table multiple times, and the inspiration function meets the monotonic restriction condition, and later reaches the path of this node no longer It is better, it can be regarded. When you expand a node, see if this node has expanded, and if expanded, it is slightly. Implemented can spread the closed table, but the efficiency is not high-time complexity O (ClosedSize), considering that each node can be identified with an integer identifier, with a binary balance lookup tree to get a better time complexity O (LOG CloseDsize)), the program is implemented in a red-black tree thinking. Fourth, compare programs
In contrast test time, a width priority method is implemented to solve the A * algorithm of 8 digital issues and two inspiration functions. The width is preferred to be a blind search method, and there is no available information to explore the problem, or H (n) = 0. When searching for extended nodes, only the number of nodes to be extended according to the number of layers, according to the extended node, the search space is large, time consuming. The inspiration function will directly affect the A * algorithm performance.
V. Input and output
The program uses the text input and output, the input file is ASTAR.IN, the A * algorithm first inspiration function output file is ASTAR1.OUT, the second inspiration function output is ASTAR2.out, the width priority algorithm is bfs.out, you can use Notepad opens. The input format is a test case consisting of two middle-digital patterns that are spaced apart from a hollow line, and outputs the effect of the test case, and the program assumes that the input data meets the requirements, not checking.
6. Test results Test case The last one requires 30 steps to obtain results, large data size, width priority algorithm and the first inspiration function A * algorithm take a few seconds to run the result, the second algorithm is very fast to get results . The following data is the result of the compiled VC 6.0. VC 6.0 supports STL support in standard C , using G to compile the compilation, which can be greatly shortened (all test cases are tested within 1 second). ). Width priority algorithm:
Enter the data number
Step count
Extended node
Generate nodes
Search time (ms)
1
5
36
65
15
2
18
23486
34961
1141
3
1
2
Seduce
0
4
30
181413
181440
6235
A * algorithm 1, using the first inspiration function:
Enter the data number
Step count
Extended node
Generate nodes
Search time (ms)
1
5
6
13
0
2
18
1279
2122
46
3
1
1
4
0
4
30
98405
122999
4266
A * algorithm 2, using the second inspiration function:
Enter the data number
Step count
Extended node
Generate nodes
Search time (ms)
1
5
5
11
0
2
18
171
289
0
3
1
1
4
0
4
30
7943
12019
359
Seven, conclusions:
1. When the width priority algorithm extension node does not consider the node and the target of the target from the OPEN table, the A * algorithm uses the valuation function to calculate the distance to the OPEN table to be extended to the margin and the target node. " The nearest node is expanded, and the expansion has little junction, and the search space is reduced, and the search space is improved. 2, inspiration function is very bad, the performance of the A * algorithm, can be seen from the above table, make full use of the problem intrinsic information, inspiration function design, can greatly reduce the expansion, for 18 steps to complete The test case can be done within 1 millisecond, and only 0.359 seconds for test cases that require 30 steps, which is much faster than the first A * algorithm. The two inspiration functions selected above meet the monotonic restrictions, and the initial nodes to the optimal path of the node are extended to a somewhere. Source code and test data / * algorithm: a * is the mostforward solution: inspiration function: the distance of each numeric bit and the digital bit in the target, meet the monotonic restriction condition; inspiration function: Not in the number of digits: a * The algorithm is an inspirated search algorithm. When searching, take the current state distance target distance from the high-near-close information, select the minimum scaled function in the current unlaking node, generate less node, the search space is small, the realization is slightly complex, note : The program does not check the input data * / # pragma Warning (Disable: 4786) #include
Const int mapsteps = 100000; const amount = 100; char buf [maxchar] [maxchar]; // Open table item open [maxsteps]; int steps = 0; // closed, query status as long as the status and it From which node is extended, it can be used for output path // each time you just get the smallest node to be extended to the F value, and improve the efficiency PAIR
// Read, convert 8 Digital Matrix Pattern into an integer representation Bool Read (Pair
/ / Calculate the distance of current nodes Int Calculate (int current, int target) {Int C [9], T [9]; INT I, CNT = 0; for (i = 0; i <9; i) {c [current% 10] = T [target% 10] = i; current / = 10; target / = 10;} for (i = 1; i <9; i) CNT = ABS (C [I] / 3 - T [I] / 3) ABS (C [I]% 3 - T [I]% 3); Return CNT;}
// Open point in the Open table, rule f (n) = g (n) h (n) class cmp {public: inline bool operator () (item a, item b) {return Ag ah> BG BH;}}; // Reference integer forms to the matrix to represent the output Void Pr (INT State) {MEMSET (BUF, ', SIZEOF (BUF)); for (int i = 0; i <3; ) I) {for (int J = 0; j <6; j = 2) {if (state% 10) BUF [I] [j] = state% 10 '0'; state / = 10;} buf [ I] [5] = '/ 0'; PUTS (BUF [i]);}}
// Used to determine if the current space can move in Wait Suit (INT A, INT B) {RETURN (A> = 0 && a <3 && B> = 0 && B <3);}
// Removing output search path path Void path (int index) {if (index == 0) {PR (Closed [index] .first); PUTS (""); return;} Path (Closed [index] .second) : PR (Closed [index] .first); PUTS (""); steps;}
INT main () {Unsigned Int T1 = clock (); Freopen ("ASTAR.IN", "R", stdin; Freopen ("ASTAR2.out", "W", stdout; set // Remove the node POP_HEAP (Open, Open end, CMP ()) from the OPEN table; --End; // Get the result, recursive output path if (head.state == target.first) {Path (Index Break;} x = head.blank / 3; y = head.blank% 3; for (i = 0; i <4; i) {nx = x XTRAN [i]; NY = Y YTRAN [I]; if (Suit (NX, NY)) {a = head.blank; b = nx * 3 ny; // Switch the decimal representation integer corresponds to two numeric NEXT = head.state ((Head.State) % P [A 1]) / P [A] - (Head.State% P [B 1]) / P [b]) * p [b] (Head.State% p [b 1]) / p [b] - (Head.State% P [A 1]) / P [A]) * p [a]; // Judgment has expanded Over IF (States.Find () == states.und ()) {states.insert (next); open [end] .pre = index; open [end] .blek = B; open [end] .state = NEXT; Open [end] .h = Calculate (Next, Target.first); open [end] .g = head.g 1; End; push_heap (Open, Open End, CMP ());}}}} IF ("no solution"); else {printf ("Num of Steps:% D / N", Steps; Printf ("Num of Expanded:% D / N", Index); Printf ("Num of Generated:% D / N", Index End); Printf ("Time ConsuMed:% D / N / N", Clock () - T2);} States.clear (); Steps = 0; Printf ("Total Time ConsuMed:% D / N", Clock () - T1); Return 0;} / * Algorithm: Width is preferred to know: Yes: Width Priority Search belongs to blind search, no profit With the current status distance of the target distance from the target distance, only the nodes of the genus are preferred when selecting the width or the number of layers, the number of nodes is large, the search space is large, but the idea is simple, but Code length and a * algorithm algorithm: The program does not check the input data * / # pragma Warning (Disable: 4786) #include / * Item is used to record the corresponding information of a node wherein: State indicates that the current 8 digital correspondence, such as 102345678, corresponding: 8 7 6 5 4 3 2 1 Reverse to all numbers (0 instead of spaces) to BLANK The location of the recording space is 7 pre-use for recording the current state is * / struct item {int State; int BLANK; int pre;}; const amount {Int;}; const INSTEPS = 500000; Const int maxChar = 100; char buf [maxchar] [maxchar]; // [0, TOP) is a closed table, [TOP, END] is OPEN table item open [MaxSTeps]; // Read, transform the matrix 8 digitally converted to use an integer to represent Bool Read (PAIR // Transfer 8 digital conversion into matrix represents output VOID PR (INT State) {MEMSET (BUF, ''); for (int i = 0; i <3; i) {for (INT J = 0; j <6; j = 2) {if (state% 10) BUF [i] [j] = state% 10 '0'; state / = 10;} BUF [i] [5 ] = '/ 0'; PUTS (BUF [i]);}} // Determine if the space is removed from the matrix, that is, whether the current state space can move in Whether INLINE BOOL SUIT (INT A, INT B) {RETURN (A> = 0 && a <3 && b> = 0 && B <3); INT Steps = 0; // Record the number of steps required to move // Remove the process of forming the final 8 digital process void path (INDEX == 0) {PR (Open [index] .state); PUTS (""); Return;} path (open [index] .pre); PR (Open [index] .state); PUTS (""); Steps;} INT main () {Unsigned Int T1 = Clock (), T2; Freopen ("ASTAR.IN", "R", stdin; Freopen ("BFS.out", "W", stdout; set Y YTRAN [I]; IF (Suit (NX, NY)) {a = head.blank; b = nx * 3 ny; // Integer corresponds to two decimal digital bits to change next = head.state ((Head .State% p [a 1]) / p [a] - (head.state% P [B 1]) / P [b]) * p [b] ((head.state% P [B 1]) / P [b] - (Head.State% P [A 1]) / P [A]) * p [a]; // Determine if the status has expanded IF (States.Find (Next) == states.end ()) {states.insert (next); open [end] .pre = top; open [end] .blek = B; open [end] .state = next; End;}}}}}} ("no solution / n"); else {printf ("Num of Steps:% D / N", Steps; Printf ("Num of Expanded:% D / N ", TOP); Printf (" Num of generated:% D / N ", END); Printf (" Time ConsuMed:% U / N / N ", Clock () - T2);} States.clear Steps = 0; }printf (" Total Time ConsuMed:% U / N ", Clock () - T1); Return 0;} test data ASTAR.IN2 8 31 6 47 5 1 2 38 47 6 5 2 1 64 87 5 3 1 2 38 47 6 5 1 2 38 47 6 5 1 2 38 4 7 6 5 1 2 34 5 67 8 8 7 65 4 32 1
