A* Search

September 4, 2010 Leave a comment Go to comments
An example of A star (A*) algorithm in action ...

Image via Wikipedia

A* uses a best-first search and finds the least-cost path from a given initial node to one goal node (out of one or more possible goals).

It uses a distance-plus-cost heuristic function (usually denoted f(x)) to determine the order in which the search visits nodes in the tree. The distance-plus-cost heuristic is a sum of two functions:

  • The path-cost function, which is the cost from the starting node to the current node (usually denoted g(x))
  • In addition, an admissible “heuristic estimate” of the distance to the goal (usually denoted h(x)).
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: