- (pronounced "A star") is a Graph/tree Search Algorithm that finds a path from a given initial Node to a given Goal Node (or one passing a given goal test). It employs a "heuristic estimate" that ranks each node by an estimate of the best route that goes through that node. It visits the nodes in order of this heuristic estimate. The A--- algorithm is therefore an example of Best-first Search .
- algorithm. Dijkstra's Algorithm , as another example of a best-first search algorithm, is the special case of A--- where for all . For depth-first search, we may consider that there is a global counter ''C'' initialized with a very big value. Every time, we process a node, we assign ''C'' to all of its newly discovered neighbors. After each single assignment, we decrease the counter ''C'' by one. Thus the earlier a node is discovered, the higher its h(x) value.
- is commonly used. A--- incrementally builds all routes leading from the starting point until it finds one that reaches the goal. But, like all Informed Search Algorithm s, it only builds routes that ''appear'' to lead towards the goal.
- employs a ''heuristic estimate'' of the distance from any given point to the goal. In the case of route finding, this may be the straight-line distance, which is usually an approximation of road distance.
- apart from Greedy Best-first Search is that it also takes the distance already travelled into account. This makes A--- ''complete'' and ''optimal'', i.e., A--- will always find the shortest route if any exists and if ''h(x)'' was chosen correctly. It is not guaranteed to perform better than simpler search algorithms. In a maze-like environment, the only way to reach the goal might be to first travel one way (away from the goal) and eventually turn around. In this case trying nodes closer to your destination first may cost you time.
- maintains a set of partial solutions, i.e. paths through the graph starting at the start node, stored in a Priority Queue . The priority assigned to a path is determined by the function
Here, is the cost of the path so far, i.e. the weight of the edges followed so far. is the heuristic estimate of the minimal cost to reach the goal from . For example, if "cost" is taken to mean distance travelled, the Straight Line Distance between two points on a map is a heuristic estimate of the distance to be travelled.
The lower , the higher the priority (so a Min-heap could be used to implement the queue).
- (start,goal)
closed := ''the empty set''
q := make_queue(path(start))
q ''is not empty''
p := remove_first(q)
x := ''the last node of p''
x '''in''' closed
x = goal
p
''add x to closed''
y '''in''' successors(x)
enqueue(q, p, y)
failure
The closed set can be omitted (yielding a tree search algorithm) if either a solution is guaranteed to exist, or if the Successors member is adapted to reject cycles.
- is ''complete'' in the sense that it will always find a solution if there is one.
- is itself admissible (or ''optimal'') ''if we do not use a closed set''. If a closed set is used, then must also be ''monotonic'' (or ''consistent'') for A--- to be optimal. This means that it never overestimates the cost of getting from a node to its neighbor. Formally, for all paths where is a successor of :
:
- is also ''optimally efficient'' for any heuristic , meaning that no algorithm employing the same heuristic will expand fewer nodes than A---, except when there are several partial solutions where exactly predicts the cost of the optimal path.
- IS ADMISSIBLE AND COMPUTATIONALLY OPTIMAL
- is both admissible and considers fewer nodes than any other admissible search algorithm with the same heuristic, because A--- works from an "optimistic" estimate of the cost of a path through every node that it considers -- optimistic in that the true cost of a path through that node to the goal will be at least as great as the estimate. But, critically, as far as A--- "knows", that optimistic estimate might be achievable.
- terminates its search, it has, by definition, found a path whose actual cost is lower than the estimated cost of any path through any open node. But since those estimates are optimistic, A--- can safely ignore those nodes. In other words, A--- will never overlook the possibility of a lower-cost path and so is admissible.
- , it cannot be admissible. Accordingly, A--- considers the fewest nodes of any admissible search algorithm that uses a no more accurate heuristic estimate.
- depends on the heuristic. In the worst case, the number of nodes expanded is Exponential in the length of the solution (the shortest path), but it is Polynomial when the heuristic function ''h'' meets the following condition:
|
