الگوریتم *A — به زبان ساده

1function reconstruct_path(cameFrom, current)
2    total_path := {current}
3    while current in cameFrom.Keys:
4        current := cameFrom[current]
5        total_path.append(current)
6    return total_path
7
8function A_Star(start, goal)
9    // The set of nodes already evaluated
10    closedSet := {}
11
12    // The set of currently discovered nodes that are not evaluated yet.
13    // Initially, only the start node is known.
14    openSet := {start}
15
16    // For each node, which node it can most efficiently be reached from.
17    // If a node can be reached from many nodes, cameFrom will eventually contain the
18    // most efficient previous step.
19    cameFrom := an empty map
20
21    // For each node, the cost of getting from the start node to that node.
22    gScore := map with default value of Infinity
23
24    // The cost of going from start to start is zero.
25    gScore[start] := 0
26
27    // For each node, the total cost of getting from the start node to the goal
28    // by passing by that node. That value is partly known, partly heuristic.
29    fScore := map with default value of Infinity
30
31    // For the first node, that value is completely heuristic.
32    fScore[start] := heuristic_cost_estimate(start, goal)
33
34    while openSet is not empty
35        current := the node in openSet having the lowest fScore[] value
36        if current = goal
37            return reconstruct_path(cameFrom, current)
38
39        openSet.Remove(current)
40        closedSet.Add(current)
41
42        for each neighbor of current
43            if neighbor in closedSet
44                continue		// Ignore the neighbor which is already evaluated.
45
46            // The distance from start to a neighbor
47            tentative_gScore := gScore[current] + dist_between(current, neighbor)
48
49            if neighbor not in openSet	// Discover a new node
50                openSet.Add(neighbor)
51            else if tentative_gScore >= gScore[neighbor]
52                continue
53
54            // This path is the best until now. Record it!
55            cameFrom[neighbor] := current
56            gScore[neighbor] := tentative_gScore
57            fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)

