Answers.Body: <blockquote>
  <p>What is the difference between the heuristic function and the evaluation function in A*?</p>
  </blockquote>
  <p>The <strong>evaluation function</strong>, often denoted as <span class="math-container">$f$</span>, 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 <span class="math-container">$n$</span> such that <span class="math-container">$f(n)$</span> is the smallest, i.e. <span class="math-container">$n^* = \operatorname{argmin}f(n)$</span>.</p>
  <p>In the case of <em>informed</em> search algorithms (such as A*), the <strong>heuristic function</strong> is a component of <span class="math-container">$f$</span>, which can be written as <span class="math-container">$f(n) = g(n) + h(n)$</span>, where <span class="math-container">$h(n)$</span> is the heuristic function. The heuristic function estimates the cost of the cheapest path from <span class="math-container">$n$</span> to the goal. Just for completeness, <span class="math-container">$g(n)$</span> is the actual cost from the start node to <span class="math-container">$n$</span> (which can be computed exactly during the search). In the case of uninformed search algorithms, you can actually view the evaluation function as just <span class="math-container">$f(n) = g(n)$</span>, i.e. the heuristic function is always zero.</p>
  <p>So, you're right.</p>
  <p>For more details, you can take a look at section 3.5 (p. 92) of the book <a href="http://aima.cs.berkeley.edu/" rel="nofollow noreferrer">Artificial Intelligence: A Modern Approach</a> (3rd edition), by Norvig and Russell (you can find the pdf online).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-13T14:03:56.937Z
Answers.LastActivityDate: 2020-12-13T14:09:05.990Z
Answers.LastEditDate: 2020-12-13T14:09:05.990Z
Answers.UserDisplayName: nbro
Body: <p>I am reading college notes on state search space. The notes (which are not publicly available) say:</p>
  <blockquote>
  <ol>
  <li><p>To do state-search space, the strategy involves two parts: defining a heuristic function, and identifying an evaluation function.</p>
  </li>
  <li><p>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).</p>
  </li>
  <li><p>Understand the difference between the heuristic search algorithm and the heuristic evaluation function.</p>
  </li>
  </ol>
  </blockquote>
  <p>I'm trying step 3 (to understand). Can I check, using the A* search as an example, that the:</p>
  <p><strong>Heuristic function:</strong> 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*; <span class="math-container">$h(n)$</span>), so the heuristic function is calculating <span class="math-container">$h(n)$</span> for a series of options and picking the best one.</p>
  <p><strong>Evaluation function:</strong> <span class="math-container">$f(n) = g(n) + h(n)$</span>.</p>
  
Tags: <comparison><search><a-star><heuristic-functions><evaluation-functions>
Title: What is the difference between the heuristic function and the evaluation function in A*?
UserDisplayName: Slowat_Kela
ThreadText: # What is the difference between the heuristic function and the evaluation function in A*?
  
  (Asked by: username_0 on 2020-12-13)
  
  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)$.
  
  **Tags:** comparison, search, a-star, heuristic-functions, evaluation-functions
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-12-13. Score: 2 | Accepted answer
  
  > 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](http://aima.cs.berkeley.edu/) (3rd edition), by Norvig and Russell (you can find the pdf online).
  
  
  ---
  
  