|
In computer science, A* (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" h(x) that ranks each node x 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. To meet Wikipedias quality standards, this article or section may require cleanup. ...
The Bellman-Ford algorithm computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). ...
Best-first search is a search algorithm which optimizes breadth-first search by expanding the most promising node chosen according to some rule. ...
Bidirectional search is a graph search algorithm that runs two simultaneous searches: one forward from the initial state, and one backward from the goal, and stopping when the two meet in the middle. ...
In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. ...
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...
In Computer Science Depth-limited search is an algorithm to explore the Vertices of a Graph. ...
Dijkstras algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is a greedy algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights. ...
In computer science, the Floyd-Warshall algorithm (sometimes known as the Roy-Floyd algorithm since Bernard Roy described this algorithm in 1959. ...
Iterative deepening depth-first search or IDDFS is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches , the depth of the shallowest goal state. ...
Johnsons algorithm is a way to solve the all-pairs shortest path problem in a sparse, weighted, directed graph. ...
In computer science, uniform-cost search (UCS) is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph. ...
Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
Tree search algorithms are specialized versions of graph search algorithms, which take the properties of trees into account. ...
This article just presents the basic definitions. ...
In computer science, a goal node is a node in a graph that meets defined criteria for success or termination. ...
Best-first search is a search algorithm which optimizes breadth-first search by expanding the most promising node chosen according to some rule. ...
The algorithm was first described in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael. In their paper, it was called algorithm A; using this algorithm with an appropriate heuristic yields optimal behavior, hence A*. Nils J. Nilsson is one of the founding researchers in the discipline of Artificial intelligence. ...
Bertram Raphael (born 1936 in New York) is a computer scientist known for his contributions to artificial intelligence. ...
Look up Heuristic in Wiktionary, the free dictionary. ...
Generally speaking, Depth-first search and breadth-first search are two special cases of A* algorithm. Dijkstra's algorithm, as a BFS, is the special case of A* where h(x) = 0 for all x. For DFS, we may consider 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 decrese the counter C by one. Thus the early a node is discovered, the higher its h(x) value. Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...
In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. ...
Dijkstras algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is a greedy algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights. ...
Intuition
Consider the problem of route finding, for which A* 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 algorithms, it only builds routes that appear to lead towards the goal. Informed search algorithms are basically algorithms that solve problems using infomation that is not necessarily provided by the problem definition. ...
To know which routes will likely lead to the goal, A* employs a heuristic estimation 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.
What sets A* apart from 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. 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. Best-first search is a search algorithm which optimizes breadth-first search by expanding the most promising node chosen according to some rule. ...
Algorithm description
 A single-step simulation in a Visual Basic GUI (link see below) A* 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 x is determined by the function f(x) = g(x) + h(x) Image File history File links AStar. ...
Image File history File links AStar. ...
A priority queue is an ADT (abstract data type) supporting the following two operations: add an element to the queue with an associated priority remove the element from the queue that has the highest priority, and return it The simplest way to implement a priority queue data type is to...
Here, g(x) is the cost of the path so far, i.e. the weight of the edges followed so far. h(x) is the heuristic estimate of the minimal cost to reach the goal from x. 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. In mathematics, the Pythagorean theorem or Pythagoras theorem is a relation in Euclidean geometry among the three sides of a right triangle. ...
The lower f(x), the higher the priority (so a min-heap could be used to implement the queue). Example of a complete binary max heap In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). ...
function A*(start,goal) var closed := the empty set var q := make_queue(path(start)) while q is not empty var p := remove_first(q) var x := the last node of p if x in closed continue if x = goal return p add x to closed foreach y in successors(p) enqueue(q, y) return failure Here, successors(p) returns the set of paths created by extending p with one neighbor node. It is assumed that the queue maintains an ordering by f-value automatically.
In the closed set (closed), all the last node of p (nodes with paths found) are recorded, so as to avoid repetition and cycles (making this a graph search). The queue is sometimes analogously called the open set. The closed set can be omitted (yielding a tree search algorithm) if either a solution is guaranteed to exist, or if the successors function is adapted to reject cycles.
Properties Like breadth-first search, A* is complete in the sense that it will always find a solution if there is one. In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. ...
If the heuristic function h is admissible, meaning that it never overestimates the actual minimal cost of reaching the goal, then A* is itself admissible (or optimal) if we do not use a closed set. If a closed set is used, then h 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 pathes x,y where y is a successor of x:
 A* is also optimally efficient for any heuristic h, meaning that no algorithm employing the same heuristic will expand fewer nodes than A*, except when there are several partial solutions where h exactly predicts the cost of the optimal path.
Why A* is admissible and computationally optimal A* is both admissible and considers fewer nodes than any other admissible search algorithm, because A*'s 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.
When A* terminates its search, it by definition has 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.
Suppose now that some other search algorithm A terminates its search with a path whose actual cost is not less than the estimated cost of a path through some open node. Algorithm A cannot rule out the possibility, based on the heuristic information it has, that a path through that node might have a lower cost. So while A might consider fewer nodes than A*, it cannot be admissible. Accordingly, A* considers the fewest nodes of any admissible search algorithm that uses a no more accurate heuristic estimate.
Complexity The time complexity of A* 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: As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ...
In complexity theory, exponential time is the computation time of a problem where the time to complete the computation, m(n), is bounded by an exponential function of the problem size, n (i. ...
In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...
 where h * is the optimal heuristic, i.e. the exact cost to get from x to the goal. In other words, the error of h should not grow faster than the logarithm of the "perfect heuristic" h * that returns the true distance from x to the goal (Russell and Norvig 2003, p. 101). Logarithms to various bases: is to base e, is to base 10, and is to base 1. ...
More problematic than its time complexity is A*'s memory usage. In the worst case, it must also remember an exponential number of nodes. Several variants of A* have been developed to cope with this, including iterative deepening A*, memory-bounded A* (MA*) and simplified memory bounded A* (SMA*) and recursive best-first search (RBFS).
Another informed search algorithm that is optimal and complete if its heuristic is admissible is recursive best-first search (RBFS).
References - Dechter, Rina; Judea Pearl (1985). "Generalized best-first search strategies and the optimality af A*". Journal of the ACM 32 (3): pp. 505 - 536.
- Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics SSC4 (2): pp. 100–107.
- Hart, P. E.; Nilsson, N. J.; Raphael, B. (1972). "Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"". SIGART Newsletter 37: pp. 28–29.
- Nilsson, N. J. (1980). Principles of Artificial Intelligence. Palo Alto, California: Tioga Publishing Company. ISBN 0935382011.
- Pearl, Judea (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley. ISBN 0-201-05594-5.
- Russell, S. J.; Norvig, P. (2003). Artificial Intelligence: A Modern Approach, pp. 97-104. ISBN 0-13-790395-2.
The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ...
The Institute of Electrical and Electronics Engineers or IEEE (pronounced as eye-triple-e) is an international non-profit, professional organization for the advancement of technology related to electricity. ...
The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ...
Artificial Intelligence: A Modern Approach (ISBN 0137903952) (AIMA) is the current standard college text book on Artificial Intelligence and is written by Stuart J. Russell and Peter Norvig. ...
External links |
Feeds |
Contact