Answers.Body: <p>Consistency is a property of heuristics. You can think of consistency as the common sense idea that our guess at the time to go from <span class="math-container">$A \rightarrow B \rightarrow C$</span> cannot be more than the time to go from <span class="math-container">$A \rightarrow B$</span>, plus our guess of the time to go from <span class="math-container">$B \rightarrow C$</span>.</p>
  
  <p>Supposing we remove a given edge <span class="math-container">$c(n,m)$</span> from our graph, but that our heuristic function gives the same value for <span class="math-container">$h(n)$</span> as before. Can the function be inconsistent? Let's try a proof sketch:</p>
  
  <ol>
  <li>Since the function was consistent before we removed this edge, it must already be the case that <span class="math-container">$h(n) &lt; c(n, m') + h(m')$</span> for every other node <span class="math-container">$m'$</span> adjacent to <span class="math-container">$n$</span>. </li>
  <li>Removing the edge <span class="math-container">$c(n,m)$</span> doesn't change these relationships, because the other edges still have the same costs as before, and the heuristic function still gives the same value for every node.</li>
  <li>The same argument may be applied to node <span class="math-container">$m$</span>.</li>
  <li>Since none of these relationships have changed, <span class="math-container">$h$</span> is still consistent.</li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-26T01:35:07.647Z
Answers.Text: if c(n,m) edge is removed how would you know that h(n) < c(n,m) + h(m) ? since we don't know how long it takes to go from n to m ? I understand intuitively why h is still consistent but how would the inequality for consistency apply for node n and m ? does c(n,m) need to be a direct edge ?
Answers.UserDisplayName: calveeen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-26T05:24:51.170Z
Answers.Text: @calveeen It ends up that if the heuristic is locally consistent (between all neighbors of states) then it is also globally consistent (where n and m are not directly connected and c(n, m) represents the cost of the shortest path between them). This can be proven by induction. Removing the edge between n and m can only make c(n, m) larger, in which case the inequality still holds.
Answers.UserDisplayName: Nathan S.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-25T23:28:41.570Z
Answers.LastActivityDate: 2020-03-28T03:46:11.157Z
Answers.LastEditDate: 2020-03-28T03:46:11.157Z
Answers.UserDisplayName: John Doucette
Body: <p>For the A* algorithm, a consistent heuristic is defined as follows:
  if, for every node <span class="math-container">$n$</span> and every successor <span class="math-container">$m$</span> of <span class="math-container">$n$</span> generated by any action <span class="math-container">$a$</span>, <span class="math-container">$h(n) \leq c(n,m) + h(m)$</span>. </p>
  
  <p>Suppose the edge <span class="math-container">$c(n,m)$</span> is removed, how do we define consistency for nodes <span class="math-container">$n, n'$</span> ? Since the <span class="math-container">$n'$</span> is not generated from <span class="math-container">$n$</span>.</p>
  
Tags: <search><a-star><consistent-heuristic>
Title: What does a consistent heuristic become if an edge is removed in A*?
UserDisplayName: calveeen
ThreadText: # What does a consistent heuristic become if an edge is removed in A*?
  
  (Asked by: username_0 on 2020-03-25)
  
  For the A\* algorithm, a consistent heuristic is defined as follows:
  if, for every node $n$ and every successor $m$ of $n$ generated by any action $a$, $h(n) \leq c(n,m) + h(m)$.
  
  Suppose the edge $c(n,m)$ is removed, how do we define consistency for nodes $n, n'$ ? Since the $n'$ is not generated from $n$.
  
  **Tags:** search, a-star, consistent-heuristic
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-03-25. Score: 2 | Accepted answer
  
  Consistency is a property of heuristics. You can think of consistency as the common sense idea that our guess at the time to go from $A \rightarrow B \rightarrow C$ cannot be more than the time to go from $A \rightarrow B$, plus our guess of the time to go from $B \rightarrow C$.
  
  Supposing we remove a given edge $c(n,m)$ from our graph, but that our heuristic function gives the same value for $h(n)$ as before. Can the function be inconsistent? Let's try a proof sketch:
  
  1. Since the function was consistent before we removed this edge, it must already be the case that $h(n) < c(n, m') + h(m')$ for every other node $m'$ adjacent to $n$.
  2. Removing the edge $c(n,m)$ doesn't change these relationships, because the other edges still have the same costs as before, and the heuristic function still gives the same value for every node.
  3. The same argument may be applied to node $m$.
  4. Since none of these relationships have changed, $h$ is still consistent.
  
  > **Comments:**
  > **username_0**: if c(n,m) edge is removed how would you know that h(n) < c(n,m) + h(m) ? since we don't know how long it takes to go from n to m ? I understand intuitively why h is still consistent but how would the inequality for consistency apply for node n and m ? does c(n,m) need to be a direct edge ?  
  > **username_2**: @username_0 It ends up that if the heuristic is locally consistent (between all neighbors of states) then it is also globally consistent (where n and m are not directly connected and c(n, m) represents the cost of the shortest path between them). This can be proven by induction. Removing the edge between n and m can only make c(n, m) larger, in which case the inequality still holds.  
  
  ---
  
  