First school a * algorithm

First, introduce a * algorithm

People who have learned the data structure know that the search algorithms have mainly deep priority algorithms and a broad priority algorithm. Single is priority to a layer of initial node, until the target is found. The depth is preferred to find a branch of the node before, and then find another branch to find the target. In the breadth, the entire search seems to be unfolded outward until it reaches the target node, so that although the solution must find the optimal solution, the number of nodes is expanded is increasing, which is added to computer memory and CPU. The resource requirements are very large, and the operation is too low, which can be said that this algorithm is not practical.

The heuristic search algorithm can be considered at this time. And a * algorithm is actually a heuristic search.

The so-called heuristic search is to use an estimated function to evaluate the value of each decision, decide which solution is tried first, which can greatly optimize ordinary breadth priority search. For example, the shortest distance from the starting point (a) to the destination (B) is fixed, we can write a shortest distance of a function judge () estimate (a) to (b), if the program has tried from the starting point ( A) Move along a route to (c), then we believe that the estimated distance between (a) to (b) between this scheme is (a) to (c) the actual distance (H) plus The distance from (c) to (b) is estimated by judge (). So, no matter which step our program search is expanded, it will calculate an evaluation value. After each decision, you will sort the evaluation value and the waiting process, and then picked out the most likely the shortest route from the various schemes to be processed. A portion of the program expands to the next step, it is loop to the object to move to the destination, or all the scenarios have attempted that there is no way to find a path to the destination.

It can be seen that the valuation of the distance is important in heuristic search. Different valuation strategies can have different effects. Let's take a look at how the valuation is expressed.

The valuation in inspiration is to use the valuation function, such as:

f (n) = g (n) h (n)

Where f (n) is the estimation function of Node N, G (n) is actually the actual price from the initial node to the n node in the status space, and H (n) is an estimated cost from the N to the target node optimal path. Here, h (n) reflects the inspiration information of the search because g (n) is known. If the detailed point, G (n) represents the broad priority trend of the search.

The valuation function in the heuristic search is very important. How to ensure that the shortest path can you find? The fill condition is that the distance between the two points calculated by the valuation function must be less than or equal to the actual distance. This can be proven from mathematics. If your valuation function does not satisfy this, it can only be called a A algorithm, and it cannot guarantee that the last result is optimal, but it may be very fast, so there is also a problem that does not necessarily require the best solution. Practical. However, it is undoubtedly, in the A * algorithm of the super-sufficient condition, the closer the value of the estimated value is, the better the value of the real value.

Second, a * algorithm pseudo code

As shown in the figure, the following state space: (the starting position is a, the target position is p, the number of letters indicates the value of the node)

Set two tables in the search process: Open and Closed. The OPEN table holds all the generated and unscrupulous nodes, and the accessible node is recorded in the closed table. One step in the algorithm is to rearrange the OPEN table according to the valuation function. Each step in this loop considers the best node in the OPEN table. The specific search process is as follows:

1) Initial status: open = [a5]; closed = []; 2) Estimate A5, get a child node, and put it in the OPEN table; open = [b4, c4, d6]; closed = [A5] 3 Estimate B4, get a child node, and put it in the OPEN table; open = [c4, E5, f5, d6]; closed = [b4, a5] 4) estimate C4; get a child node, and put it in In the OPEN table; open = [h3, g4, e5, f5, d6]; closed = [c4, b4, A5] 5) estimate H3, acquire a child node, and put it in the OPEN table; open = [O2, P3, G4, E5, F5, D6]; Closed = [H3, C4, B4, A5] 6) Estimates O2, acquire a child node, and put it in the OPEN table; open = [p3, g4, e5, f5 , D6]; Closed = [O2, H3, C4, B4, A5] 7) Estimate P3, has been obtained; see the specific process, then look at the fake program. The fake program of the algorithm is as follows:

BEST_FIRST_SEARCH () {open = [start node]; closed = []; while (OPEN table non-empty) {get a node X from the Open and delete it from the OPEN table. If (x is the target node) {obtain path path; return path path;} for (sub-node y) {if (Y is not in the OPEN table and close table) {ask Y's valuation; Insert in the OPEN table;} // No sorted else if (y in the OPEN table) {if (Y's valuation value is less than the valuation of the OPEN table) Update the valuation in the OPEN table;} else // y in the close table The value of {if (Y is less than the valuation value of the Close table) {Update the valuation in the Close table; remove the node from the Close table, and put it in the OPEN table;}} Insert the X node into the Close table; Value sorts the nodes in the OPEN table;}}}

Third, a * algorithm implementation (1)

Void AstarpathFinder :: FindPath (int SX, INT SY, INT DX, INT DY) {node * node, * bestnode; int Tilenumdest; // Get the target location, determine TilenumDest = Tilenum (SX, SY); // Generate Open = (node ​​*) Calloc (1, sizeof (node)); closed = (node ​​*) Calloc (1, sizeof (node)); // Generate the start node and put it in the OPEN table Node = (Node *) Calloc (1, sizeof (node)); Node-> g = 0; // This is calculated to calculate h value // shop really use sqrt (). Node-> h = (DX-SX) * ( DX-SX) (DY-SY) * (DY-SY); // This is calculated to calculate the f value, that is, the value node-> f = node-> g node-> h; node-> nodenum = tilenum DX, DY); Node-> x = DX; Node-> Y = DY; // make open list point = node = node; for (;;) {// from the OPEN table to get an estimate The best value node bestNode = returnBestNode (); // If the node is quit // if We've Found the end, break and finish break; if (BestNode-> nodenum == tilenumdest) / / Otherwise Children's GenerateSuccessors (BestNode, SX, SY);} Path = BestNode;}

// Generate a child node function: Void AstarpathFinder :: generateSuccessors (Node * BestNode, Int DX, INT DY) {Int x, y; // Oh! Generate the child nodes in eight directions, simple! // Upper-left if (Freetile (x = bestnode-> x-tilesize, y = bestnode-> y-tilesize)) Generatesucc (BestNode, X, Y, DX, DY); // Upper if (Freetile (x = Bestnode-> x, y = bestnode-> y-tilesize)) GENERATESUCC (BestNode, X, Y, DX, DY); // Upper-Right IF (Freetile (x = bestnode-> x tilesis, y = bestnode- > Y-TILESIZE)) GenerateSucc (BestNode, X, Y, DX, DY); // Right IF (Freetile (x = bestnode-> x tilesize, y = bestnode-> y) GENERATESUCC (BestNode, X, Y , DX, DY); // Lower-Right IF (Freetile (x = Bestnode-> x tilesize, y = bestnode-> y tilesize)) GenerateSucc (BestNode, X, Y, DX, DY); // Lower IF (Freetile (x = bestnode-> x, y = bestnode-> y tilesize)) GENERATESUCC (BestNode, X, Y, DX, DY); // Lower-Left if (Freetile (x = bestnode-> x- TILESIZE, Y = BESTNODE-> Y TILESIZE)) GenerateSucc (BestNode, X, Y, DX, DY); // Left if (Freetile (x = bestnode-> x-tilesis, y = bestnode-> y) generatesucc BestNode, X, Y, DX, DY);

Void ASTARPATHFINDER :: GenerateSucc (Node * BestNode, INT X, INT Y, INT DX, INT DY) {INT G, TILENUMS, C = 0; Node * OLD, * Success; // Calculate the g value of the sub-node / / g (Success) = g (BestNode) Cost of getting from bestnode to successor g = bestnode-> g 1; // identification purposes tilenums = tilenum (x, y); // Is the child node Open table? // if Equal to null the NOT IN OPEN LIST, ELSE IT RETURns the node in in = null) {// If in for (c = 0; c <8; C ) // add old to the list of bestnode's children (or success "). If (BestNode-> Child [C] == null) Break; BestNode-> Child [C] = OLD; // Compare the valuation in the Open table and Current valuation (as long as the G value can be compared) // if we new g value is g) {// current valuation small update Valuation value in the OPEN table OLD-> Parent = BestNode; OLD-> g = g; OLD-> f = g old-> h;}} else / / Is it in a closed table? // if equal to null the NOT IN OPEN LIST, Else It Returns the node in in = null) {// If in for (c = 0; c <8; C ) // add old to the list of bestnode's children (or success "). If (BestNode-> Child [C] == null) Break; BestNode-> Child [C] = OLD; // Compare the valuation in the closed table and Current valuation (as long as the G value can be compared) // ix u i g =

S Parent to Point To BestNode if (g g) {// The current valuation value is updated in the CLOSED table's valuation value Old-> Parent = BestNode; OLD-> g = g; OLD-> f = G Old-> h; // renew all the valuation of all child nodes in turn // Since We change the g value of old, We need // to Propagate this New value Downwards, IE // do a depth-first Traversal of the tree!}}}} // does not in the Open table ELSE {// Generate new nodes Successor = (Node *) Calloc (1, sizeof (node)); successor-> PARENT = BESTNODE; SUCCESSOR-> g = g; // Should Do SQRT (), But Since We Don't real success we don't real success-> h = (x-dx) * (x-dx) (Y-DY) * (Y-DY) * Y-DY); // Care About The Distance But Just Which Branch Looks Successor-> f = G Successor-> H; // Better this Should Suffice. Anyayz it's faster. Success -> x = x; successor-> y = y; successor-> nodenum = tilenums; // Insert an OPEN table, simultaneously sort. // INSERT SUCCESSOR ON OPEN LIST WRT F INSERT (SUCCESSOR); for (c = 0; C <8; C ) // add old to the list of bestnode's children (or success "). If (BestNode-> Child [C] == NULL) Break; bestnode-> Child [C] = success -}} 4, a * algorithm implementation (2)

/ * Cloud Wind Solving Code (Cloud Wu's Pathfinding Code) * / # Define MapMaxSize 100 // The map area is up to 100X100 # Define Maxint 8192 / / Defines a maximum integer, any two-point distance from the map will not exceed it # DEFINE StackSize 65536 / / Save the stack size #define tile_num (x, y) ((y) * map_num (x, y) // of the search node to convert X, Y coordinate to the map #define tile_x (n) (N) (n)% map_w) // Loosing x, y coordinate #define tile_y (n) ((n) / map_w)

// tree structure, more special, is a reverse link from the leaf node to the root node. Typedef struct node * Tree;

Struct node {int h; int tile; tree fa;};

Typedef struct node2 * link;

Struct node2 {tree node; int F; link next;};

Link queue; // Save Node Tree Stack [stacksize] without processing walking method; // Save the already processed node (search after search) int StackTop; unsigned char map [mapMaxSize] [MapMaxSize]; // Map data INT DIS_MAP [MapMaxSize] [MapMaxSize]; // When saving the search path, the most optimal solution in the middle

INT MAP_W, MAP_H; // Map Width and High Int Start_x, Start_Y, End_x, End_y; // Location, End Point Coordinate

// Initialized queue vid init_Queue () {que = (limited); queue-> node = null; queue-> f = -1; queue-> next = (link) malloc (Sizeof * Queue); queue-> next-> f = maxint; queue-> next-> node = null; queue-> next-> next = null;}

// To be processed node into the queue, rely on the destination to estimate the distance insertion VOID Enter_Queue (Tree Node, INT F) {link P = queue, Father, Q; While (f> p-> f) {Father = P; P; = P-> next; assert (p);} Q = (link) malloc (SizeOf (* q)); assert (queue); Q-> f = f, q-> node = node, q-> next = p; father-> next = q;}

// will estimate the most recent programs for the destination Tree get_from_queue () {tree bestchoice = queue-> Next-> node; link next = queue-> next-> next; free (queue-> next); queue-> Next = next; stack [stacktop ] = bestchoice; assert (stacktop

/ / Release Stack Top Node Void Pop_stack () {free (stack [- stacktop]);} // Release all nodes VOID Freetree () {INT I; LINK P; for (i = 0; i node); queue = queue-> next; free (p);}}

// Valuation function, valuation X, Y to the destination distance, the estimated value must ensure a small Int Judge than actual value, {{{int distanceance; distance = ABS (end_x-x) ABS (End_Y-Y) RETURN DITANCE;

// Try the next step to move to x, y, Y, INT X, INT Y, Tree Father {Tree P = Father; INTH; IF (MAP [Y]! = ') Return 1; // If (x, y) is an obstacle, the WHILE (P) {IF (x == Tile_x (P-> Tile) && y == Tile_y (P-> Tile)) Return 1; // If (x Y) I have passed, failed P = P-> Father;} h = father-> h 1; if (h> = dis_map [y]) Return 1; // If there is a better scheme movement By (x, y) failed dis_map [y] = h; // Record the distance of this (x, y) is a history optimal distance // put this plan into the tortured queue P = (Tree ) Malloc (sizeof (* p)); p-> father = father; p-> h = father-> h 1; p-> tile = tile_num (x, y); enter_queue (p, p-> h Judge (x, y)); return 0;}

// Path looks for main function void FindPath (INT * PATH) {Tree root; INT i, J; stacktop = 0; for (i = 0; i tile = Tile_NUM (start_x, start_y); root-> h = 0; root-> Father = null; Enter_Queue (root, judge (start_x, start_y)); for (;;) {Int x, y, child; tree p; root = get_from_queue (); if (root == null) {* path = - 1; return;} x = Tile_x (root-> tile); y = tile_y (root-> tile); if (x == end_x && y == end_y) Break; // reach the destination successfully returns Child = Trytile X, Y-1, root; // Try moving CHILD & = Trytile (x, y 1, root); // Try moving CHILD & = Trytile (X-1, Y, Root); // Try Left Mobile & = Trytile (x 1, y, root); // Try to move if (Child! = 0) POP_STACK (); // If four directions can be moved, release this dead node} // backtrack Tree, save the best path to PA in PA TH [] in For (i = 0; root; i ) {path [i] = root-> tile; root = root-> father;} Path [i] = - 1; freeetree ();} void printpath (int * PATH) {INT i; for (i = 0; Path [I]> = 0; i ) {gotoxy (Tile_X (Path [i]) 1, TILE_Y (PATH [I]) 1); CPRINTF (" / XFE ");}}

INT readMap () {file * f; INT I, J; f = fopen ("map.dat", "r"); assert (f); fscanf (f, "% d,% d / n", & map_w, & map_h); for (i = 0; I

INT main () {int path [maxint]; readmap (); showMap (); getCh (); FindPath (PATH); PrintPath (PATH); getCh (); return 0;}