1// A C++ Program to implement A* Search Algorithm 
2#include<bits/stdc++.h> 
3using namespace std; 
4  
5#define ROW 9 
6#define COL 10 
7  
8// Creating a shortcut for int, int pair type 
9typedef pair<int, int> Pair; 
10  
11// Creating a shortcut for pair<int, pair<int, int>> type 
12typedef pair<double, pair<int, int>> pPair; 
13  
14// A structure to hold the neccesary parameters 
15struct cell 
16{ 
17    // Row and Column index of its parent 
18    // Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1 
19    int parent_i, parent_j; 
20    // f = g + h 
21    double f, g, h; 
22}; 
23  
24// A Utility Function to check whether given cell (row, col) 
25// is a valid cell or not. 
26bool isValid(int row, int col) 
27{ 
28    // Returns true if row number and column number 
29    // is in range 
30    return (row >= 0) && (row < ROW) && 
31           (col >= 0) && (col < COL); 
32} 
33  
34// A Utility Function to check whether the given cell is 
35// blocked or not 
36bool isUnBlocked(int grid[][COL], int row, int col) 
37{ 
38    // Returns true if the cell is not blocked else false 
39    if (grid[row][col] == 1) 
40        return (true); 
41    else
42        return (false); 
43} 
44  
45// A Utility Function to check whether destination cell has 
46// been reached or not 
47bool isDestination(int row, int col, Pair dest) 
48{ 
49    if (row == dest.first && col == dest.second) 
50        return (true); 
51    else
52        return (false); 
53} 
54  
55// A Utility Function to calculate the 'h' heuristics. 
56double calculateHValue(int row, int col, Pair dest) 
57{ 
58    // Return using the distance formula 
59    return ((double)sqrt ((row-dest.first)*(row-dest.first) 
60                          + (col-dest.second)*(col-dest.second))); 
61} 
62  
63// A Utility Function to trace the path from the source 
64// to destination 
65void tracePath(cell cellDetails[][COL], Pair dest) 
66{ 
67    printf ("\nThe Path is "); 
68    int row = dest.first; 
69    int col = dest.second; 
70  
71    stack<Pair> Path; 
72  
73    while (!(cellDetails[row][col].parent_i == row 
74             && cellDetails[row][col].parent_j == col )) 
75    { 
76        Path.push (make_pair (row, col)); 
77        int temp_row = cellDetails[row][col].parent_i; 
78        int temp_col = cellDetails[row][col].parent_j; 
79        row = temp_row; 
80        col = temp_col; 
81    } 
82  
83    Path.push (make_pair (row, col)); 
84    while (!Path.empty()) 
85    { 
86        pair<int,int> p = Path.top(); 
87        Path.pop(); 
88        printf("-> (%d,%d) ",p.first,p.second); 
89    } 
90  
91    return; 
92} 
93  
94// A Function to find the shortest path between 
95// a given source cell to a destination cell according 
96// to A* Search Algorithm 
97void aStarSearch(int grid[][COL], Pair src, Pair dest) 
98{ 
99    // If the source is out of range 
100    if (isValid (src.first, src.second) == false) 
101    { 
102        printf ("Source is invalid\n"); 
103        return; 
104    } 
105  
106    // If the destination is out of range 
107    if (isValid (dest.first, dest.second) == false) 
108    { 
109        printf ("Destination is invalid\n"); 
110        return; 
111    } 
112  
113    // Either the source or the destination is blocked 
114    if (isUnBlocked(grid, src.first, src.second) == false || 
115            isUnBlocked(grid, dest.first, dest.second) == false) 
116    { 
117        printf ("Source or the destination is blocked\n"); 
118        return; 
119    } 
120  
121    // If the destination cell is the same as source cell 
122    if (isDestination(src.first, src.second, dest) == true) 
123    { 
124        printf ("We are already at the destination\n"); 
125        return; 
126    } 
127  
128    // Create a closed list and initialise it to false which means 
129    // that no cell has been included yet 
130    // This closed list is implemented as a boolean 2D array 
131    bool closedList[ROW][COL]; 
132    memset(closedList, false, sizeof (closedList)); 
133  
134    // Declare a 2D array of structure to hold the details 
135    //of that cell 
136    cell cellDetails[ROW][COL]; 
137  
138    int i, j; 
139  
140    for (i=0; i<ROW; i++) 
141    { 
142        for (j=0; j<COL; j++) 
143        { 
144            cellDetails[i][j].f = FLT_MAX; 
145            cellDetails[i][j].g = FLT_MAX; 
146            cellDetails[i][j].h = FLT_MAX; 
147            cellDetails[i][j].parent_i = -1; 
148            cellDetails[i][j].parent_j = -1; 
149        } 
150    } 
151  
152    // Initialising the parameters of the starting node 
153    i = src.first, j = src.second; 
154    cellDetails[i][j].f = 0.0; 
155    cellDetails[i][j].g = 0.0; 
156    cellDetails[i][j].h = 0.0; 
157    cellDetails[i][j].parent_i = i; 
158    cellDetails[i][j].parent_j = j; 
159  
160    /* 
161     Create an open list having information as- 
162     <f, <i, j>> 
163     where f = g + h, 
164     and i, j are the row and column index of that cell 
165     Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1 
166     This open list is implenented as a set of pair of pair.*/
167    set<pPair> openList; 
168  
169    // Put the starting cell on the open list and set its 
170    // 'f' as 0 
171    openList.insert(make_pair (0.0, make_pair (i, j))); 
172  
173    // We set this boolean value as false as initially 
174    // the destination is not reached. 
175    bool foundDest = false; 
176  
177    while (!openList.empty()) 
178    { 
179        pPair p = *openList.begin(); 
180  
181        // Remove this vertex from the open list 
182        openList.erase(openList.begin()); 
183  
184        // Add this vertex to the closed list 
185        i = p.second.first; 
186        j = p.second.second; 
187        closedList[i][j] = true; 
188       
189       /* 
190        Generating all the 8 successor of this cell 
191  
192            N.W   N   N.E 
193              \   |   / 
194               \  |  / 
195            W----Cell----E 
196                 / | \ 
197               /   |  \ 
198            S.W    S   S.E 
199  
200        Cell-->Popped Cell (i, j) 
201        N -->  North       (i-1, j) 
202        S -->  South       (i+1, j) 
203        E -->  East        (i, j+1) 
204        W -->  West           (i, j-1) 
205        N.E--> North-East  (i-1, j+1) 
206        N.W--> North-West  (i-1, j-1) 
207        S.E--> South-East  (i+1, j+1) 
208        S.W--> South-West  (i+1, j-1)*/
209  
210        // To store the 'g', 'h' and 'f' of the 8 successors 
211        double gNew, hNew, fNew; 
212  
213        //----------- 1st Successor (North) ------------ 
214  
215        // Only process this cell if this is a valid one 
216        if (isValid(i-1, j) == true) 
217        { 
218            // If the destination cell is the same as the 
219            // current successor 
220            if (isDestination(i-1, j, dest) == true) 
221            { 
222                // Set the Parent of the destination cell 
223                cellDetails[i-1][j].parent_i = i; 
224                cellDetails[i-1][j].parent_j = j; 
225                printf ("The destination cell is found\n"); 
226                tracePath (cellDetails, dest); 
227                foundDest = true; 
228                return; 
229            } 
230            // If the successor is already on the closed 
231            // list or if it is blocked, then ignore it. 
232            // Else do the following 
233            else if (closedList[i-1][j] == false && 
234                     isUnBlocked(grid, i-1, j) == true) 
235            { 
236                gNew = cellDetails[i][j].g + 1.0; 
237                hNew = calculateHValue (i-1, j, dest); 
238                fNew = gNew + hNew; 
239  
240                // If it isn’t on the open list, add it to 
241                // the open list. Make the current square 
242                // the parent of this square. Record the 
243                // f, g, and h costs of the square cell 
244                //                OR 
245                // If it is on the open list already, check 
246                // to see if this path to that square is better, 
247                // using 'f' cost as the measure. 
248                if (cellDetails[i-1][j].f == FLT_MAX || 
249                        cellDetails[i-1][j].f > fNew) 
250                { 
251                    openList.insert( make_pair(fNew, 
252                                               make_pair(i-1, j))); 
253  
254                    // Update the details of this cell 
255                    cellDetails[i-1][j].f = fNew; 
256                    cellDetails[i-1][j].g = gNew; 
257                    cellDetails[i-1][j].h = hNew; 
258                    cellDetails[i-1][j].parent_i = i; 
259                    cellDetails[i-1][j].parent_j = j; 
260                } 
261            } 
262        } 
263  
264        //----------- 2nd Successor (South) ------------ 
265  
266        // Only process this cell if this is a valid one 
267        if (isValid(i+1, j) == true) 
268        { 
269            // If the destination cell is the same as the 
270            // current successor 
271            if (isDestination(i+1, j, dest) == true) 
272            { 
273                // Set the Parent of the destination cell 
274                cellDetails[i+1][j].parent_i = i; 
275                cellDetails[i+1][j].parent_j = j; 
276                printf("The destination cell is found\n"); 
277                tracePath(cellDetails, dest); 
278                foundDest = true; 
279                return; 
280            } 
281            // If the successor is already on the closed 
282            // list or if it is blocked, then ignore it. 
283            // Else do the following 
284            else if (closedList[i+1][j] == false && 
285                     isUnBlocked(grid, i+1, j) == true) 
286            { 
287                gNew = cellDetails[i][j].g + 1.0; 
288                hNew = calculateHValue(i+1, j, dest); 
289                fNew = gNew + hNew; 
290  
291                // If it isn’t on the open list, add it to 
292                // the open list. Make the current square 
293                // the parent of this square. Record the 
294                // f, g, and h costs of the square cell 
295                //                OR 
296                // If it is on the open list already, check 
297                // to see if this path to that square is better, 
298                // using 'f' cost as the measure. 
299                if (cellDetails[i+1][j].f == FLT_MAX || 
300                        cellDetails[i+1][j].f > fNew) 
301                { 
302                    openList.insert( make_pair (fNew, make_pair (i+1, j))); 
303                    // Update the details of this cell 
304                    cellDetails[i+1][j].f = fNew; 
305                    cellDetails[i+1][j].g = gNew; 
306                    cellDetails[i+1][j].h = hNew; 
307                    cellDetails[i+1][j].parent_i = i; 
308                    cellDetails[i+1][j].parent_j = j; 
309                } 
310            } 
311        } 
312  
313        //----------- 3rd Successor (East) ------------ 
314  
315        // Only process this cell if this is a valid one 
316        if (isValid (i, j+1) == true) 
317        { 
318            // If the destination cell is the same as the 
319            // current successor 
320            if (isDestination(i, j+1, dest) == true) 
321            { 
322                // Set the Parent of the destination cell 
323                cellDetails[i][j+1].parent_i = i; 
324                cellDetails[i][j+1].parent_j = j; 
325                printf("The destination cell is found\n"); 
326                tracePath(cellDetails, dest); 
327                foundDest = true; 
328                return; 
329            } 
330  
331            // If the successor is already on the closed 
332            // list or if it is blocked, then ignore it. 
333            // Else do the following 
334            else if (closedList[i][j+1] == false && 
335                     isUnBlocked (grid, i, j+1) == true) 
336            { 
337                gNew = cellDetails[i][j].g + 1.0; 
338                hNew = calculateHValue (i, j+1, dest); 
339                fNew = gNew + hNew; 
340  
341                // If it isn’t on the open list, add it to 
342                // the open list. Make the current square 
343                // the parent of this square. Record the 
344                // f, g, and h costs of the square cell 
345                //                OR 
346                // If it is on the open list already, check 
347                // to see if this path to that square is better, 
348                // using 'f' cost as the measure. 
349                if (cellDetails[i][j+1].f == FLT_MAX || 
350                        cellDetails[i][j+1].f > fNew) 
351                { 
352                    openList.insert( make_pair(fNew, 
353                                        make_pair (i, j+1))); 
354  
355                    // Update the details of this cell 
356                    cellDetails[i][j+1].f = fNew; 
357                    cellDetails[i][j+1].g = gNew; 
358                    cellDetails[i][j+1].h = hNew; 
359                    cellDetails[i][j+1].parent_i = i; 
360                    cellDetails[i][j+1].parent_j = j; 
361                } 
362            } 
363        } 
364  
365        //----------- 4th Successor (West) ------------ 
366  
367        // Only process this cell if this is a valid one 
368        if (isValid(i, j-1) == true) 
369        { 
370            // If the destination cell is the same as the 
371            // current successor 
372            if (isDestination(i, j-1, dest) == true) 
373            { 
374                // Set the Parent of the destination cell 
375                cellDetails[i][j-1].parent_i = i; 
376                cellDetails[i][j-1].parent_j = j; 
377                printf("The destination cell is found\n"); 
378                tracePath(cellDetails, dest); 
379                foundDest = true; 
380                return; 
381            } 
382  
383            // If the successor is already on the closed 
384            // list or if it is blocked, then ignore it. 
385            // Else do the following 
386            else if (closedList[i][j-1] == false && 
387                     isUnBlocked(grid, i, j-1) == true) 
388            { 
389                gNew = cellDetails[i][j].g + 1.0; 
390                hNew = calculateHValue(i, j-1, dest); 
391                fNew = gNew + hNew; 
392  
393                // If it isn’t on the open list, add it to 
394                // the open list. Make the current square 
395                // the parent of this square. Record the 
396                // f, g, and h costs of the square cell 
397                //                OR 
398                // If it is on the open list already, check 
399                // to see if this path to that square is better, 
400                // using 'f' cost as the measure. 
401                if (cellDetails[i][j-1].f == FLT_MAX || 
402                        cellDetails[i][j-1].f > fNew) 
403                { 
404                    openList.insert( make_pair (fNew, 
405                                          make_pair (i, j-1))); 
406  
407                    // Update the details of this cell 
408                    cellDetails[i][j-1].f = fNew; 
409                    cellDetails[i][j-1].g = gNew; 
410                    cellDetails[i][j-1].h = hNew; 
411                    cellDetails[i][j-1].parent_i = i; 
412                    cellDetails[i][j-1].parent_j = j; 
413                } 
414            } 
415        } 
416  
417        //----------- 5th Successor (North-East) ------------ 
418  
419        // Only process this cell if this is a valid one 
420        if (isValid(i-1, j+1) == true) 
421        { 
422            // If the destination cell is the same as the 
423            // current successor 
424            if (isDestination(i-1, j+1, dest) == true) 
425            { 
426                // Set the Parent of the destination cell 
427                cellDetails[i-1][j+1].parent_i = i; 
428                cellDetails[i-1][j+1].parent_j = j; 
429                printf ("The destination cell is found\n"); 
430                tracePath (cellDetails, dest); 
431                foundDest = true; 
432                return; 
433            } 
434  
435            // If the successor is already on the closed 
436            // list or if it is blocked, then ignore it. 
437            // Else do the following 
438            else if (closedList[i-1][j+1] == false && 
439                     isUnBlocked(grid, i-1, j+1) == true) 
440            { 
441                gNew = cellDetails[i][j].g + 1.414; 
442                hNew = calculateHValue(i-1, j+1, dest); 
443                fNew = gNew + hNew; 
444  
445                // If it isn’t on the open list, add it to 
446                // the open list. Make the current square 
447                // the parent of this square. Record the 
448                // f, g, and h costs of the square cell 
449                //                OR 
450                // If it is on the open list already, check 
451                // to see if this path to that square is better, 
452                // using 'f' cost as the measure. 
453                if (cellDetails[i-1][j+1].f == FLT_MAX || 
454                        cellDetails[i-1][j+1].f > fNew) 
455                { 
456                    openList.insert( make_pair (fNew,  
457                                    make_pair(i-1, j+1))); 
458  
459                    // Update the details of this cell 
460                    cellDetails[i-1][j+1].f = fNew; 
461                    cellDetails[i-1][j+1].g = gNew; 
462                    cellDetails[i-1][j+1].h = hNew; 
463                    cellDetails[i-1][j+1].parent_i = i; 
464                    cellDetails[i-1][j+1].parent_j = j; 
465                } 
466            } 
467        } 
468  
469        //----------- 6th Successor (North-West) ------------ 
470  
471        // Only process this cell if this is a valid one 
472        if (isValid (i-1, j-1) == true) 
473        { 
474            // If the destination cell is the same as the 
475            // current successor 
476            if (isDestination (i-1, j-1, dest) == true) 
477            { 
478                // Set the Parent of the destination cell 
479                cellDetails[i-1][j-1].parent_i = i; 
480                cellDetails[i-1][j-1].parent_j = j; 
481                printf ("The destination cell is found\n"); 
482                tracePath (cellDetails, dest); 
483                foundDest = true; 
484                return; 
485            } 
486  
487            // If the successor is already on the closed 
488            // list or if it is blocked, then ignore it. 
489            // Else do the following 
490            else if (closedList[i-1][j-1] == false && 
491                     isUnBlocked(grid, i-1, j-1) == true) 
492            { 
493                gNew = cellDetails[i][j].g + 1.414; 
494                hNew = calculateHValue(i-1, j-1, dest); 
495                fNew = gNew + hNew; 
496  
497                // If it isn’t on the open list, add it to 
498                // the open list. Make the current square 
499                // the parent of this square. Record the 
500                // f, g, and h costs of the square cell 
501                //                OR 
502                // If it is on the open list already, check 
503                // to see if this path to that square is better, 
504                // using 'f' cost as the measure. 
505                if (cellDetails[i-1][j-1].f == FLT_MAX || 
506                        cellDetails[i-1][j-1].f > fNew) 
507                { 
508                    openList.insert( make_pair (fNew, make_pair (i-1, j-1))); 
509                    // Update the details of this cell 
510                    cellDetails[i-1][j-1].f = fNew; 
511                    cellDetails[i-1][j-1].g = gNew; 
512                    cellDetails[i-1][j-1].h = hNew; 
513                    cellDetails[i-1][j-1].parent_i = i; 
514                    cellDetails[i-1][j-1].parent_j = j; 
515                } 
516            } 
517        } 
518  
519        //----------- 7th Successor (South-East) ------------ 
520  
521        // Only process this cell if this is a valid one 
522        if (isValid(i+1, j+1) == true) 
523        { 
524            // If the destination cell is the same as the 
525            // current successor 
526            if (isDestination(i+1, j+1, dest) == true) 
527            { 
528                // Set the Parent of the destination cell 
529                cellDetails[i+1][j+1].parent_i = i; 
530                cellDetails[i+1][j+1].parent_j = j; 
531                printf ("The destination cell is found\n"); 
532                tracePath (cellDetails, dest); 
533                foundDest = true; 
534                return; 
535            } 
536  
537            // If the successor is already on the closed 
538            // list or if it is blocked, then ignore it. 
539            // Else do the following 
540            else if (closedList[i+1][j+1] == false && 
541                     isUnBlocked(grid, i+1, j+1) == true) 
542            { 
543                gNew = cellDetails[i][j].g + 1.414; 
544                hNew = calculateHValue(i+1, j+1, dest); 
545                fNew = gNew + hNew; 
546  
547                // If it isn’t on the open list, add it to 
548                // the open list. Make the current square 
549                // the parent of this square. Record the 
550                // f, g, and h costs of the square cell 
551                //                OR 
552                // If it is on the open list already, check 
553                // to see if this path to that square is better, 
554                // using 'f' cost as the measure. 
555                if (cellDetails[i+1][j+1].f == FLT_MAX || 
556                        cellDetails[i+1][j+1].f > fNew) 
557                { 
558                    openList.insert(make_pair(fNew,  
559                                        make_pair (i+1, j+1))); 
560  
561                    // Update the details of this cell 
562                    cellDetails[i+1][j+1].f = fNew; 
563                    cellDetails[i+1][j+1].g = gNew; 
564                    cellDetails[i+1][j+1].h = hNew; 
565                    cellDetails[i+1][j+1].parent_i = i; 
566                    cellDetails[i+1][j+1].parent_j = j; 
567                } 
568            } 
569        } 
570  
571        //----------- 8th Successor (South-West) ------------ 
572  
573        // Only process this cell if this is a valid one 
574        if (isValid (i+1, j-1) == true) 
575        { 
576            // If the destination cell is the same as the 
577            // current successor 
578            if (isDestination(i+1, j-1, dest) == true) 
579            { 
580                // Set the Parent of the destination cell 
581                cellDetails[i+1][j-1].parent_i = i; 
582                cellDetails[i+1][j-1].parent_j = j; 
583                printf("The destination cell is found\n"); 
584                tracePath(cellDetails, dest); 
585                foundDest = true; 
586                return; 
587            } 
588  
589            // If the successor is already on the closed 
590            // list or if it is blocked, then ignore it. 
591            // Else do the following 
592            else if (closedList[i+1][j-1] == false && 
593                     isUnBlocked(grid, i+1, j-1) == true) 
594            { 
595                gNew = cellDetails[i][j].g + 1.414; 
596                hNew = calculateHValue(i+1, j-1, dest); 
597                fNew = gNew + hNew; 
598  
599                // If it isn’t on the open list, add it to 
600                // the open list. Make the current square 
601                // the parent of this square. Record the 
602                // f, g, and h costs of the square cell 
603                //                OR 
604                // If it is on the open list already, check 
605                // to see if this path to that square is better, 
606                // using 'f' cost as the measure. 
607                if (cellDetails[i+1][j-1].f == FLT_MAX || 
608                        cellDetails[i+1][j-1].f > fNew) 
609                { 
610                    openList.insert(make_pair(fNew,  
611                                        make_pair(i+1, j-1))); 
612  
613                    // Update the details of this cell 
614                    cellDetails[i+1][j-1].f = fNew; 
615                    cellDetails[i+1][j-1].g = gNew; 
616                    cellDetails[i+1][j-1].h = hNew; 
617                    cellDetails[i+1][j-1].parent_i = i; 
618                    cellDetails[i+1][j-1].parent_j = j; 
619                } 
620            } 
621        } 
622    } 
623  
624    // When the destination cell is not found and the open 
625    // list is empty, then we conclude that we failed to 
626    // reach the destiantion cell. This may happen when the 
627    // there is no way to destination cell (due to blockages) 
628    if (foundDest == false) 
629        printf("Failed to find the Destination Cell\n"); 
630  
631    return; 
632} 
633  
634  
635// Driver program to test above function 
636int main() 
637{ 
638    /* Description of the Grid- 
639     1--> The cell is not blocked 
640     0--> The cell is blocked    */
641    int grid[ROW][COL] = 
642    { 
643        { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 }, 
644        { 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 }, 
645        { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 }, 
646        { 0, 0, 1, 0, 1, 0, 0, 0, 0, 1 }, 
647        { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 }, 
648        { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 }, 
649        { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 }, 
650        { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 }, 
651        { 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 } 
652    }; 
653  
654    // Source is the left-most bottom-most corner 
655    Pair src = make_pair(8, 0); 
656  
657    // Destination is the left-most top-most corner 
658    Pair dest = make_pair(0, 0); 
659  
660    aStarSearch(grid, src, dest); 
661  
662    return(0); 
663}

