A* search algorithm facts for kids

A* (pronounced "A star") is a clever set of steps, called an algorithm, that computers use to find the best way to get from one place to another. Imagine you have a map with many locations and you know how difficult it is to travel directly between them. A* can quickly tell you the fastest or easiest path.

It's a bit like Dijkstra's algorithm, but A* is smarter. It makes good guesses about which direction to go, so it doesn't waste time exploring slow or wrong paths. A* is perfect when you only need to find the path between two specific points. If you need to find many paths on the same map, other algorithms like the Floyd–Warshall algorithm might be faster. A* won't help if you need to visit several places on one trip, which is a different kind of puzzle called the Travelling salesman problem.

How A* Finds the Best Path

Let's use an example to understand how A* works. Imagine you want to go from point A to point Z. There are other points in between, like B, C, D, and E.

• A connects to B and C.
• B and C connect to D and E.
• D and E connect to Z.

This means there are four possible ways to get from A to Z:

• A-B-D-Z
• A-C-D-Z
• A-B-E-Z
• A-C-E-Z

Step-by-Step Journey

First, the computer looks at how hard it is to get from A to B, and from A to C. This "difficulty" is called the "cost." The cost for a place means how hard it is to reach that place from A. The computer writes down these costs.

Next, the computer looks at B. It checks how hard it is to get from B to D. It adds this to B's cost to find a total cost for D. It writes this down. Then, it looks at C. It checks how hard it is to get from C to D. It adds this to C's cost. This gives a different total cost for D.

The computer always wants the best path. So, if the new cost for D (from C) is less than the old cost for D (from B), it replaces the old one. It only remembers the path that is faster. It will keep only one of A-B-D or A-C-D, whichever is quicker.

The computer continues this process. It finds the fastest way to get to E. Finally, it calculates the cost from D to Z and from E to Z. It adds these to the best costs for D and E. The smallest total cost it finds for Z is the answer. Now the computer knows the fastest way!

Why A* is Faster than Dijkstra's Algorithm

The steps described above are similar to Dijkstra's algorithm. Dijkstra's algorithm can be slow. It might explore many places that are far from the goal. For example, if you're looking for a path between two nearby cities, Dijkstra's might explore roads in a completely different state!

A* solves this problem. You give the computer a smart guess about how far each place is from the final destination. This guess is called a heuristic. For example, if you're finding a path on a map, a good guess is the straight-line distance to the end point. The real path will be longer, but this guess helps A* choose the right direction.

Instead of just picking the place nearest to A, A* looks at the place that will probably have the lowest total cost. It finds this total by adding the cost to reach that place from A, plus the guessed distance left to the end. This way, A* focuses its search in the right direction. Even a simple guess can make the program much faster.

In computer science, each "place" is called a vertex, and each "path" between two places is an edge. These are terms from graph theory.

What A* is Used For

A* is one of many algorithms that find paths. They are all called path-finding algorithms. The "places" and "paths" aren't always real roads or cities. They can be ideas or steps in a process.

Real-World Examples

• Navigation Apps: When you use Google Maps or Mapquest to find a road trip, A* helps. The "paths" are roads, and the "places" are houses or cities.
• Internet Routers: When you send information over the Internet, it travels through many computers. Many routers use A* to find the best way to send your information quickly. Here, the "paths" are cables, and the "places" are computers.
• Chemical Reactions: Imagine you want to make a certain chemical from ingredients you have. Mixing some ingredients makes new chemicals. A path-finding algorithm can tell you the best order to mix them. Here, the "paths" are chemical reactions, the "cost" is how long the reaction takes, and the "places" are the different chemicals you can make.

Images for kids

• 

  A* was invented by researchers working on Shakey the Robot's path planning.

• 

  A* pathfinding algorithm navigating around a randomly-generated maze

• 

  Illustration of A* search for finding path from a start node to a goal node in a robot motion planning problem. The empty circles represent the nodes in the open set, 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.

  See also: Dijkstra's algorithm
• 

  An example of A* algorithm in action (nodes are cities connected with roads, h(x) is the straight-line distance to target point) Green: Start, Blue: Target, Orange: Visited

• 

  The A* algorithm finding a path of railroads between Washington, D.C. and Los Angeles.

• 

  A* search that uses a heuristic that is 5.0(=ε) times a consistent heuristic, and obtains a suboptimal path.

See also

In Spanish: Algoritmo de búsqueda A* para niños