Posts Tagged ‘A* search algorithm’

Simplified Memory Bounded A* Search

September 4th, 2010 No comments

The Simplified Memory-Bounded Algorithm (SMA*) is a variant of A* search which is memory-bounded.

  • Complete & optimal if enough memory is available to store shallowest solution path.
  • To enqueue new expand, dequeue the unpromising node with highest f-cost.
  • Retains ancestor node information about the quality of the best path in the forgotten sub tree.

Regenerate forgotten node if all other paths look worse.

Iterative Deepening A* Search

September 4th, 2010 No comments

Modification of A* search use f-cost limit as depth bound

  • Increase threshold as minimum of f(.) of previous cycle
  • Each iteration expands all nodes inside the contour for current f-cost
  • complete and optimal
  • Same order of node expansion
  • Storage Efficient – practical

IDA* do not remember history

Therefore cannot avoid repeated states

A* Search

September 4th, 2010 No 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)).