1from queue import PriorityQueue
2 
3#Creating Base Class
4class State(object):
5    def __init__(self, value, parent, start = 0, goal = 0):
6        self.children = []
7        self.parent = parent
8        self.value = value
9        self.dist = 0
10        if parent:
11            self.start = parent.start
12            self.goal = parent.goal
13            self.path = parent.path[:]
14            self.path.append(value)
15 
16        else:
17            self.path = [value]
18            self.start = start
19            self.goal = goal
20 
21    def GetDistance(self):
22        pass
23    def CreateChildren(self):
24        pass
25 
26 
27# Creating subclass
28class State_String(State):
29    def __init__(self, value, parent, start = 0, goal = 0 ):
30        super(State_String, self).__init__(value, parent, start, goal)
31        self.dist = self.GetDistance()
32 
33    def GetDistance(self):
34            if self.value == self.goal:
35                return 0
36            dist = 0
37            for i in range(len(self.goal)):
38                letter = self.goal[i]
39                dist += abs(i - self.value.index(letter))
40            return dist
41 
42    def CreateChildren(self):
43            if not self.children:
44                for i in range(len(self.goal)-1):
45                    val = self.value
46                    val = val[:i] + val[i+1] + val[i] + val[i+2:]
47                    child = State_String(val, self)
48                    self.children.append(child)
49 
50# Creating a class that hold the final magic
51class A_Star_Solver:
52    def __init__(self, start, goal):
53        self.path = []
54        self.vistedQueue =[]
55        self.priorityQueue = PriorityQueue()
56        self.start = start
57        self.goal = goal
58 
59    def Solve(self):
60        startState = State_String(self.start,0,self.start,self.goal)
61 
62        count = 0
63        self.priorityQueue.put((0,count, startState))
64        while(not self.path and self.priorityQueue.qsize()):
65               closesetChild = self.priorityQueue.get()[2]
66               closesetChild.CreateChildren()
67               self.vistedQueue.append(closesetChild.value)
68               for child in closesetChild.children:
69                   if child.value not in self.vistedQueue:
70                    count += 1
71                    if not child.dist:
72                       self.path = child.path
73                       break
74                    self.priorityQueue.put((child.dist,count,child))
75        if not self.path:
76            print("Goal Of  is not possible !" + self.goal )
77        return self.path
78 
79# Calling all the existing stuffs
80if __name__ == "__main__":
81    start1 = "hema"
82    goal1 = "mahe"
83    print("Starting....")
84    a = A_Star_Solver(start1,goal1)
85    a.Solve()
86    for i in range(len(a.path)):
87        print("{0}){1}".format(i,a.path[i]))

