I am reading college notes on state search space. The notes (which are not publicly available) say:

  1. To do state-search space, the strategy involves two parts: defining a heuristic function, and identifying an evaluation function.

  2. The heuristic is a smart search of the available space. The evaluation function may be well-defined (e.g. the solution solves a problem and receives a score) or may itself be the heuristic (e.g. if chess says pick A or B as the next move and picks A, the evaluation function is the heuristic).

  3. Understand the difference between the heuristic search algorithm and the heuristic evaluation function.

I'm trying step 3 (to understand). Can I check, using the A* search as an example, that the:

Heuristic function: estimated cost from the current node to the goal, i.e. it's a heuristic that's calculating the simplest way to get to the goal (in A*; $h(n)$), so the heuristic function is calculating $h(n)$ for a series of options and picking the best one.

Evaluation function: $f(n) = g(n) + h(n)$.


What is the difference between the heuristic function and the evaluation function in A*?

The evaluation function, often denoted as $f$, is the function that you use to choose which node to expand during one iteration of A* (i.e. decide which node to take from the frontier, determine the next possible actions and which next nodes those actions lead to, and add those nodes to the frontier). Typically, you expand the node $n$ such that $f(n)$ is the smallest, i.e. $n^* = \operatorname{argmin}f(n)$.

In the case of informed search algorithms (such as A*), the heuristic function is a component of $f$, which can be written as $f(n) = g(n) + h(n)$, where $h(n)$ is the heuristic function. The heuristic function estimates the cost of the cheapest path from $n$ to the goal. Just for completeness, $g(n)$ is the actual cost from the start node to $n$ (which can be computed exactly during the search). In the case of uninformed search algorithms, you can actually view the evaluation function as just $f(n) = g(n)$, i.e. the heuristic function is always zero.

So, you're right.

For more details, you can take a look at section 3.5 (p. 92) of the book Artificial Intelligence: A Modern Approach (3rd edition), by Norvig and Russell (you can find the pdf online).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.