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

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

- Start with the start node, place it in the (previously empty) list
**open**. - Let n be the first node on
**open**. Remove n from**open**. Fail if**open**is empty. - If n is the goal, then a solution has been found (optional: stop here).
- 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. - Repeat from step 2.