Archive

Posts Tagged ‘Data structure’

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.

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

Best-First Search (Greedy Search)

September 4th, 2010 2 comments

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

Judea Pearl described best-first search as estimating the promise of node n by a “heuristic evaluation function f(n) which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain.”

Some authors have used “best-first search” to refer specifically to a search with a heuristic that attempts to predict how close the end of a path is to a solution, so that paths, which are judged closer to a solution, are extended first. This specific type of search is called greedy best-first search.

Efficient selection of the current best candidate for extension is typically implemented using a priority queue

Depth First Search

September 4th, 2010 No comments

Depth First Search

Depth First Search

Formally, DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it has not finished exploring. In a non-recursive implementation, all freshly expanded nodes are added to a stack for exploration.