Answers.Body: <p><span class="math-container">$c(n, a, G) = h^*(n)$</span> is true because <span class="math-container">$h^*$</span> is the optimal heuristic, i.e. it gives you the minimal/optimal cost from <span class="math-container">$n$</span> to the goal <span class="math-container">$G$</span>, which, in that base case, is exactly <span class="math-container">$c(n, a, G)$</span>, i.e. the edge distance from <span class="math-container">$n$</span> to <span class="math-container">$G$</span>.</p>
  <p>Now, I understand the confusion arises from the parameter <span class="math-container">$a$</span>, the action.</p>
  <p>Here, <span class="math-container">$a$</span> is arbitrary, but, in this case, there's only one action that should lead to <span class="math-container">$G$</span>, which I suppose is a reasonable assumption, otherwise you would have multiple arrows from <span class="math-container">$n$</span> to <span class="math-container">$G$</span> (which are neighbours), which I've never seen.</p>
  <p>I don't even know why they use this parameter <span class="math-container">$a$</span>. I think you can safely ignore it, unless you want to consider cases where there are more than one edge between two neighbours <span class="math-container">$n$</span> and <span class="math-container">$n'$</span>, which is useless because you can always consider the cheapest edge.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-24T16:38:55.750Z
Answers.LastActivityDate: 2023-12-24T16:44:26.493Z
Answers.LastEditDate: 2023-12-24T16:44:26.493Z
Answers.UserDisplayName: nbro
Body: <p>I found a <a href="https://www.comp.nus.edu.sg/%7Ekanmy/courses/3243_2007/tutorials/solutions/cs3243-sol03.pdf" rel="nofollow noreferrer">proof</a> that if a heuristic <span class="math-container">$h$</span> is consistent, then it is admissible, but I'm confused by one of the steps in the proof.</p>
  <p>The proof is by induction on <span class="math-container">$k$</span>, the number of actions from a node <span class="math-container">$n$</span> to the goal node <span class="math-container">$G$</span>.</p>
  <p><strong>Base step</strong>: <span class="math-container">$k = 1$</span>, i.e., node <span class="math-container">$n$</span> is one step from <span class="math-container">$G$</span>. Since the heuristic function <span class="math-container">$h$</span> is consistent,</p>
  <p><span class="math-container">$$h(n) \leq c(n, a, G) + h(G)$$</span></p>
  <p>Since <span class="math-container">$h(G) = 0$</span>,</p>
  <p><span class="math-container">$$h(n) \leq c(n, a, G) = h^{\ast}(n)$$</span></p>
  <p>Therefore, <span class="math-container">$h$</span> is admissible.</p>
  <p><strong>Induction step</strong>: Assume: If <span class="math-container">$h(n′)$</span> is consistent, then <span class="math-container">$h(n′)$</span> is admissible, for all nodes <span class="math-container">$n′$</span> that are <span class="math-container">$k$</span> steps from <span class="math-container">$G$</span>.</p>
  <p><span class="math-container">$$h(n) \leq c(n, a, n') + h(n')$$</span></p>
  <p>Since <span class="math-container">$n′$</span> is <span class="math-container">$k$</span> steps from <span class="math-container">$G$</span> and <span class="math-container">$h$</span> is admissible for node <span class="math-container">$n′$</span> that is <span class="math-container">$k$</span> steps from <span class="math-container">$G$</span>,</p>
  <p><span class="math-container">$$h(n') \leq h^{\ast}(n')$$</span>
  <span class="math-container">$$\implies c(n,a,n') + h(n') \leq c(n, a, n') + h^{\ast}(n')$$</span>
  <span class="math-container">$$\implies h(n) \leq c(n, a, n') + h^{\ast}(n') = h^{\ast}(n)$$</span></p>
  <p>hence, <span class="math-container">$h$</span> us admissible for node n.</p>
  <p>I'm specifically confused about these lines:</p>
  <p><span class="math-container">$$h(n) \leq c(n, a, G) = h^{\ast}(n)$$</span></p>
  <p>and</p>
  <p><span class="math-container">$$h(n) \leq c(n, a, n') + h^{\ast}(n') = h^{\ast}(n)$$</span></p>
  <p>How do we know that <span class="math-container">$c(n,a,G) = h^{\ast}(n)$</span>? Wouldn't it depend on the action <span class="math-container">$a$</span> chosen?</p>
  <p>Also, how do we know: <span class="math-container">$c(n, a, n') + h^{\ast}(n') = h^{\ast}(n)$</span>?</p>
  
