Each child is placed into a list of nodes -- the so called open list -- in order determined by search function evaluation (smaller values first). The heuristic function estimates 'how much work must be done to reach a goal from the node in question'. Typically, the search function is expressed as: Edit

f(n) = g(n) + h(n) Edit

where g(n) represents the (computed, actual) cost of getting to the node n along the current path to it, and h is the heuristic function. Thus, f(n) estimates the cost or effort to successfully get from start to goal by going through node n (along some particular path) 

Evaluation function
A common cost function g(-) is path length. The cost of getting from the start node to a current node is the length of relevant path. This can be computed incrementally.

It is important to realise that this kind of search can follow a contiguous path for a while, until some previously unchosen node has smallest f(-) value, in which case this node n is expanded, and its children considered.

Pseudocode Edit

  1. Start with the start node, place it in the (previously empty) list open.
  2. Let n be the first node on open. Remove n from open. Fail if open is empty.
  3. If n is the goal, then a solution has been found (optional: stop here).
  4. Expand n, obtaining all of its children, and evaluate f(-) for each item. Insert each of these children into open, maintaining order where the smallest f(-) values come first.
  5. Repeat from step 2.