Answers.Body: <p>In the A* algorithm, at each iteration, a node is chosen which minimizes a certain function, called the <em>evaluation function</em>, which, in the case of A*, is defined as</p>
  
  <p><span class="math-container">$$f(n)=g(n)+h(n)$$</span></p>
  
  <p>where <span class="math-container">$g(n)$</span> is the length (or cost) of the cheapest path from the start node to the current node <span class="math-container">$n$</span> and <span class="math-container">$h(n)$</span> is the heuristic function that estimates the <em>cost</em> of the cheapest path from current node <span class="math-container">$n$</span> to goal node.</p>
  
  <p>There is potentially more than one path to the goal from a given node <span class="math-container">$n$</span>. However, one of these paths is the cheapest path. An <a href="https://en.wikipedia.org/wiki/Admissible_heuristic" rel="nofollow noreferrer"><strong>admissible heuristic</strong></a> function is a <a href="https://en.wikipedia.org/wiki/Heuristic_(computer_science)" rel="nofollow noreferrer">heuristic</a> function that does <strong>not</strong> overestimate the cost to reach the goal node, that is, it estimates a cost to reach a goal that is smaller or equal to the cheapest path from <span class="math-container">$n$</span>, which is denoted by <span class="math-container">$h^*(n)$</span>. Therefore, an admissible heuristic <span class="math-container">$h$</span> satisfies <span class="math-container">$h(n) \leq h^*(n), \forall n$</span>. Given that the goal is to find the cheapest path from a start to a goal node, intuitively, an admissible heuristic is an <em>optimistic</em> predictive function.</p>
  
  <p>A* is guaranteed to find the optimal solution (or path) if it uses an admissible heuristic. In section 2.4 of the book <a href="https://books.google.ch/books?id=4JwN5DTpcqkC&amp;pg=PA72&amp;source=gbs_toc_r&amp;cad=4#v=onepage&amp;q&amp;f=false" rel="nofollow noreferrer">Principles of Artificial Intelligence</a> (1982), Nils J. Nilsson provides the proof of this fact.</p>
  
  <p>However, not all admissible heuristics give the same information, so not all admissible heuristics are equally efficient. For instance, a heuristic function that is trivially admissible is <span class="math-container">$h(n) = 0, \forall n$</span>. However, in this case, the only actual information that is used to choose the next node to expand is only based on <span class="math-container">$g(n)$</span>, that is, <span class="math-container">$f(n) = g(n)$</span>. <a href="https://ai.stackexchange.com/q/9182/2444">This evaluation function corresponds to the evaluation function of the uniform-cost search algorithm</a>, which is an uninformed-search algorithm (as opposed to A*, which, nonetheless, is considered an informed-search algorithm).</p>
  
  <p>Which admissible heuristic is thus more informed? Consider two versions of A*, each with a different <em>admissible</em> heuristic function</p>
  
  <p><span class="math-container">$$
  f_1(n) = g_1(n) + h_1(n)
  $$</span></p>
  
  <p>and </p>
  
  <p><span class="math-container">$$
  f_2(n) = g_1(n) + h_2(n)
  $$</span></p>
  
  <p>where <span class="math-container">$h_1(n) \leq h^*(n), \forall n$</span> and <span class="math-container">$h_2(n) \leq h^*(n), \forall n$</span>. Then A* with the evaluation function <span class="math-container">$f_1$</span> is more informed than A* with <span class="math-container">$f_2$</span> if, for all non-goal nodes <span class="math-container">$n$</span>, <span class="math-container">$h_1(n) &gt; h_2(n)$</span>. See <a href="https://books.google.ch/books?id=4JwN5DTpcqkC&amp;pg=PA72&amp;source=gbs_toc_r&amp;cad=4#v=onepage&amp;q&amp;f=false" rel="nofollow noreferrer">section 2.4.4. of the cited book</a> where an example that attempts to show this is given. </p>
  
  <p>The admissibility of a heuristic depends on the problem. For example, in the case of the <a href="https://www.aaai.org/Papers/AAAI/2000/AAAI00-212.pdf" rel="nofollow noreferrer">Fifteen Puzzle problem</a>, both Manhattan and the Hamming distances are admissible heuristics. However, in other problems, these distances might not <a href="https://math.stackexchange.com/q/2704941/168764">induce</a> an admissible heuristic.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-15T17:55:52.307Z