Tags: <search><heuristics><a-star><admissible-heuristic><consistent-heuristic>
Title: How do we know that $c(n,a,G) = h^{\ast}(n)$, in the proof that if a heuristic is consistent then it is admissible?
UserDisplayName: Hugh Mann
ThreadText: # How do we know that $c(n,a,G) = h^{\ast}(n)$, in the proof that if a heuristic is consistent then it is admissible?
  
  (Asked by: username_0 on 2023-12-23)
  
  I found a [proof](https://www.comp.nus.edu.sg/%7Ekanmy/courses/3243_2007/tutorials/solutions/cs3243-sol03.pdf) that if a heuristic $h$ is consistent, then it is admissible, but I'm confused by one of the steps in the proof.
  
  The proof is by induction on $k$, the number of actions from a node $n$ to the goal node $G$.
  
  **Base step**: $k = 1$, i.e., node $n$ is one step from $G$. Since the heuristic function $h$ is consistent,
  
  $$h(n) \leq c(n, a, G) + h(G)$$
  
  Since $h(G) = 0$,
  
  $$h(n) \leq c(n, a, G) = h^{\ast}(n)$$
  
  Therefore, $h$ is admissible.
  
  **Induction step**: Assume: If $h(n′)$ is consistent, then $h(n′)$ is admissible, for all nodes $n′$ that are $k$ steps from $G$.
  
  $$h(n) \leq c(n, a, n') + h(n')$$
  
  Since $n′$ is $k$ steps from $G$ and $h$ is admissible for node $n′$ that is $k$ steps from $G$,
  
  $$h(n') \leq h^{\ast}(n')$$
  $$\implies c(n,a,n') + h(n') \leq c(n, a, n') + h^{\ast}(n')$$
  $$\implies h(n) \leq c(n, a, n') + h^{\ast}(n') = h^{\ast}(n)$$
  
  hence, $h$ us admissible for node n.
  
  I'm specifically confused about these lines:
  
  $$h(n) \leq c(n, a, G) = h^{\ast}(n)$$
  
  and
  
  $$h(n) \leq c(n, a, n') + h^{\ast}(n') = h^{\ast}(n)$$
  
  How do we know that $c(n,a,G) = h^{\ast}(n)$? Wouldn't it depend on the action $a$ chosen?
  
  Also, how do we know: $c(n, a, n') + h^{\ast}(n') = h^{\ast}(n)$?
  
  **Tags:** search, heuristics, a-star, admissible-heuristic, consistent-heuristic
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-12-24. Score: 1
  
  $c(n, a, G) = h^\*(n)$ is true because $h^\*$ is the optimal heuristic, i.e. it gives you the minimal/optimal cost from $n$ to the goal $G$, which, in that base case, is exactly $c(n, a, G)$, i.e. the edge distance from $n$ to $G$.
  
  Now, I understand the confusion arises from the parameter $a$, the action.
  
  Here, $a$ is arbitrary, but, in this case, there's only one action that should lead to $G$, which I suppose is a reasonable assumption, otherwise you would have multiple arrows from $n$ to $G$ (which are neighbours), which I've never seen.
  
  I don't even know why they use this parameter $a$. I think you can safely ignore it, unless you want to consider cases where there are more than one edge between two neighbours $n$ and $n'$, which is useless because you can always consider the cheapest edge.
  
  
  ---
  
  