Algorithm A
A is a general graph search algorithm, developed by Nilsson.
Evaluation Function
It uses an evaluation function \(f(n)\) of the form:
-
\(f(n) \rightarrow\) an estimate of the actual cost of an optimal path from start node \(s\) to a goal node, through \(n\).
-
\(g(n) \rightarrow\) the minimum of the costs of all paths so far discovered by algorithm A from start node \(s\) to node \(n\).
-
\(h(n) \rightarrow\) an estimate of the actual cost of an optimal path from node \(n\) to a goal node.
\(f(n)\) is used to judge the merit of a node \(n\) before selecting it from the \(\texttt{OPEN}\) list.
\(g^*(n) \rightarrow\) the actual cost of an optimal path joining start node \(s\) to node \(n\).
@TODO insert diagram of state space showing nodes s, n and goal as well as costs c1..c4 of paths from s to n
Here, \(g^*(n) = \min{c_1, c_2, c_3, c_4}\)
\(h^*(n) \rightarrow\) the actual cost of an optimal path joining node \(n\) to a goal node.
\(f^*(s) \rightarrow\) the actual cost of an optimal path joining start node \(s\) to a goal node.
If node \(n\) lies on an optimal path joining \(s\) to a goal node, then