  Communication
Free Faster access than browser!

# A* search algorithm

In computer science, A* (pronounced as "A star") is a computer algorithm that is widely used in pathfinding and graph traversal, which is the process of plotting an efficiently directed path between multiple points, called "nodes". 

62 relations: Admissible heuristic, Algorithm, Amortized analysis, Any-angle path planning, Anytime A*, Artificial intelligence, Association for Computing Machinery, Association for the Advancement of Artificial Intelligence, Bertram Raphael, Best-first search, Bidirectional search, Binary heap, Branch and bound, Branching factor, Breadth-first search, Computational complexity theory, Computer performance, Computer science, Consistent heuristic, D*, Depth-first search, Dijkstra's algorithm, Dynamic programming, Edsger W. Dijkstra, Euclidean distance, Fibonacci heap, Fringe search, Glossary of graph theory terms, Graph (abstract data type), Graph traversal, Greedy algorithm, Hash table, Heuristic, Heuristic (computer science), Incremental heuristic search, Institute of Electrical and Electronics Engineers, Iterative deepening A*, Journal of the ACM, Jump point search, Lifelong Planning A*, Linear programming, Logarithm, Motion planning, Natural language processing, Nils John Nilsson, Parsing, Pathfinding, Peter E. Hart, Princeton University, Priority queue, ... Expand index (12 more) »

In computer science, specifically in algorithms related to pathfinding, a heuristic function is said to be admissible if it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the lowest possible cost from the current point in the path.

## Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

## Amortized analysis

In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute.

## Any-angle path planning

Any-angle path planning algorithms are a subset of pathfinding algorithms that search for a path between two points in space and allow the turns in the path to have any angle.

## Anytime A*

In computer science, anytime A*, also known as anytime repairing A* (ARA*), is a variation of the A* search algorithm.

## Artificial intelligence

Artificial intelligence (AI, also machine intelligence, MI) is intelligence demonstrated by machines, in contrast to the natural intelligence (NI) displayed by humans and other animals.

## Association for Computing Machinery

The Association for Computing Machinery (ACM) is an international learned society for computing.

## Association for the Advancement of Artificial Intelligence

The Association for the Advancement of Artificial Intelligence (AAAI) is an international, nonprofit, scientific society devoted to promote research in, and responsible use of, artificial intelligence.

## Bertram Raphael

Bertram Raphael (born 1936) is an American computer scientist known for his contributions to artificial intelligence.

## Best-first search

Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule.

## Bidirectional search

Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph.

## Binary heap

A binary heap is a heap data structure that takes the form of a binary tree.

## Branch and bound

Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization.

## Branching factor

In computing, tree data structures, and game theory, the branching factor is the number of children at each node, the outdegree.

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures.

## Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

## Computer performance

Computer performance is the amount of work accomplished by a computer system.

## Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

## Consistent heuristic

In the study of path-finding problems in artificial intelligence, a heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the step cost of reaching that neighbor.

## D*

D* (pronounced "D star") is any one of the following three related incremental search algorithms.

## Depth-first search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.

## Dijkstra's algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.

## Dynamic programming

Dynamic programming is both a mathematical optimization method and a computer programming method.

## Edsger W. Dijkstra

Edsger Wybe Dijkstra (11 May 1930 – 6 August 2002) was a Dutch systems scientist, programmer, software engineer, science essayist, and early pioneer in computing science.

## Euclidean distance

In mathematics, the Euclidean distance or Euclidean metric is the "ordinary" straight-line distance between two points in Euclidean space.

## Fibonacci heap

In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees.

## Fringe search

In computer science, fringe search is a graph search algorithm that finds the least-cost path from a given initial node to one goal node.

## Glossary of graph theory terms

This is a glossary of graph theory terms.

## Graph (abstract data type)

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics, specifically the field of graph theory.

## Graph traversal

In computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph.

## Greedy algorithm

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum.

## Hash table

In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values.

## Heuristic

A heuristic technique (εὑρίσκω, "find" or "discover"), often called simply a heuristic, is any approach to problem solving, learning, or discovery that employs a practical method, not guaranteed to be optimal, perfect, logical, or rational, but instead sufficient for reaching an immediate goal.

## Heuristic (computer science)

In computer science, artificial intelligence, and mathematical optimization, a heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution.

## Incremental heuristic search

Incremental heuristic search algorithms combine both incremental and heuristic search to speed up searches of sequences of similar search problems, which is important in domains that are only incompletely known or change dynamically.

## Institute of Electrical and Electronics Engineers

The Institute of Electrical and Electronics Engineers (IEEE) is a professional association with its corporate office in New York City and its operations center in Piscataway, New Jersey.

## Iterative deepening A*

Iterative deepening A* (IDA*) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph.

## Journal of the ACM

The Journal of the ACM is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects.

## Jump point search

In computer science, Jump Point Search (JPS) is an optimization to the A* search algorithm for uniform-cost grids.

## Lifelong Planning A*

LPA* or Lifelong Planning A* is an incremental heuristic search algorithm based on A*.

## Linear programming

Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.

## Logarithm

In mathematics, the logarithm is the inverse function to exponentiation.

## Motion planning

Motion planning (also known as the navigation problem or the piano mover's problem) is a term used in robotics for the process of breaking down a desired movement task into discrete motions that satisfy movement constraints and possibly optimize some aspect of the movement.

## Natural language processing

Natural language processing (NLP) is an area of computer science and artificial intelligence concerned with the interactions between computers and human (natural) languages, in particular how to program computers to process and analyze large amounts of natural language data.

## Nils John Nilsson

Nils John Nilsson (born 1933) is an American computer scientist.

## Parsing

Parsing, syntax analysis or syntactic analysis is the process of analysing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar.

## Pathfinding

Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points.

## Peter E. Hart

Peter E. Hart (born c. 1940s) is an American computer scientist and entrepreneur.

## Princeton University

Princeton University is a private Ivy League research university in Princeton, New Jersey.

## Priority queue

In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it.

## Probabilistic context-free grammar

Grammar theory to model symbol strings originated from work in computational linguistics aiming to understand the structure of natural languages.

## Pseudocode

Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm.

## Reduced cost

In linear programming, reduced cost, or opportunity cost, is the amount by which an objective function coefficient would have to improve (so increase for maximization problem, decrease for minimization problem) before it would be possible for a corresponding variable to assume a positive value in the optimal solution.

## Search algorithm

In computer science, a search algorithm is any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain.

## Shakey the robot

Shakey the robot was the first general-purpose mobile robot to be able to reason about its own actions.

## SMA*

SMA* or Simplified Memory Bounded A* is a shortest path algorithm based on the A* algorithm.

## SRI International

SRI International (SRI) is an American nonprofit research institute headquartered in Menlo Park, California.

## Stack (abstract data type)

In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations.

## Theta*

Theta* is an any-angle path planning algorithm that is based on the A* search algorithm.

## Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

## Tree (data structure)

In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

## Vertex (graph theory)

In mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices).

## References

Hey! We are on Facebook now! »