325:
407:
1318:
1298:, i.e., those that remain to be explored, and the filled ones are in the closed set. Color on each closed node indicates the distance from the goal: the greener, the closer. One can first see the A* moving in a straight line in the direction of the goal, then when hitting the obstacle, it explores alternative routes through the nodes from the open set.
415:
1361:
in the priority queue more than once (each entry corresponding to a different path to the node, and each with a different cost). A standard approach here is to check if a node about to be added already appears in the priority queue. If it does, then the priority and parent pointers are changed to correspond to the lower-cost path. A standard
3125:âA*-likeâ means the algorithm searches by extending paths originating at the start node one edge at a time, just as A* does. This excludes, for example, algorithms that search backward from the goal or in both directions simultaneously. In addition, the algorithms covered by this theorem must be admissible, and ânot more informedâ than A*.
1771:
A* by a large margin. However, more recent research found that this pathological case only occurs in certain contrived situations where the edge weight of the search graph is exponential in the size of the graph and that certain inconsistent (but admissible) heuristics can lead to a reduced number of node expansions in A* searches.
1338:
1758:
and admissible. The most interesting positive result they proved is that A*, with a consistent heuristic, is optimally efficient with respect to all admissible A*-like search algorithms on all "non-pathological" search problems. Roughly speaking, their notion of the non-pathological problem is what
1348:
There are a number of simple optimizations or implementation details that can significantly affect the performance of an A* implementation. The first detail to note is that the way the priority queue handles ties can have a significant effect on performance in some situations. If ties are broken so
1640:
value). When the heuristic is admissible, those estimates are optimistic (not quiteâsee the next paragraph), so A* can safely ignore those nodes because they cannot possibly lead to a cheaper solution than the one it already has. In other words, A* will never overlook the possibility of a lower-cost
1360:
When a path is required at the end of the search, it is common to keep with each node a reference to that node's parent. At the end of the search, these references can be used to recover the optimal path. If these references are being kept then it can be important that the same node doesn't appear
614:
The algorithm described so far gives us only the length of the shortest path. To find the actual sequence of steps, the algorithm can be easily revised so that each node on the path keeps track of its predecessor. After this algorithm is run, the ending node will point to its predecessor, and so on,
397:
The original 1968 A* paper contained a theorem stating that no A*-like algorithm could expand fewer nodes than A* if the heuristic function is consistent and A*'s tie-breaking rule is suitably chosen. A "correction" was published a few years later claiming that consistency was not required, but this
1770:
of node expansions (the number of iterations of A*'s main loop). When the heuristic being used is admissible but not consistent, it is possible for a node to be expanded by A* many times, an exponential number of times in the worst case. In such circumstances, Dijkstra's algorithm could outperform
1791:
While the admissibility criterion guarantees an optimal solution path, it also means that A* must examine all equally meritorious paths to find the optimal path. To compute approximate shortest paths, it is possible to speed up the search at the expense of optimality by relaxing the admissibility
315:
Compared to
Dijkstra's algorithm, the A* algorithm only finds the shortest path from a specified source to a specified goal, and not the shortest-path tree from a specified source to all possible goals. This is a necessary trade-off for using a specific-goal-directed heuristic. For Dijkstra's
1759:
we now mean by "up to tie-breaking". This result does not hold if A*'s heuristic is admissible but not consistent. In that case, Dechter and Pearl showed there exist admissible A*-like algorithms that can expand arbitrarily fewer nodes than A* on some non-pathological problems.
398:
was shown to be false in 1985 in
Dechter and Pearl's definitive study of A*'s optimality (now called optimal efficiency), which gave an example of A* with a heuristic that was admissible but not consistent expanding arbitrarily more nodes than an alternative A*-like algorithm.
2495:
1746:, the set of nodes expanded by A in solving P is a subset (possibly equal) of the set of nodes expanded by AâČ in solving P. The definitive study of the optimal efficiency of A* is due to Rina Dechter and Judea Pearl. They considered a variety of definitions of
2882:
of A* is roughly the same as that of all other graph search algorithms, as it keeps all generated nodes in memory. In practice, this turns out to be the biggest drawback of the A* search, leading to the development of memory-bounded heuristic searches, such as
453:
At each iteration of its main loop, A* needs to determine which of its paths to extend. It does so based on the cost of the path and an estimate of the cost required to extend the path all the way to the goal. Specifically, A* selects the path that minimizes
417:
421:
420:
416:
393:
of heuristic functions. A* was originally designed for finding least-cost paths when the cost of a path is the sum of its costs, but it has been shown that A* can be used to find optimal paths for any problem satisfying the conditions of a cost algebra.
422:
2064:
1317:
1267:
In this pseudocode, if a node is reached by one path, removed from openSet, and subsequently reached by a cheaper path, it will be added to openSet again. This is essential to guarantee that the path returned is optimal if the heuristic function is
3430:
Bertram
Raphael, who was directing work on Shakey at that time, observed that a better value for the score would be the sum of the distance traveled so far from the initial position plus my heuristic estimate of how far the robot had to
419:
336:, which had the aim of building a mobile robot that could plan its own actions. Nils Nilsson originally proposed using the Graph Traverser algorithm for Shakey's path planning. Graph Traverser is guided by a heuristic function
3393:
One of the first problems we considered was how to plan a sequence of 'way points' that Shakey could use in navigating from place to place. Shakey's navigation problem is a search problem, similar to ones I have mentioned
4264:
2382:
1337:
2720:
286:, it is generally outperformed by algorithms that can pre-process the graph to attain better performance, as well as by memory-bounded approaches; however, A* is still the best solution in many cases.
2377:
1954:
1780:
2842:
1284:
1616:
When A* terminates its search, it has found a path from start to goal whose actual cost is lower than the estimated cost of any path from start to goal through any open node (the node's
4349:
1575:
127:
2903:
problem in applications such as video games, but was originally designed as a general graph traversal algorithm. It finds applications in diverse problems, including the problem of
2529:
2138:
1530:, i.e. it will always find a solution (a path from start to goal) if one exists. On infinite graphs with a finite branching factor and edge costs that are bounded away from zero (
1961:
2282:
2213:
199:
514:
1595:
418:
599:
values of its neighbors are updated accordingly, and these neighbors are added to the queue. The algorithm continues until a removed node (thus the node with the lowest
426:
Illustration of A* search for finding a path between two points on a graph. From left to right, a heuristic that prefers points closer to the goal is used increasingly.
265:
4127:
Proceedings of the international workshop on planning under uncertainty for autonomous systems, international conference on automated planning and scheduling (ICAPS)
2978:
1423:
4130:
2095:
1509:
1476:
446:
of a graph, it aims to find a path to the given goal node having the smallest cost (least distance travelled, shortest time, etc.). It does this by maintaining a
1718:
1688:
1664:
1636:
4445:
4408:
1313:
An example of an A* algorithm in action where nodes are cities connected with roads and h(x) is the straight-line distance to the target point:
703:. With a consistent heuristic, A* is guaranteed to find an optimal path without processing any node more than once and A* is equivalent to running
1369:
that maps elements to their position in the heap, allowing this decrease-priority operation to be performed in logarithmic time. Alternatively, a
3803:"The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving"
2594:
The heuristic function has a major effect on the practical performance of A* search, since a good heuristic allows A* to prune away many of the
1333:(the shortest possible distance on a sphere) to the target. The algorithm is searching for a path between Washington, D.C., and Los Angeles.
3896:
561:â meaning that it never overestimates the actual cost to get to the goal â A* is guaranteed to return a least-cost path from start to goal.
4338:
4041:
Proceedings of the 2003 Human
Language Technology Conference of the North American Chapter of the Association for Computational Linguistics
3932:
633:
to the goal, since that is physically the smallest possible distance between any two points. For a grid map from a video game, using the
316:
algorithm, since the entire shortest-path tree is generated, every node is a goal, and there can be no specific-goal-directed heuristic.
4007:
3973:
2490:{\displaystyle w_{\alpha }(n)={\begin{cases}\lambda &g(\pi (n))\leq g({\tilde {n}})\\\Lambda &{\text{otherwise}}\end{cases}}}
4438:
4171:
1365:
based priority queue does not directly support the operation of searching for one of its elements, but it can be augmented with a
3802:
2619:
4397:
1276:. If the heuristic is consistent, when a node is removed from openSet the path to it is guaranteed to be optimal so the test â
228:, a source node and a goal node, the algorithm finds the shortest path (with respect to the given weights) from source to goal.
4546:
1792:
criterion. Oftentimes we want to bound this relaxation, so that we can guarantee that the solution path is no worse than (1 +
4699:
4380:
4016:
3836:
3785:
3747:
3459:
3228:
2300:
4694:
4431:
4320:
4119:
2297:
AlphA* attempts to promote depth-first exploitation by preferring recently expanded nodes. AlphA* uses the cost function
1873:
4524:
3982:
3204:
3179:
4063:
3722:
2749:
2609:, which can be determined empirically for a problem instance by measuring the number of nodes generated by expansion,
3641:
3611:
3423:
3386:
2140:. uses two heuristic functions. The first is the FOCAL list, which is used to select candidate nodes, and the second
450:
of paths originating at the start node and extending those paths one edge at a time until the goal node is reached.
568:
to perform the repeated selection of minimum (estimated) cost nodes to expand. This priority queue is known as the
1668:
values of open nodes are not guaranteed to be optimistic even if the heuristic is admissible. This is because the
2908:
2557:
1480:
value. Both
Dijkstra's algorithm and depth-first search can be implemented more efficiently without including an
4404:
2560:
of A* depends on the heuristic. In the worst case of an unbounded search space, the number of nodes expanded is
4611:
4529:
1533:
282:(the average number of successors per state), as it stores all generated nodes in memory. Thus, in practical
52:
4601:
3039:
3034:
3029:
2508:
2059:{\displaystyle w(n)={\begin{cases}1-{\frac {d(n)}{N}}&d(n)\leq N\\0&{\text{otherwise}}\end{cases}}}
309:
133:
42:
3009:
2111:
1854:
as the heuristic function, and perform the A* search as usual (which eventually happens faster than using
4684:
2912:
1861:
since fewer nodes are expanded). The path hence found by the search algorithm can have a cost of at most
4704:
4689:
4591:
2591:
from the start state; if it is not, and the state space is infinite, the algorithm will not terminate.
4679:
3292:
2230:
2161:
1388:, as another example of a uniform-cost search algorithm, can be viewed as a special case of A* where
431:
293:
143:
4660:
4634:
4188:
3092:, search for paths that are not limited to moving along graph edges but rather can take on any angle
2413:
1985:
460:
4649:
4263:
Fareh, Raouf; Baziyad, Mohammed; Rahman, Mohammad H.; Rabie, Tamer; Bettayeb, Maamar (2019-05-14).
2587:(the average number of successors per state). This assumes that a goal state exists at all, and is
2106:
Sampled
Dynamic Weighting uses sampling of nodes to better estimate and debias the heuristic error.
1329:
The A* algorithm has real-world applications. In this example, edges are railroads and h(x) is the
1580:
4709:
4596:
4568:
3914:
3692:
3659:
3105:
3089:
3019:
2942:
1443:
to all of its newly discovered neighbors. After every single assignment, we decrease the counter
1385:
1301:
704:
305:
4033:
905:// For node n, cameFrom is the node immediately preceding it on the cheapest path from the start
4639:
4606:
4487:
4475:
3047:
2884:
35:
3940:
3911:
Proceedings of the Eighth
International Joint Conference on Artificial Intelligence (IJCAI-83)
3631:
3601:
3564:
234:
4626:
4583:
3939:(Report). Institute for Production Technology, University of Southern Denmark. Archived from
3810:
Proceedings of the Third
International Joint Conference on Artificial Intelligence (IJCAI-73)
1641:
path from start to goal and so it will continue to search until no such possibilities exist.
1330:
447:
283:
2948:
1393:
4519:
4514:
4492:
4345:
3727:. Twenty-First International Joint Conference on Artificial Intelligence. pp. 634â639.
3335:
3095:
3077:
3057:
2598:
nodes that an uninformed search would expand. Its quality can be expressed in terms of the
2225:
are constants. If no nodes can be selected, the algorithm will backtrack with the function
1784:
1755:
1610:
1609:
if it is guaranteed to return an optimal solution. If the heuristic function used by A* is
1273:
1269:
962:// For node n, fScore := gScore + h(n). fScore represents our current best guess as to
700:
558:
390:
386:
2995:
except that beam search maintains a limit on the numbers of paths that it has to explore.
2739:
when the search space is a tree, there is a single goal state, and the heuristic function
2071:
1485:
1452:
1025:// This operation can occur in O(Log(N)) time if openSet is a min-heap or a priority queue
8:
4644:
4213:
2981:
1822:) is an admissible heuristic function, in the weighted version of the A* search one uses
1697:
443:
4148:
3339:
4616:
4541:
4292:
4245:
4225:
4086:
3877:
3603:
Geospatial
Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools
3545:
3526:
3499:
3480:
3351:
3326:
Doran, J. E.; Michie, D. (1966-09-20). "Experiments with the Graph
Traverser program".
3265:
3100:
1673:
1649:
1621:
1432:
1354:
926:// For node n, gScore is the cost of the cheapest path from start to n currently known.
638:
630:
4423:
3481:"Correction to 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths'"
3444:
893:// This is usually implemented as a min-heap or priority queue rather than a hash-set.
557:
to the goal. The heuristic function is problem-specific. If the heuristic function is
4563:
4504:
4376:
4370:
4319:(Technical report). Econometric Institute, Erasmus University Rotterdam. EI 2009-10.
4296:
4284:
4167:
4012:
3998:
3978:
3964:
3869:
3832:
3781:
3775:
3753:
3743:
3672:
3637:
3607:
3476:
3455:
3419:
3406:
3382:
3369:
3224:
3185:
3175:
3163:
3052:
1526:
On finite graphs with non-negative edge weights A* is guaranteed to terminate and is
435:
301:
4265:"Investigating Reduced Path Planning Strategy for Differential Wheeled Mobile Robot"
4090:
3355:
3269:
3134:
Goal nodes may be passed over multiple times if there remain other nodes with lower
1357:
among equal cost paths (avoiding exploring more than one equally optimal solution).
4276:
4249:
4235:
4163:
4078:
4044:
3881:
3861:
3824:
3701:
3668:
3579:
3549:
3535:
3503:
3491:
3343:
3308:
3257:
3216:
2985:
2924:
2879:
2584:
2561:
1730:
Algorithm A is optimally efficient with respect to a set of alternative algorithms
1350:
634:
333:
279:
267:
221:
136:
25:
3452:
Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI)
857:// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
4467:
4454:
4082:
3829:
Proceedings of the Tenth European Conference on Artificial Intelligence (ECAI-92)
3706:
3687:
3296:
3215:. Lecture Notes in Computer Science. Vol. 5515. Springer. pp. 117â139.
3208:
2927:
best-first search algorithm is that it takes the cost/distance already traveled,
2736:
2725:
Good heuristics are those with low effective branching factor (the optimal being
1291:
1287:
Illustration of A* search for finding path from a start node to a goal node in a
297:
210:
45:
3299:(1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths".
3220:
4458:
4311:
3865:
3657:
Martelli, Alberto (1977). "On the Complexity of Admissible Search Algorithms".
3410:
3373:
1374:
1370:
565:
439:
225:
4280:
3757:
3738:
Pohl, Ira (1970). "First results on the effect of error in heuristic search".
3261:
3189:
1130:// tentative_gScore is the distance from start to the neighbor through current
4673:
4558:
4288:
3563:
Nannicini, Giacomo; Delling, Daniel; Schultes, Dominik; Liberti, Leo (2012).
3312:
3288:
3024:
1779:
641:
becomes better depending on the set of movements available (4-way or 8-way).
289:
4048:
3495:
3213:
Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation
1439:
initialized with a very large value. Every time we process a node we assign
4094:
4002:
3968:
3873:
3347:
3167:
2588:
1283:
708:
328:
A* was invented by researchers working on Shakey the Robot's path planning.
324:
304:) first published the algorithm in 1968. It can be seen as an extension of
3852:
Pearl, Judea; Jin H. Kim (1982). "Studies in semi-admissible heuristics".
3080:
algorithm, but special care needs to be taken for the stopping criterion.
1435:
can be implemented using A* by considering that there is a global counter
4509:
2992:
2900:
1754:
in combination with A*'s heuristic being merely admissible or being both
1362:
1127:// d(current,neighbor) is the weight of the edge from current to neighbor
214:
4337:
Goldberg, Andrew V.; Harrelson, Chris; Kaplan, Haim; Werneck, Renato F.
1796:) times the optimal solution path. This new guarantee is referred to as
3004:
1366:
965:// how cheap a path could be from start to finish if it goes through n.
762:
4240:
3777:
Heuristics: Intelligent Search Strategies for Computer Problem Solving
3583:
3540:
3521:
1613:, then A* is admissible. An intuitive "proof" of this is as follows:
3600:
De Smith, Michael John; Goodchild, Michael F.; Longley, Paul (2007),
2862:
607:
value of that goal is then also the cost of the shortest path, since
550:
224:
due to its completeness, optimality, and optimal efficiency. Given a
217:
3633:
Python Algorithms: Mastering Basic Algorithms in the Python Language
2915:. Other cases include an Informational search with online learning.
1175:// This path to neighbor is better than any previous one. Record it!
410:
A* pathfinding algorithm navigating around a randomly-generated maze
274:
is the depth of the solution (the length of the shortest path) and
3913:. Vol. 2. Karlsruhe, Germany. pp. 789â791. Archived from
3522:"Generalized best-first search strategies and the optimality of A*"
3245:
1288:
406:
4230:
3443:
Edelkamp, Stefan; Jabbar, Shahid; Lluch-Lafuente, Alberto (2005).
2980:
for all nodes; in turn, both Dijkstra and A* are special cases of
1692:
values of open nodes are not guaranteed to be optimal, so the sum
1597:), A* is guaranteed to terminate only if there exists a solution.
2904:
887:// The set of discovered nodes that may need to be (re-)expanded.
3562:
3246:"Finding shortest paths on real road networks: the case for A*"
3070:
618:
As an example, when searching for the shortest route on a map,
4064:"A Group-Testing Algorithm with Online Informational Learning"
3854:
IEEE Transactions on Pattern Analysis and Machine Intelligence
2147:
is used to select the most promising node from the FOCAL list.
1447:
by one. Thus the earlier a node is discovered, the higher its
1373:
can perform the same decrease-priority operations in constant
3442:
3202:
4573:
4497:
3065:
2888:
2715:{\displaystyle N+1=1+b^{*}+(b^{*})^{2}+\dots +(b^{*})^{d}.}
2483:
2052:
553:
function that estimates the cost of the cheapest path from
4336:
4149:"General branch and bound, and its relation to Aâ and AOâ"
4118:
Ferguson, Dave; Likhachev, Maxim; Stentz, Anthony (2005).
3904:â an efficient near admissible heuristic search algorithm"
2945:
can be viewed as a special case of A* where the heuristic
580:. At each step of the algorithm, the node with the lowest
3565:"Bidirectional A* search on time-dependent road networks"
3250:
International Journal of Geographical Information Science
3599:
1783:
A* search that uses a heuristic that is 5.0(=Δ) times a
4553:
4536:
4453:
4262:
4117:
3014:
4313:
Yet another bidirectional algorithm for shortest paths
1536:
1294:
problem. The empty circles represent the nodes in the
3720:
3138:
values, as they may lead to a shorter path to a goal.
2984:. A* itself is a special case of a generalization of
2951:
2853:
is the optimal heuristic, the exact cost to get from
2752:
2622:
2511:
2385:
2372:{\displaystyle f_{\alpha }(n)=(1+w_{\alpha }(n))f(n)}
2303:
2233:
2164:
2114:
2074:
1964:
1876:
1700:
1676:
1652:
1624:
1583:
1488:
1455:
1396:
463:
237:
146:
55:
3894:
3301:
IEEE Transactions on Systems Science and Cybernetics
1644:
The actual proof is a bit more involved because the
4375:. Palo Alto, California: Tioga Publishing Company.
4339:"Efficient Point-to-Point Shortest Path Algorithms"
603:value out of all fringe nodes) is a goal node. The
4147:Nau, Dana S.; Kumar, Vipin; Kanal, Laveen (1984).
4061:
3822:
3519:
3474:
3287:
2972:
2836:
2714:
2523:
2489:
2371:
2276:
2207:
2132:
2089:
2058:
1949:{\displaystyle f(n)=g(n)+(1+\varepsilon w(n))h(n)}
1948:
1712:
1682:
1658:
1630:
1589:
1569:
1503:
1470:
1417:
508:
259:
193:
121:
16:Algorithm used for pathfinding and graph traversal
3243:
3211:(2009). "Engineering Route Planning Algorithms".
2564:in the depth of the solution (the shortest path)
1280:â will always fail if the node is reached again.
615:until some node's predecessor is the start node.
4671:
4034:"A* parsing: fast exact Viterbi parse selection"
3977:(2nd ed.). Prentice Hall. pp. 97â104.
3688:"Inconsistent heuristics in theory and practice"
3685:
2918:
2837:{\displaystyle |h(x)-h^{*}(x)|=O(\log h^{*}(x))}
611:at the goal is zero in an admissible heuristic.
3851:
3812:. Vol. 3. California, USA. pp. 11â17.
2103:is the anticipated length of the solution path.
1865:times that of the least cost path in the graph.
1521:
1253:// Open set is empty but goal was never reached
534:is the cost of the path from the start node to
385:. Peter Hart invented the concepts we now call
4055:
2613:, and the depth of the solution, then solving
4439:
4405:"A* Search Algorithm in JavaScript (Updated)"
4146:
3997:
3963:
3895:Ghallab, Malik; Dennis Allard (August 1983).
3823:Köll, Andreas; Hermann Kaindl (August 1992).
3595:
3593:
3162:
1725:
4032:Klein, Dan; Manning, Christopher D. (2003).
4031:
4011:(3rd ed.). Prentice Hall. p. 103.
3108: â Algorithm for finding shortest paths
438:, meaning that it is formulated in terms of
4402:
4218:Journal of Artificial Intelligence Research
3625:
3623:
3325:
890:// Initially, only the start node is known.
366:. Bertram Raphael suggested using the sum,
4446:
4432:
4211:
4120:"A Guide to Heuristic-based Path Planning"
4008:Artificial Intelligence: A Modern Approach
3974:Artificial Intelligence: A Modern Approach
3831:. Vienna, Austria: Wiley. pp. 16â17.
3769:
3767:
3724:Using Inconsistent Heuristics on A* Search
3679:
3606:, Troubadour Publishing Ltd, p. 344,
3590:
2857:to the goal. In other words, the error of
1326:green: start; blue: goal; orange: visited
308:. A* achieves better performance by using
4239:
4229:
3714:
3705:
3539:
3418:. Cambridge: Cambridge University Press.
3381:. Cambridge: Cambridge University Press.
3283:
3281:
3279:
3172:Artificial intelligence a modern approach
1868:Dynamic Weighting uses the cost function
1343:
3656:
3650:
3620:
1778:
1570:{\textstyle d(x,y)>\varepsilon >0}
1282:
413:
405:
323:
4368:
3959:
3957:
3764:
3742:. Edinburgh University Press: 219â236.
3721:Zhang, Zhifu; N. R. Sturtevant (2009).
3629:
3405:
3368:
695:denotes the length of that edge), then
122:{\displaystyle O(|E|\log |V|)=O(b^{d})}
4672:
3937:-admissible heuristic search algorithm
3276:
854:// A* finds a path from start to goal.
362:, the distance from the start node to
351:to the goal node: it entirely ignores
4427:
4411:from the original on 15 February 2020
4372:Principles of Artificial Intelligence
4309:
3991:
3930:
3825:"A new approach to dynamic weighting"
3773:
3515:
3513:
3412:The Quest for Artificial Intelligence
3375:The Quest for Artificial Intelligence
2524:{\displaystyle \lambda \leq \Lambda }
1774:
591:value is removed from the queue, the
4212:Hansen, Eric A.; Zhou, Rong (2007).
3954:
3800:
3737:
3158:
3156:
3154:
2871:that returns the true distance from
2133:{\displaystyle A_{\varepsilon }^{*}}
1722:is not guaranteed to be optimistic.
564:Typical implementations of A* use a
442:: starting from a specific starting
300:of Stanford Research Institute (now
231:One major practical drawback is its
4398:Hierarchical Path-Finding A* (HPA*)
3520:Dechter, Rina; Judea Pearl (1985).
3237:
3066:Simplified Memory bounded A* (SMA*)
2547:is the most recently expanded node.
1811:Weighted A*/Static Weighting's. If
648:satisfies the additional condition
347:, the estimated distance from node
13:
4362:
3686:Felner, Ariel; Uzi Zahavi (2011).
3510:
2518:
2470:
220:, which is used in many fields of
14:
4721:
4390:
4355:from the original on 18 May 2022.
3479:; Raphael, Bertram (1972-12-01).
3445:"Cost-Algebraic Heuristic Search"
3362:
3174:(4th ed.). Boston: Pearson.
3151:
1605:A search algorithm is said to be
4326:from the original on 2014-06-11.
4177:from the original on 2012-10-04.
4136:from the original on 2016-06-29.
3244:Zeng, W.; Church, R. L. (2009).
2899:A* is often used for the common
2156:selects nodes with the function
1762:Optimal efficiency is about the
1600:
1380:
1336:
1316:
4661:List of graph search algorithms
4330:
4303:
4256:
4205:
4181:
4140:
4111:
4025:
3924:
3888:
3845:
3816:
3794:
3731:
3556:
3468:
3128:
2894:
2743:meets the following condition:
2277:{\displaystyle Cf(n)+Dh_{F}(n)}
2208:{\displaystyle Af(n)+Bh_{F}(n)}
2099:is the depth of the search and
1787:, and obtains a suboptimal path
194:{\displaystyle O(|V|)=O(b^{d})}
3436:
3399:
3319:
3196:
3119:
3035:Generalized Adaptive A* (GAA*)
2961:
2955:
2861:will not grow faster than the
2831:
2828:
2822:
2803:
2793:
2789:
2783:
2767:
2761:
2754:
2700:
2686:
2668:
2654:
2463:
2457:
2448:
2439:
2436:
2430:
2424:
2402:
2396:
2366:
2360:
2354:
2351:
2345:
2326:
2320:
2314:
2271:
2265:
2246:
2240:
2202:
2196:
2177:
2171:
2084:
2078:
2026:
2020:
2006:
2000:
1974:
1968:
1943:
1937:
1931:
1928:
1922:
1907:
1901:
1895:
1886:
1880:
1552:
1540:
1498:
1492:
1465:
1459:
1406:
1400:
523:is the next node on the path,
509:{\displaystyle f(n)=g(n)+h(n)}
503:
497:
488:
482:
473:
467:
401:
254:
241:
188:
175:
166:
162:
154:
150:
116:
103:
94:
90:
82:
71:
63:
59:
1:
4062:Kagan E.; Ben-Gal I. (2014).
3145:
3048:Iterative deepening A* (IDA*)
2919:Relations to other algorithms
2551:
1516:
756:
4700:Game artificial intelligence
4168:10.1016/0004-3702(84)90004-3
4083:10.1080/0740817X.2013.803639
3707:10.1016/j.artint.2011.02.001
3673:10.1016/0004-3702(77)90002-9
3630:Hetland, Magnus Lie (2010),
3076:A* can also be adapted to a
3040:Incremental heuristic search
1590:{\displaystyle \varepsilon }
1522:Termination and completeness
1353:manner, A* will behave like
1278:tentative_gScore < gScore
7:
3221:10.1007/978-3-642-02094-0_7
3083:
3062:New Bidirectional A* (NBA*)
3058:Lifelong Planning A* (LPA*)
2998:
2865:of the "perfect heuristic"
1766:of nodes expanded, not the
209:(pronounced "A-star") is a
10:
4726:
4695:Combinatorial optimization
4214:"Anytime Heuristic Search"
3866:10.1109/TPAMI.1982.4767270
2923:What sets A* apart from a
1742:and every algorithm AâČ in
1738:if for every problem P in
1726:Optimality and consistency
1308:
1299:
332:A* was created as part of
319:
4658:
4625:
4582:
4466:
4281:10.1017/S0263574719000572
3801:Pohl, Ira (August 1973).
3262:10.1080/13658810801949850
2887:, memory-bounded A*, and
765:describes the algorithm:
432:informed search algorithm
132:
41:
31:
21:
4310:Pijls, Wim; Post, Henk.
3313:10.1109/TSSC.1968.300136
3112:
2941:Some common variants of
1807:-admissible algorithms:
908:// to n currently known.
767:
260:{\displaystyle O(b^{d})}
4569:Monte Carlo tree search
4396:Variation on A* called
4369:Nilsson, N. J. (1980).
4156:Artificial Intelligence
4049:10.3115/1073445.1073461
3693:Artificial Intelligence
3660:Artificial Intelligence
3636:, Apress, p. 214,
3496:10.1145/1056777.1056779
3090:Any-angle path planning
3030:Fringe Saving A* (FSA*)
2735:The time complexity is
1349:the queue behaves in a
701:monotone, or consistent
3740:Machine Intelligence 5
3348:10.1098/rspa.1966.0205
2974:
2973:{\displaystyle h(n)=0}
2885:Iterative deepening A*
2838:
2716:
2525:
2491:
2373:
2278:
2209:
2134:
2091:
2060:
1950:
1803:There are a number of
1788:
1714:
1684:
1660:
1632:
1591:
1571:
1505:
1472:
1419:
1418:{\displaystyle h(x)=0}
1344:Implementation details
1305:
631:straight-line distance
510:
427:
411:
329:
284:travel-routing systems
261:
195:
123:
4627:Minimum spanning tree
3931:Reese, BjĂžrn (1999).
3774:Pearl, Judea (1984).
3328:Proc. R. Soc. Lond. A
2975:
2839:
2717:
2526:
2492:
2374:
2279:
2210:
2135:
2092:
2061:
1951:
1782:
1734:on a set of problems
1715:
1685:
1661:
1633:
1592:
1572:
1506:
1473:
1420:
1331:great-circle distance
1286:
511:
425:
409:
327:
312:to guide its search.
262:
196:
124:
4612:Shortest path faster
4520:Breadth-first search
4515:Bidirectional search
4461:traversal algorithms
4346:Princeton University
4043:. pp. 119â126.
3106:Dijkstra's algorithm
3096:Breadth-first search
3078:bidirectional search
2949:
2943:Dijkstra's algorithm
2750:
2620:
2509:
2383:
2301:
2231:
2162:
2112:
2090:{\displaystyle d(n)}
2072:
1962:
1874:
1785:consistent heuristic
1698:
1674:
1650:
1622:
1581:
1534:
1513:value at each node.
1504:{\displaystyle h(x)}
1486:
1471:{\displaystyle h(x)}
1453:
1394:
1386:Dijkstra's algorithm
1302:Dijkstra's algorithm
705:Dijkstra's algorithm
691:of the graph (where
629:might represent the
461:
306:Dijkstra's algorithm
235:
144:
53:
4547:Iterative deepening
4193:theory.stanford.edu
3700:(9â10): 1570â1603.
3488:ACM SIGART Bulletin
3340:1966RSPSA.294..235D
2982:dynamic programming
2909:stochastic grammars
2539:) is the parent of
2505:are constants with
2129:
1713:{\displaystyle g+h}
4685:Routing algorithms
4542:Depth-first search
3780:. Addison-Wesley.
3527:Journal of the ACM
3164:Russell, Stuart J.
3101:Depth-first search
2970:
2834:
2712:
2521:
2487:
2482:
2369:
2274:
2205:
2130:
2115:
2087:
2056:
2051:
1946:
1789:
1775:Bounded relaxation
1710:
1680:
1656:
1628:
1587:
1567:
1501:
1468:
1433:depth-first search
1415:
1355:depth-first search
1306:
639:Chebyshev distance
506:
428:
412:
334:the Shakey project
330:
257:
191:
119:
4705:Greedy algorithms
4690:Search algorithms
4667:
4666:
4564:Jump point search
4505:Best-first search
4403:Brian Grinstead.
4382:978-0-935382-01-3
4241:10.1613/jair.2096
4129:. pp. 9â18.
4018:978-0-13-604259-4
3838:978-0-471-93608-4
3787:978-0-201-05594-8
3749:978-0-85224-176-9
3584:10.1002/NET.20438
3541:10.1145/3828.3830
3461:978-1-57735-236-5
3334:(1437): 235â259.
3230:978-3-642-02093-3
3053:Jump point search
2991:A* is similar to
2602:branching factor
2478:
2460:
2047:
2013:
1683:{\displaystyle g}
1659:{\displaystyle f}
1631:{\displaystyle f}
644:If the heuristic
436:best-first search
423:
302:SRI International
204:
203:
4717:
4680:Graph algorithms
4448:
4441:
4434:
4425:
4424:
4420:
4418:
4416:
4386:
4357:
4356:
4354:
4343:
4334:
4328:
4327:
4325:
4318:
4307:
4301:
4300:
4260:
4254:
4253:
4243:
4233:
4209:
4203:
4202:
4200:
4199:
4189:"Variants of A*"
4185:
4179:
4178:
4176:
4153:
4144:
4138:
4137:
4135:
4124:
4115:
4109:
4108:
4106:
4105:
4099:
4093:. Archived from
4071:IIE Transactions
4068:
4059:
4053:
4052:
4038:
4029:
4023:
4022:
3995:
3989:
3988:
3961:
3952:
3951:
3949:
3948:
3928:
3922:
3921:
3919:
3908:
3892:
3886:
3885:
3849:
3843:
3842:
3820:
3814:
3813:
3807:
3798:
3792:
3791:
3771:
3762:
3761:
3735:
3729:
3728:
3718:
3712:
3711:
3709:
3683:
3677:
3676:
3654:
3648:
3646:
3627:
3618:
3616:
3597:
3588:
3587:
3569:
3560:
3554:
3553:
3543:
3517:
3508:
3507:
3485:
3477:Nilsson, Nils J.
3475:Hart, Peter E.;
3472:
3466:
3465:
3449:
3440:
3434:
3433:
3417:
3407:Nilsson, Nils J.
3403:
3397:
3396:
3380:
3370:Nilsson, Nils J.
3366:
3360:
3359:
3323:
3317:
3316:
3285:
3274:
3273:
3241:
3235:
3234:
3207:; Schultes, D.;
3200:
3194:
3193:
3160:
3139:
3137:
3132:
3126:
3123:
2986:branch and bound
2979:
2977:
2976:
2971:
2938:, into account.
2937:
2880:space complexity
2874:
2870:
2860:
2856:
2852:
2843:
2841:
2840:
2835:
2821:
2820:
2796:
2782:
2781:
2757:
2731:
2721:
2719:
2718:
2713:
2708:
2707:
2698:
2697:
2676:
2675:
2666:
2665:
2650:
2649:
2612:
2608:
2597:
2585:branching factor
2582:
2578:
2567:
2530:
2528:
2527:
2522:
2496:
2494:
2493:
2488:
2486:
2485:
2479:
2476:
2462:
2461:
2453:
2395:
2394:
2378:
2376:
2375:
2370:
2344:
2343:
2313:
2312:
2285:
2283:
2281:
2280:
2275:
2264:
2263:
2216:
2214:
2212:
2211:
2206:
2195:
2194:
2139:
2137:
2136:
2131:
2128:
2123:
2098:
2096:
2094:
2093:
2088:
2065:
2063:
2062:
2057:
2055:
2054:
2048:
2045:
2014:
2009:
1995:
1957:
1955:
1953:
1952:
1947:
1853:
1846:
1721:
1719:
1717:
1716:
1711:
1691:
1689:
1687:
1686:
1681:
1667:
1665:
1663:
1662:
1657:
1639:
1637:
1635:
1634:
1629:
1596:
1594:
1593:
1588:
1576:
1574:
1573:
1568:
1512:
1510:
1508:
1507:
1502:
1479:
1477:
1475:
1474:
1469:
1426:
1424:
1422:
1421:
1416:
1340:
1320:
1279:
1260:
1257:
1254:
1251:
1248:
1245:
1242:
1239:
1236:
1233:
1230:
1227:
1224:
1221:
1218:
1215:
1212:
1209:
1206:
1203:
1202:tentative_gScore
1200:
1197:
1194:
1193:tentative_gScore
1191:
1188:
1185:
1182:
1179:
1176:
1173:
1170:
1167:
1166:tentative_gScore
1164:
1161:
1158:
1155:
1152:
1149:
1146:
1143:
1140:
1137:
1134:
1133:tentative_gScore
1131:
1128:
1125:
1122:
1119:
1116:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1077:
1076:reconstruct_path
1074:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1050:
1047:
1044:
1041:
1038:
1035:
1032:
1029:
1026:
1023:
1020:
1017:
1014:
1011:
1008:
1005:
1002:
999:
996:
993:
990:
987:
984:
981:
978:
975:
972:
969:
966:
963:
960:
957:
954:
951:
948:
945:
942:
939:
936:
933:
930:
927:
924:
921:
918:
915:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
867:
864:
861:
858:
855:
852:
849:
846:
843:
840:
837:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
773:reconstruct_path
771:
752:
698:
694:
690:
678:
647:
635:Taxicab distance
628:
610:
606:
602:
598:
594:
590:
556:
548:
537:
533:
522:
515:
513:
512:
507:
424:
384:
365:
361:
350:
346:
280:branching factor
277:
273:
268:space complexity
266:
264:
263:
258:
253:
252:
222:computer science
200:
198:
197:
192:
187:
186:
165:
157:
137:space complexity
128:
126:
125:
120:
115:
114:
93:
85:
74:
66:
26:Search algorithm
19:
18:
4725:
4724:
4720:
4719:
4718:
4716:
4715:
4714:
4670:
4669:
4668:
4663:
4654:
4621:
4578:
4462:
4452:
4414:
4412:
4393:
4383:
4365:
4363:Further reading
4360:
4352:
4341:
4335:
4331:
4323:
4316:
4308:
4304:
4261:
4257:
4210:
4206:
4197:
4195:
4187:
4186:
4182:
4174:
4151:
4145:
4141:
4133:
4122:
4116:
4112:
4103:
4101:
4097:
4066:
4060:
4056:
4036:
4030:
4026:
4019:
3999:Russell, Stuart
3996:
3992:
3985:
3965:Russell, Stuart
3962:
3955:
3946:
3944:
3929:
3925:
3917:
3906:
3902:
3893:
3889:
3850:
3846:
3839:
3821:
3817:
3805:
3799:
3795:
3788:
3772:
3765:
3750:
3736:
3732:
3719:
3715:
3684:
3680:
3655:
3651:
3644:
3628:
3621:
3614:
3598:
3591:
3567:
3561:
3557:
3518:
3511:
3483:
3473:
3469:
3462:
3447:
3441:
3437:
3426:
3415:
3404:
3400:
3389:
3378:
3367:
3363:
3324:
3320:
3286:
3277:
3242:
3238:
3231:
3201:
3197:
3182:
3161:
3152:
3148:
3143:
3142:
3135:
3133:
3129:
3124:
3120:
3115:
3086:
3001:
2950:
2947:
2946:
2928:
2921:
2897:
2872:
2866:
2858:
2854:
2848:
2816:
2812:
2792:
2777:
2773:
2753:
2751:
2748:
2747:
2726:
2703:
2699:
2693:
2689:
2671:
2667:
2661:
2657:
2645:
2641:
2621:
2618:
2617:
2610:
2603:
2595:
2580:
2569:
2565:
2558:time complexity
2554:
2510:
2507:
2506:
2481:
2480:
2475:
2473:
2467:
2466:
2452:
2451:
2419:
2409:
2408:
2390:
2386:
2384:
2381:
2380:
2339:
2335:
2308:
2304:
2302:
2299:
2298:
2259:
2255:
2232:
2229:
2228:
2226:
2190:
2186:
2163:
2160:
2159:
2157:
2154:
2145:
2124:
2119:
2113:
2110:
2109:
2073:
2070:
2069:
2067:
2050:
2049:
2044:
2042:
2036:
2035:
2015:
1996:
1994:
1981:
1980:
1963:
1960:
1959:
1875:
1872:
1871:
1869:
1859:
1848:
1839:
1828:
1823:
1816:
1777:
1728:
1699:
1696:
1695:
1693:
1675:
1672:
1671:
1669:
1651:
1648:
1647:
1645:
1623:
1620:
1619:
1617:
1603:
1582:
1579:
1578:
1577:for some fixed
1535:
1532:
1531:
1524:
1519:
1487:
1484:
1483:
1481:
1454:
1451:
1450:
1448:
1395:
1392:
1391:
1389:
1383:
1346:
1311:
1304:
1292:motion planning
1277:
1262:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1234:
1231:
1228:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1144:
1141:
1138:
1135:
1132:
1129:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1105:
1102:
1099:
1096:
1093:
1090:
1087:
1084:
1081:
1078:
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1015:
1012:
1009:
1006:
1003:
1000:
997:
994:
991:
988:
985:
982:
979:
976:
973:
970:
967:
964:
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
931:
928:
925:
922:
919:
916:
913:
910:
907:
904:
901:
898:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
832:
829:
826:
823:
820:
817:
814:
811:
808:
805:
802:
799:
796:
793:
790:
787:
784:
781:
778:
775:
772:
769:
759:
711:
696:
692:
680:
679:for every edge
649:
645:
619:
608:
604:
600:
596:
592:
581:
554:
539:
535:
524:
520:
462:
459:
458:
440:weighted graphs
414:
404:
367:
363:
352:
348:
337:
322:
298:Bertram Raphael
275:
271:
248:
244:
236:
233:
232:
211:graph traversal
182:
178:
161:
153:
145:
142:
141:
110:
106:
89:
81:
70:
62:
54:
51:
50:
17:
12:
11:
5:
4723:
4713:
4712:
4710:Graph distance
4707:
4702:
4697:
4692:
4687:
4682:
4665:
4664:
4659:
4656:
4655:
4653:
4652:
4650:Reverse-delete
4647:
4642:
4637:
4631:
4629:
4623:
4622:
4620:
4619:
4614:
4609:
4604:
4602:FloydâWarshall
4599:
4594:
4588:
4586:
4580:
4579:
4577:
4576:
4571:
4566:
4561:
4556:
4551:
4550:
4549:
4539:
4534:
4533:
4532:
4527:
4517:
4512:
4507:
4502:
4501:
4500:
4495:
4490:
4478:
4472:
4470:
4464:
4463:
4451:
4450:
4443:
4436:
4428:
4422:
4421:
4400:
4392:
4391:External links
4389:
4388:
4387:
4381:
4364:
4361:
4359:
4358:
4329:
4302:
4275:(2): 235â255.
4255:
4204:
4180:
4139:
4110:
4077:(2): 164â184.
4054:
4024:
4017:
3990:
3984:978-0137903955
3983:
3953:
3923:
3920:on 2014-08-06.
3900:
3887:
3860:(4): 392â399.
3844:
3837:
3815:
3793:
3786:
3763:
3748:
3730:
3713:
3678:
3649:
3642:
3619:
3612:
3589:
3578:(2): 240â251.
3555:
3534:(3): 505â536.
3509:
3467:
3460:
3435:
3424:
3409:(2009-10-30).
3398:
3387:
3372:(2009-10-30).
3361:
3318:
3275:
3256:(4): 531â543.
3236:
3229:
3195:
3181:978-0134610993
3180:
3149:
3147:
3144:
3141:
3140:
3127:
3117:
3116:
3114:
3111:
3110:
3109:
3103:
3098:
3093:
3085:
3082:
3074:
3073:
3068:
3063:
3060:
3055:
3050:
3045:
3042:
3037:
3032:
3027:
3022:
3017:
3012:
3007:
3000:
2997:
2969:
2966:
2963:
2960:
2957:
2954:
2920:
2917:
2896:
2893:
2845:
2844:
2833:
2830:
2827:
2824:
2819:
2815:
2811:
2808:
2805:
2802:
2799:
2795:
2791:
2788:
2785:
2780:
2776:
2772:
2769:
2766:
2763:
2760:
2756:
2723:
2722:
2711:
2706:
2702:
2696:
2692:
2688:
2685:
2682:
2679:
2674:
2670:
2664:
2660:
2656:
2653:
2648:
2644:
2640:
2637:
2634:
2631:
2628:
2625:
2553:
2550:
2549:
2548:
2520:
2517:
2514:
2484:
2474:
2472:
2469:
2468:
2465:
2459:
2456:
2450:
2447:
2444:
2441:
2438:
2435:
2432:
2429:
2426:
2423:
2420:
2418:
2415:
2414:
2412:
2407:
2404:
2401:
2398:
2393:
2389:
2368:
2365:
2362:
2359:
2356:
2353:
2350:
2347:
2342:
2338:
2334:
2331:
2328:
2325:
2322:
2319:
2316:
2311:
2307:
2295:
2294:are constants.
2273:
2270:
2267:
2262:
2258:
2254:
2251:
2248:
2245:
2242:
2239:
2236:
2204:
2201:
2198:
2193:
2189:
2185:
2182:
2179:
2176:
2173:
2170:
2167:
2152:
2148:
2143:
2127:
2122:
2118:
2107:
2104:
2086:
2083:
2080:
2077:
2053:
2043:
2041:
2038:
2037:
2034:
2031:
2028:
2025:
2022:
2019:
2016:
2012:
2008:
2005:
2002:
1999:
1993:
1990:
1987:
1986:
1984:
1979:
1976:
1973:
1970:
1967:
1945:
1942:
1939:
1936:
1933:
1930:
1927:
1924:
1921:
1918:
1915:
1912:
1909:
1906:
1903:
1900:
1897:
1894:
1891:
1888:
1885:
1882:
1879:
1866:
1857:
1837:
1826:
1814:
1776:
1773:
1727:
1724:
1709:
1706:
1703:
1679:
1655:
1627:
1602:
1599:
1586:
1566:
1563:
1560:
1557:
1554:
1551:
1548:
1545:
1542:
1539:
1523:
1520:
1518:
1515:
1500:
1497:
1494:
1491:
1467:
1464:
1461:
1458:
1414:
1411:
1408:
1405:
1402:
1399:
1382:
1379:
1375:amortized time
1371:Fibonacci heap
1345:
1342:
1310:
1307:
768:
761:The following
758:
755:
566:priority queue
517:
516:
505:
502:
499:
496:
493:
490:
487:
484:
481:
478:
475:
472:
469:
466:
403:
400:
321:
318:
256:
251:
247:
243:
240:
226:weighted graph
202:
201:
190:
185:
181:
177:
174:
171:
168:
164:
160:
156:
152:
149:
139:
130:
129:
118:
113:
109:
105:
102:
99:
96:
92:
88:
84:
80:
77:
73:
69:
65:
61:
58:
48:
39:
38:
33:
32:Data structure
29:
28:
23:
15:
9:
6:
4:
3:
2:
4722:
4711:
4708:
4706:
4703:
4701:
4698:
4696:
4693:
4691:
4688:
4686:
4683:
4681:
4678:
4677:
4675:
4662:
4657:
4651:
4648:
4646:
4643:
4641:
4638:
4636:
4633:
4632:
4630:
4628:
4624:
4618:
4615:
4613:
4610:
4608:
4605:
4603:
4600:
4598:
4595:
4593:
4590:
4589:
4587:
4585:
4584:Shortest path
4581:
4575:
4572:
4570:
4567:
4565:
4562:
4560:
4559:Fringe search
4557:
4555:
4552:
4548:
4545:
4544:
4543:
4540:
4538:
4535:
4531:
4528:
4526:
4525:Lexicographic
4523:
4522:
4521:
4518:
4516:
4513:
4511:
4508:
4506:
4503:
4499:
4496:
4494:
4491:
4489:
4486:
4485:
4484:
4483:
4479:
4477:
4474:
4473:
4471:
4469:
4465:
4460:
4456:
4449:
4444:
4442:
4437:
4435:
4430:
4429:
4426:
4410:
4406:
4401:
4399:
4395:
4394:
4384:
4378:
4374:
4373:
4367:
4366:
4351:
4347:
4340:
4333:
4322:
4315:
4314:
4306:
4298:
4294:
4290:
4286:
4282:
4278:
4274:
4270:
4266:
4259:
4251:
4247:
4242:
4237:
4232:
4227:
4223:
4219:
4215:
4208:
4194:
4190:
4184:
4173:
4169:
4165:
4161:
4157:
4150:
4143:
4132:
4128:
4121:
4114:
4100:on 2016-11-05
4096:
4092:
4088:
4084:
4080:
4076:
4072:
4065:
4058:
4050:
4046:
4042:
4035:
4028:
4020:
4014:
4010:
4009:
4004:
4003:Norvig, Peter
4000:
3994:
3986:
3980:
3976:
3975:
3970:
3969:Norvig, Peter
3966:
3960:
3958:
3943:on 2016-01-31
3942:
3938:
3936:
3927:
3916:
3912:
3905:
3903:
3891:
3883:
3879:
3875:
3871:
3867:
3863:
3859:
3855:
3848:
3840:
3834:
3830:
3826:
3819:
3811:
3804:
3797:
3789:
3783:
3779:
3778:
3770:
3768:
3759:
3755:
3751:
3745:
3741:
3734:
3726:
3725:
3717:
3708:
3703:
3699:
3695:
3694:
3689:
3682:
3674:
3670:
3666:
3662:
3661:
3653:
3645:
3643:9781430232377
3639:
3635:
3634:
3626:
3624:
3615:
3613:9781905886609
3609:
3605:
3604:
3596:
3594:
3585:
3581:
3577:
3573:
3566:
3559:
3551:
3547:
3542:
3537:
3533:
3529:
3528:
3523:
3516:
3514:
3505:
3501:
3497:
3493:
3490:(37): 28â29.
3489:
3482:
3478:
3471:
3463:
3457:
3453:
3446:
3439:
3432:
3427:
3425:9780521122931
3421:
3414:
3413:
3408:
3402:
3395:
3390:
3388:9780521122931
3384:
3377:
3376:
3371:
3365:
3357:
3353:
3349:
3345:
3341:
3337:
3333:
3329:
3322:
3314:
3310:
3306:
3302:
3298:
3294:
3293:Nilsson, N.J.
3290:
3284:
3282:
3280:
3271:
3267:
3263:
3259:
3255:
3251:
3247:
3240:
3232:
3226:
3222:
3218:
3214:
3210:
3206:
3203:Delling, D.;
3199:
3191:
3187:
3183:
3177:
3173:
3169:
3168:Norvig, Peter
3165:
3159:
3157:
3155:
3150:
3131:
3122:
3118:
3107:
3104:
3102:
3099:
3097:
3094:
3091:
3088:
3087:
3081:
3079:
3072:
3069:
3067:
3064:
3061:
3059:
3056:
3054:
3051:
3049:
3046:
3043:
3041:
3038:
3036:
3033:
3031:
3028:
3026:
3023:
3021:
3018:
3016:
3013:
3011:
3008:
3006:
3003:
3002:
2996:
2994:
2989:
2987:
2983:
2967:
2964:
2958:
2952:
2944:
2939:
2935:
2931:
2926:
2916:
2914:
2910:
2906:
2902:
2892:
2890:
2886:
2881:
2876:
2875:to the goal.
2869:
2864:
2851:
2825:
2817:
2813:
2809:
2806:
2800:
2797:
2786:
2778:
2774:
2770:
2764:
2758:
2746:
2745:
2744:
2742:
2738:
2733:
2729:
2709:
2704:
2694:
2690:
2683:
2680:
2677:
2672:
2662:
2658:
2651:
2646:
2642:
2638:
2635:
2632:
2629:
2626:
2623:
2616:
2615:
2614:
2606:
2601:
2592:
2590:
2586:
2576:
2572:
2563:
2559:
2546:
2542:
2538:
2534:
2515:
2512:
2504:
2500:
2454:
2445:
2442:
2433:
2427:
2421:
2416:
2410:
2405:
2399:
2391:
2387:
2363:
2357:
2348:
2340:
2336:
2332:
2329:
2323:
2317:
2309:
2305:
2296:
2293:
2289:
2268:
2260:
2256:
2252:
2249:
2243:
2237:
2234:
2224:
2220:
2199:
2191:
2187:
2183:
2180:
2174:
2168:
2165:
2155:
2149:
2146:
2125:
2120:
2116:
2108:
2105:
2102:
2081:
2075:
2039:
2032:
2029:
2023:
2017:
2010:
2003:
1997:
1991:
1988:
1982:
1977:
1971:
1965:
1940:
1934:
1925:
1919:
1916:
1913:
1910:
1904:
1898:
1892:
1889:
1883:
1877:
1867:
1864:
1860:
1851:
1844:
1840:
1833:
1829:
1821:
1817:
1810:
1809:
1808:
1806:
1801:
1800:-admissible.
1799:
1795:
1786:
1781:
1772:
1769:
1765:
1760:
1757:
1753:
1749:
1745:
1741:
1737:
1733:
1723:
1707:
1704:
1701:
1677:
1653:
1642:
1625:
1614:
1612:
1608:
1601:Admissibility
1598:
1584:
1564:
1561:
1558:
1555:
1549:
1546:
1543:
1537:
1529:
1514:
1495:
1489:
1462:
1456:
1446:
1442:
1438:
1434:
1430:
1412:
1409:
1403:
1397:
1387:
1381:Special cases
1378:
1376:
1372:
1368:
1364:
1358:
1356:
1352:
1341:
1339:
1334:
1332:
1327:
1325:
1321:
1319:
1314:
1303:
1297:
1293:
1290:
1285:
1281:
1275:
1271:
1266:
766:
764:
754:
750:
746:
742:
738:
734:
730:
726:
722:
718:
714:
710:
706:
702:
688:
684:
676:
672:
668:
664:
660:
656:
652:
642:
640:
636:
632:
626:
622:
616:
612:
588:
584:
579:
575:
571:
567:
562:
560:
552:
546:
542:
531:
527:
500:
494:
491:
485:
479:
476:
470:
464:
457:
456:
455:
451:
449:
445:
441:
437:
433:
408:
399:
395:
392:
388:
387:admissibility
382:
378:
374:
370:
359:
355:
344:
340:
335:
326:
317:
313:
311:
307:
303:
299:
295:
291:
287:
285:
281:
269:
249:
245:
238:
229:
227:
223:
219:
216:
212:
208:
183:
179:
172:
169:
158:
147:
140:
138:
135:
131:
111:
107:
100:
97:
86:
78:
75:
67:
56:
49:
47:
44:
40:
37:
34:
30:
27:
24:
20:
4592:BellmanâFord
4481:
4480:
4413:. Retrieved
4371:
4332:
4312:
4305:
4272:
4268:
4258:
4221:
4217:
4207:
4196:. Retrieved
4192:
4183:
4162:(1): 29â58.
4159:
4155:
4142:
4126:
4113:
4102:. Retrieved
4095:the original
4074:
4070:
4057:
4040:
4027:
4006:
3993:
3972:
3945:. Retrieved
3941:the original
3934:
3926:
3915:the original
3910:
3898:
3890:
3857:
3853:
3847:
3828:
3818:
3809:
3796:
3776:
3739:
3733:
3723:
3716:
3697:
3691:
3681:
3664:
3658:
3652:
3632:
3602:
3575:
3571:
3558:
3531:
3525:
3487:
3470:
3451:
3438:
3429:
3411:
3401:
3392:
3374:
3364:
3331:
3327:
3321:
3307:(2): 100â7.
3304:
3300:
3253:
3249:
3239:
3212:
3198:
3171:
3130:
3121:
3075:
2990:
2940:
2933:
2929:
2922:
2898:
2895:Applications
2877:
2867:
2849:
2846:
2740:
2734:
2727:
2724:
2604:
2599:
2593:
2574:
2570:
2555:
2544:
2540:
2536:
2532:
2502:
2498:
2291:
2287:
2222:
2218:
2150:
2141:
2100:
2066:, and where
1862:
1855:
1849:
1842:
1835:
1831:
1824:
1819:
1812:
1804:
1802:
1797:
1793:
1790:
1767:
1763:
1761:
1751:
1747:
1743:
1739:
1735:
1731:
1729:
1643:
1615:
1606:
1604:
1527:
1525:
1444:
1440:
1436:
1428:
1384:
1359:
1347:
1335:
1328:
1323:
1322:
1315:
1312:
1295:
1264:
1263:
760:
748:
744:
740:
736:
732:
728:
724:
720:
716:
712:
709:reduced cost
686:
682:
674:
670:
666:
662:
658:
654:
650:
643:
624:
620:
617:
613:
586:
582:
577:
573:
569:
563:
544:
540:
529:
525:
518:
452:
429:
396:
380:
376:
372:
368:
357:
353:
342:
338:
331:
314:
294:Nils Nilsson
288:
230:
206:
205:
4510:Beam search
4476:αâÎČ pruning
4224:: 267â297.
3933:AlphA*: An
3667:(1): 1â13.
3297:Raphael, B.
3289:Hart, P. E.
3205:Sanders, P.
2993:beam search
2901:pathfinding
2562:exponential
1363:binary heap
402:Description
391:consistency
215:pathfinding
46:performance
4674:Categories
4597:Dijkstra's
4415:8 February
4198:2023-06-09
4104:2016-02-12
3947:2014-11-05
3758:1067280266
3454:: 1362â7.
3209:Wagner, D.
3190:1021874142
3146:References
3044:Reduced A*
3005:Anytime A*
2737:polynomial
2552:Complexity
1756:consistent
1611:admissible
1607:admissible
1517:Properties
1431:. General
1367:hash table
1300:See also:
1274:consistent
1270:admissible
851:total_path
830:total_path
791:total_path
763:pseudocode
757:Pseudocode
699:is called
559:admissible
310:heuristics
290:Peter Hart
134:Worst-case
43:Worst-case
4640:Kruskal's
4635:BorĆŻvka's
4607:Johnson's
4297:181849209
4289:0263-5747
4231:1110.2737
4005:(2009) .
3971:(2003) .
2863:logarithm
2818:∗
2810:
2779:∗
2771:−
2695:∗
2681:⋯
2663:∗
2647:∗
2600:effective
2589:reachable
2519:Λ
2516:≤
2513:λ
2477:otherwise
2471:Λ
2458:~
2443:≤
2428:π
2417:λ
2392:α
2341:α
2310:α
2126:∗
2121:ε
2046:otherwise
2030:≤
1992:−
1917:ε
1585:ε
1559:ε
1272:but not
797:{current}
707:with the
551:heuristic
430:A* is an
218:algorithm
79:
4530:Parallel
4409:Archived
4350:Archived
4321:Archived
4269:Robotica
4172:Archived
4131:Archived
4091:18588494
3874:21869053
3572:Networks
3394:earlier.
3356:21698093
3270:14833639
3170:(2018).
3084:See also
3020:Field D*
3010:Block A*
2999:Variants
2579:, where
2497:, where
2379:, where
2286:, where
2217:, where
1958:, where
1528:complete
1427:for all
1296:open set
1247:neighbor
1223:neighbor
1214:neighbor
1178:cameFrom
1157:neighbor
1118:neighbor
1082:cameFrom
989:Infinity
950:Infinity
911:cameFrom
860:function
827:cameFrom
809:cameFrom
779:cameFrom
770:function
578:frontier
570:open set
4250:9832874
3882:3176931
3550:2092415
3504:6386648
3336:Bibcode
2905:parsing
2583:is the
2284:
2227:
2215:
2158:
2097:
2068:
1956:
1870:
1720:
1694:
1690:
1670:
1666:
1646:
1638:
1618:
1511:
1482:
1478:
1449:
1425:
1390:
1309:Example
1265:Remark:
1259:failure
1235:openSet
1232:openSet
1184:current
1151:current
1124:current
1106:current
1094:openSet
1088:current
1064:current
1043:openSet
1028:current
1013:openSet
980:default
941:default
902:{start}
896:openSet
842:current
836:prepend
821:current
803:current
785:current
637:or the
434:, or a
320:History
278:is the
4645:Prim's
4468:Search
4379:
4295:
4287:
4248:
4089:
4015:
3981:
3880:
3872:
3835:
3784:
3756:
3746:
3640:
3610:
3548:
3502:
3458:
3422:
3385:
3354:
3268:
3227:
3188:
3178:
3071:Theta*
3025:Fringe
2925:greedy
2907:using
2847:where
2543:, and
1852:> 1
1768:number
1256:return
1196:fScore
1187:gScore
1172:gScore
1139:gScore
1100:Remove
1073:return
1055:fScore
1052:lowest
1046:having
992:fScore
968:fScore
953:gScore
929:gScore
863:A_Star
848:return
574:fringe
538:, and
519:where
270:where
4617:Yen's
4455:Graph
4353:(PDF)
4342:(PDF)
4324:(PDF)
4317:(PDF)
4293:S2CID
4246:S2CID
4226:arXiv
4175:(PDF)
4152:(PDF)
4134:(PDF)
4123:(PDF)
4098:(PDF)
4087:S2CID
4067:(PDF)
4037:(PDF)
3918:(PDF)
3907:(PDF)
3878:S2CID
3806:(PDF)
3568:(PDF)
3546:S2CID
3500:S2CID
3484:(PDF)
3448:(PDF)
3416:(PDF)
3379:(PDF)
3352:S2CID
3266:S2CID
3113:Notes
2730:* = 1
1289:robot
1058:value
1022:empty
1010:while
1004:start
983:value
944:value
920:empty
869:start
800:while
549:is a
36:Graph
22:Class
4574:SSS*
4498:SMA*
4493:LPA*
4488:IDA*
4459:tree
4457:and
4417:2021
4377:ISBN
4285:ISSN
4013:ISBN
3979:ISBN
3870:PMID
3833:ISBN
3782:ISBN
3754:OCLC
3744:ISBN
3638:ISBN
3608:ISBN
3456:ISBN
3420:ISBN
3383:ISBN
3225:ISBN
3186:OCLC
3176:ISBN
2889:SMA*
2878:The
2556:The
2501:and
2290:and
2221:and
1834:) =
1750:and
1748:Alts
1744:Alts
1732:Alts
1562:>
1556:>
1351:LIFO
1324:Key:
1169:<
1115:each
1070:goal
1037:node
977:with
938:with
875:goal
815:Keys
743:) â
735:) +
723:) =
669:) +
657:) â€
595:and
448:tree
444:node
389:and
375:) +
296:and
213:and
4277:doi
4236:doi
4164:doi
4079:doi
4045:doi
3862:doi
3702:doi
3698:175
3669:doi
3580:doi
3536:doi
3492:doi
3431:go.
3344:doi
3332:294
3309:doi
3258:doi
3217:doi
2913:NLP
2911:in
2807:log
2732:).
1836:Δ h
1764:set
1241:add
1226:not
1112:for
1049:the
1034:the
1019:not
974:map
935:map
923:map
576:or
76:log
4676::
4554:D*
4537:B*
4482:A*
4407:.
4348:.
4344:.
4291:.
4283:.
4273:38
4271:.
4267:.
4244:.
4234:.
4222:28
4220:.
4216:.
4191:.
4170:.
4160:23
4158:.
4154:.
4125:.
4085:.
4075:46
4073:.
4069:.
4039:.
4001:;
3967:;
3956:^
3909:.
3876:.
3868:.
3856:.
3827:.
3808:.
3766:^
3752:.
3696:.
3690:.
3663:.
3622:^
3592:^
3576:59
3574:.
3570:.
3544:.
3532:32
3530:.
3524:.
3512:^
3498:.
3486:.
3450:.
3428:.
3391:.
3350:.
3342:.
3330:.
3303:.
3295:;
3291:;
3278:^
3264:.
3254:23
3252:.
3248:.
3223:.
3184:.
3166:;
3153:^
3015:D*
2988:.
2891:.
2568::
2531:,
1847:,
1377:.
1229:in
1220:if
1199::=
1190::=
1181::=
1163:if
1136::=
1121:of
1061:if
1040:in
1031::=
1016:is
995::=
986:of
971::=
956::=
947:of
932::=
917:an
914::=
899::=
824::=
806:in
794::=
753:.
731:,
719:,
713:d'
685:,
665:,
572:,
292:,
207:A*
4447:e
4440:t
4433:v
4419:.
4385:.
4299:.
4279::
4252:.
4238::
4228::
4201:.
4166::
4107:.
4081::
4051:.
4047::
4021:.
3987:.
3950:.
3935:Δ
3901:Δ
3899:A
3897:"
3884:.
3864::
3858:4
3841:.
3790:.
3760:.
3710:.
3704::
3675:.
3671::
3665:8
3647:.
3617:.
3586:.
3582::
3552:.
3538::
3506:.
3494::
3464:.
3358:.
3346::
3338::
3315:.
3311::
3305:4
3272:.
3260::
3233:.
3219::
3192:.
3136:f
2968:0
2965:=
2962:)
2959:n
2956:(
2953:h
2936:)
2934:n
2932:(
2930:g
2873:x
2868:h
2859:h
2855:x
2850:h
2832:)
2829:)
2826:x
2823:(
2814:h
2804:(
2801:O
2798:=
2794:|
2790:)
2787:x
2784:(
2775:h
2768:)
2765:x
2762:(
2759:h
2755:|
2741:h
2728:b
2710:.
2705:d
2701:)
2691:b
2687:(
2684:+
2678:+
2673:2
2669:)
2659:b
2655:(
2652:+
2643:b
2639:+
2636:1
2633:=
2630:1
2627:+
2624:N
2611:N
2607:*
2605:b
2596:b
2581:b
2577:)
2575:b
2573:(
2571:O
2566:d
2545:ñ
2541:n
2537:n
2535:(
2533:Ï
2503:Î
2499:λ
2464:)
2455:n
2449:(
2446:g
2440:)
2437:)
2434:n
2431:(
2425:(
2422:g
2411:{
2406:=
2403:)
2400:n
2397:(
2388:w
2367:)
2364:n
2361:(
2358:f
2355:)
2352:)
2349:n
2346:(
2337:w
2333:+
2330:1
2327:(
2324:=
2321:)
2318:n
2315:(
2306:f
2292:D
2288:C
2272:)
2269:n
2266:(
2261:F
2257:h
2253:D
2250:+
2247:)
2244:n
2241:(
2238:f
2235:C
2223:B
2219:A
2203:)
2200:n
2197:(
2192:F
2188:h
2184:B
2181:+
2178:)
2175:n
2172:(
2169:f
2166:A
2153:Δ
2151:A
2144:F
2142:h
2117:A
2101:N
2085:)
2082:n
2079:(
2076:d
2040:0
2033:N
2027:)
2024:n
2021:(
2018:d
2011:N
2007:)
2004:n
2001:(
1998:d
1989:1
1983:{
1978:=
1975:)
1972:n
1969:(
1966:w
1944:)
1941:n
1938:(
1935:h
1932:)
1929:)
1926:n
1923:(
1920:w
1914:+
1911:1
1908:(
1905:+
1902:)
1899:n
1896:(
1893:g
1890:=
1887:)
1884:n
1881:(
1878:f
1863:Δ
1858:a
1856:h
1850:Δ
1845:)
1843:n
1841:(
1838:a
1832:n
1830:(
1827:w
1825:h
1820:n
1818:(
1815:a
1813:h
1805:Δ
1798:Δ
1794:Δ
1752:P
1740:P
1736:P
1708:h
1705:+
1702:g
1678:g
1654:f
1626:f
1565:0
1553:)
1550:y
1547:,
1544:x
1541:(
1538:d
1499:)
1496:x
1493:(
1490:h
1466:)
1463:x
1460:(
1457:h
1445:C
1441:C
1437:C
1429:x
1413:0
1410:=
1407:)
1404:x
1401:(
1398:h
1250:)
1244:(
1238:.
1217:)
1211:(
1208:h
1205:+
1160:)
1154:,
1148:(
1145:d
1142:+
1109:)
1103:(
1097:.
1091:)
1085:,
1079:(
1067:=
1007:)
1001:(
998:h
959:0
884:)
881:h
878:,
872:,
866:(
845:)
839:(
833:.
818::
812:.
788:)
782:,
776:(
751:)
749:x
747:(
745:h
741:y
739:(
737:h
733:y
729:x
727:(
725:d
721:y
717:x
715:(
697:h
693:d
689:)
687:y
683:x
681:(
677:)
675:y
673:(
671:h
667:y
663:x
661:(
659:d
655:x
653:(
651:h
646:h
627:)
625:x
623:(
621:h
609:h
605:f
601:f
597:g
593:f
589:)
587:x
585:(
583:f
555:n
547:)
545:n
543:(
541:h
536:n
532:)
530:n
528:(
526:g
521:n
504:)
501:n
498:(
495:h
492:+
489:)
486:n
483:(
480:g
477:=
474:)
471:n
468:(
465:f
383:)
381:n
379:(
377:h
373:n
371:(
369:g
364:n
360:)
358:n
356:(
354:g
349:n
345:)
343:n
341:(
339:h
276:b
272:d
255:)
250:d
246:b
242:(
239:O
189:)
184:d
180:b
176:(
173:O
170:=
167:)
163:|
159:V
155:|
151:(
148:O
117:)
112:d
108:b
104:(
101:O
98:=
95:)
91:|
87:V
83:|
72:|
68:E
64:|
60:(
57:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