Answers.LastActivityDate: 2019-09-20T11:56:46.343Z
Answers.LastEditDate: 2019-09-20T11:56:46.343Z
Answers.UserDisplayName: nbro
Body: <p>I am trying to solve a maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristic functions.</p>
  <p>Currently, I explored the Manhattan and Euclidean distances. Which other heuristic functions are available? How do we compare them? How do we know whether a heuristic function is better than another?</p>
  
Tags: <comparison><search><a-star><admissible-heuristic><heuristic-functions>
Title: How do we determine whether a heuristic function is better than another?
UserDisplayName: m2rik
ThreadText: # How do we determine whether a heuristic function is better than another?
  
  (Asked by: username_0 on 2019-09-15)
  
  I am trying to solve a maze puzzle using the A\* algorithm. I am trying to analyze the algorithm based on different applicable heuristic functions.
  
  Currently, I explored the Manhattan and Euclidean distances. Which other heuristic functions are available? How do we compare them? How do we know whether a heuristic function is better than another?
  
  **Tags:** comparison, search, a-star, admissible-heuristic, heuristic-functions
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-09-15. Score: 3
  
  In the A\* algorithm, at each iteration, a node is chosen which minimizes a certain function, called the *evaluation function*, which, in the case of A\*, is defined as
  
  $$f(n)=g(n)+h(n)$$
  
  where $g(n)$ is the length (or cost) of the cheapest path from the start node to the current node $n$ and $h(n)$ is the heuristic function that estimates the *cost* of the cheapest path from current node $n$ to goal node.
  
  There is potentially more than one path to the goal from a given node $n$. However, one of these paths is the cheapest path. An [**admissible heuristic**](https://en.wikipedia.org/wiki/Admissible_heuristic) function is a [heuristic](https://en.wikipedia.org/wiki/Heuristic_(computer_science)) function that does **not** overestimate the cost to reach the goal node, that is, it estimates a cost to reach a goal that is smaller or equal to the cheapest path from $n$, which is denoted by $h^\*(n)$. Therefore, an admissible heuristic $h$ satisfies $h(n) \leq h^\*(n), \forall n$. Given that the goal is to find the cheapest path from a start to a goal node, intuitively, an admissible heuristic is an *optimistic* predictive function.
  
  A\* is guaranteed to find the optimal solution (or path) if it uses an admissible heuristic. In section 2.4 of the book [Principles of Artificial Intelligence](https://books.google.ch/books?id=4JwN5DTpcqkC&pg=PA72&source=gbs_toc_r&cad=4#v=onepage&q&f=false) (1982), Nils J. Nilsson provides the proof of this fact.
  
  However, not all admissible heuristics give the same information, so not all admissible heuristics are equally efficient. For instance, a heuristic function that is trivially admissible is $h(n) = 0, \forall n$. However, in this case, the only actual information that is used to choose the next node to expand is only based on $g(n)$, that is, $f(n) = g(n)$. [This evaluation function corresponds to the evaluation function of the uniform-cost search algorithm](https://ai.stackexchange.com/q/9182/2444), which is an uninformed-search algorithm (as opposed to A\*, which, nonetheless, is considered an informed-search algorithm).
  
  Which admissible heuristic is thus more informed? Consider two versions of A\*, each with a different *admissible* heuristic function
  
  $$
  f\_1(n) = g\_1(n) + h\_1(n)
  $$
  
  and
  
  $$
  f\_2(n) = g\_1(n) + h\_2(n)
  $$
  
  where $h\_1(n) \leq h^\*(n), \forall n$ and $h\_2(n) \leq h^\*(n), \forall n$. Then A\* with the evaluation function $f\_1$ is more informed than A\* with $f\_2$ if, for all non-goal nodes $n$, $h\_1(n) > h\_2(n)$. See [section 2.4.4. of the cited book](https://books.google.ch/books?id=4JwN5DTpcqkC&pg=PA72&source=gbs_toc_r&cad=4#v=onepage&q&f=false) where an example that attempts to show this is given.
  
  The admissibility of a heuristic depends on the problem. For example, in the case of the [Fifteen Puzzle problem](https://www.aaai.org/Papers/AAAI/2000/AAAI00-212.pdf), both Manhattan and the Hamming distances are admissible heuristics. However, in other problems, these distances might not [induce](https://math.stackexchange.com/q/2704941/168764) an admissible heuristic.
  
  
  ---
  
  