1/** Find the path from start to goal using A-Star search
2     *
3     * @param start The starting location
4     * @param goal The goal location
5     * @return The list of intersections that form the shortest path from
6     *   start to goal (including both start and goal).
7     */
8    public List<GeographicPoint> aStarSearch(GeographicPoint start,
9                                             GeographicPoint goal)
10    {
11 
12        MapNode startNode = pointNodeMap.get(start);
13        MapNode endNode = pointNodeMap.get(goal);
14 
15        // setup for A*
16        HashMap<MapNode,MapNode> parentMap = new HashMap<MapNode,MapNode>();
17        HashSet<MapNode> visited = new HashSet<MapNode>();
18        Map<MapNode, Double> distances = initializeAllToInfinity();
19 
20        Queue<MapNode> priorityQueue = initQueue();
21 
22        //  enque StartNode, with distance 0
23        startNode.setDistanceToStart(new Double(0));
24        distances.put(startNode, new Double(0));
25        priorityQueue.add(startNode);
26        MapNode current = null;
27 
28        while (!priorityQueue.isEmpty()) {
29            current = priorityQueue.remove();
30 
31            if (!visited.contains(current) ){
32                visited.add(current);
33                // if last element in PQ reached
34                if (current.equals(endNode)) return reconstructPath(parentMap, startNode, endNode, 0);
35 
36                Set<MapNode> neighbors = getNeighbors(current);
37                for (MapNode neighbor : neighbors) {
38                    if (!visited.contains(neighbor) ){  
39 
40                        // calculate predicted distance to the end node
41                        double predictedDistance = neighbor.getLocation().distance(endNode.getLocation());
42 
43                        // 1. calculate distance to neighbor. 2. calculate dist from start node
44                        double neighborDistance = current.calculateDistance(neighbor);
45                        double totalDistance = current.getDistanceToStart() + neighborDistance + predictedDistance;
46 
47                        // check if distance smaller
48                        if(totalDistance < distances.get(neighbor) ){
49                            // update n's distance
50                            distances.put(neighbor, totalDistance);
51                            // used for PriorityQueue
52                            neighbor.setDistanceToStart(totalDistance);
53                            neighbor.setPredictedDistance(predictedDistance);
54                            // set parent
55                            parentMap.put(neighbor, current);
56                            // enqueue
57                            priorityQueue.add(neighbor);
58                        }
59                    }
60                }
61            }
62        }
63        return null;
64    }