Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Free
Faster access than browser!
 

A* search algorithm

Index 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". [1]

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, ..., Probabilistic context-free grammar, Pseudocode, Reduced cost, Search algorithm, Shakey the robot, SMA*, SRI International, Stack (abstract data type), Theta*, Time complexity, Tree (data structure), Vertex (graph theory). Expand index (12 more) »

Admissible heuristic

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.

New!!: A* search algorithm and Admissible heuristic · See more »

Algorithm

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

New!!: A* search algorithm and Algorithm · See more »

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.

New!!: A* search algorithm and Amortized analysis · See more »

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.

New!!: A* search algorithm and Any-angle path planning · See more »

Anytime A*

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

New!!: A* search algorithm and Anytime A* · See more »

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.

New!!: A* search algorithm and Artificial intelligence · See more »

Association for Computing Machinery

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

New!!: A* search algorithm and Association for Computing Machinery · See more »

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.

New!!: A* search algorithm and Association for the Advancement of Artificial Intelligence · See more »

Bertram Raphael

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

New!!: A* search algorithm and Bertram Raphael · See more »

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.

New!!: A* search algorithm and Best-first search · See more »

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.

New!!: A* search algorithm and Bidirectional search · See more »

Binary heap

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

New!!: A* search algorithm and Binary heap · See more »

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.

New!!: A* search algorithm and Branch and bound · See more »

Branching factor

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

New!!: A* search algorithm and Branching factor · See more »

Breadth-first search

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

New!!: A* search algorithm and Breadth-first search · See more »

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.

New!!: A* search algorithm and Computational complexity theory · See more »

Computer performance

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

New!!: A* search algorithm and Computer performance · See more »

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.

New!!: A* search algorithm and Computer science · See more »

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.

New!!: A* search algorithm and Consistent heuristic · See more »

D*

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

New!!: A* search algorithm and D* · See more »

Depth-first search

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

New!!: A* search algorithm and Depth-first search · See more »

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.

New!!: A* search algorithm and Dijkstra's algorithm · See more »

Dynamic programming

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

New!!: A* search algorithm and Dynamic programming · See more »

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.

New!!: A* search algorithm and Edsger W. Dijkstra · See more »

Euclidean distance

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

New!!: A* search algorithm and Euclidean distance · See more »

Fibonacci heap

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

New!!: A* search algorithm and Fibonacci heap · See more »

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.

New!!: A* search algorithm and Fringe search · See more »

Glossary of graph theory terms

This is a glossary of graph theory terms.

New!!: A* search algorithm and Glossary of graph theory terms · See more »

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.

New!!: A* search algorithm and Graph (abstract data type) · See more »

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.

New!!: A* search algorithm and Graph traversal · See more »

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.

New!!: A* search algorithm and Greedy algorithm · See more »

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.

New!!: A* search algorithm and Hash table · See more »

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.

New!!: A* search algorithm and Heuristic · See more »

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.

New!!: A* search algorithm and Heuristic (computer science) · See more »

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.

New!!: A* search algorithm and Incremental heuristic search · See more »

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.

New!!: A* search algorithm and Institute of Electrical and Electronics Engineers · See more »

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.

New!!: A* search algorithm and Iterative deepening A* · See more »

Journal of the ACM

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

New!!: A* search algorithm and Journal of the ACM · See more »

Jump point search

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

New!!: A* search algorithm and Jump point search · See more »

Lifelong Planning A*

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

New!!: A* search algorithm and Lifelong Planning A* · See more »

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.

New!!: A* search algorithm and Linear programming · See more »

Logarithm

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

New!!: A* search algorithm and Logarithm · See more »

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.

New!!: A* search algorithm and Motion planning · See more »

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.

New!!: A* search algorithm and Natural language processing · See more »

Nils John Nilsson

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

New!!: A* search algorithm and Nils John Nilsson · See more »

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.

New!!: A* search algorithm and Parsing · See more »

Pathfinding

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

New!!: A* search algorithm and Pathfinding · See more »

Peter E. Hart

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

New!!: A* search algorithm and Peter E. Hart · See more »

Princeton University

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

New!!: A* search algorithm and Princeton University · See more »

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.

New!!: A* search algorithm and Priority queue · See more »

Probabilistic context-free grammar

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

New!!: A* search algorithm and Probabilistic context-free grammar · See more »

Pseudocode

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

New!!: A* search algorithm and Pseudocode · See more »

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.

New!!: A* search algorithm and Reduced cost · See more »

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.

New!!: A* search algorithm and Search algorithm · See more »

Shakey the robot

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

New!!: A* search algorithm and Shakey the robot · See more »

SMA*

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

New!!: A* search algorithm and SMA* · See more »

SRI International

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

New!!: A* search algorithm and SRI International · See more »

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.

New!!: A* search algorithm and Stack (abstract data type) · See more »

Theta*

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

New!!: A* search algorithm and Theta* · See more »

Time complexity

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

New!!: A* search algorithm and Time complexity · See more »

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.

New!!: A* search algorithm and Tree (data structure) · See more »

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).

New!!: A* search algorithm and Vertex (graph theory) · See more »

Redirects here:

A Star, A Star Search Algorithm, A star, A star search, A star search algorithm, A*, A* algorithm, A* search, A-star, A-star algorithm, A-star search algorithm, TBA*.

References

[1] https://en.wikipedia.org/wiki/A*_search_algorithm

OutgoingIncoming
Hey! We are on Facebook now! »