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:[]
f(n) = g(n) + h(n)[]
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[]
- 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.