Answers.Body: <p>What you are doing when calculating <span class="math-container">$d'(x,y)$</span>:</p>
  
  <ol>
  <li><span class="math-container">$d(x,y)$</span>: calculating the original edge distance from <span class="math-container">$x$</span> to <span class="math-container">$y$</span></li>
  <li><span class="math-container">$h(y)$</span>: plus the heuristic from <span class="math-container">$y$</span> to the goal</li>
  <li><span class="math-container">$h(x)$</span>: minus the heuristic from <span class="math-container">$x$</span> to the goal</li>
  </ol>
  
  <p>So, using this recalculation of the original edge-values (<span class="math-container">$1.$</span>) in Dijkstra's algorithm you are inherently accounting for the heuristic component of A* by incorporating it (<span class="math-container">$2.$</span>) into the value of the edge traversed, and discarding (<span class="math-container">$3.$</span>) the accumulated previous heuristic values of previous nodes in the path.</p>
  
  <p>The additional condition <span class="math-container">$h(x) ≤ d(x, y) + h(y)$</span> ensures the new edge-values are strictly positive.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-24T13:05:11.017Z
Answers.LastActivityDate: 2020-04-24T14:06:15.103Z
Answers.LastEditDate: 2020-04-24T14:06:15.103Z
Answers.UserDisplayName: brazofuerte
Body: <p>According to <a href="https://en.wikipedia.org/wiki/A*_search_algorithm#Description" rel="nofollow noreferrer">this Wikipedia article</a></p>
  <blockquote>
  <p>If the heuristic <span class="math-container">$h$</span> satisfies the additional condition <span class="math-container">$h(x) \leq d(x, y) + h(y)$</span> for every edge <span class="math-container">$(x, y)$</span> of the graph (where <span class="math-container">$d$</span> denotes the length of that edge), then <span class="math-container">$h$</span> is called monotone, or consistent. In such a case, <span class="math-container">$A^*$</span> can be implemented more efficiently — roughly speaking, no node needs to be processed more than once (see closed set below) — and <span class="math-container">$A^*$</span> is equivalent to running Dijkstra's algorithm with the reduced cost <span class="math-container">$d'(x, y) = d(x, y) + h(y) − h(x).$</span></p>
  </blockquote>
  <p>Can someone intuitively explain why the reduced cost is of this form ?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-17T11:55:10.457Z
Comments.Text: Djikstra is actually a special case of A*.
  Think of Djikstra intuitively as A* with the heuristic cost being always zero.
Comments.UserDisplayName: Valentin Metz
Tags: <comparison><search><heuristics><a-star><dijkstras-algorithm>
Title: A* is similar to Dijkstra with reduced cost
UserDisplayName: Shrey Shrivastava
ThreadText: # A* is similar to Dijkstra with reduced cost
  
  (Asked by: username_0 on 2019-05-24)
  
  According to [this Wikipedia article](https://en.wikipedia.org/wiki/A*_search_algorithm#Description)
  
  > If the heuristic $h$ satisfies the additional condition $h(x) \leq d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge), then $h$ is called monotone, or consistent. In such a case, $A^\*$ can be implemented more efficiently — roughly speaking, no node needs to be processed more than once (see closed set below) — and $A^\*$ is equivalent to running Dijkstra's algorithm with the reduced cost $d'(x, y) = d(x, y) + h(y) − h(x).$
  
  Can someone intuitively explain why the reduced cost is of this form ?
  
  **Tags:** comparison, search, heuristics, a-star, dijkstras-algorithm
  
  > **Comments:**
  > **username_1**: Djikstra is actually a special case of A*. Think of Djikstra intuitively as A* with the heuristic cost being always zero.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-04-24. Score: 1
  
  What you are doing when calculating $d'(x,y)$:
  
  1. $d(x,y)$: calculating the original edge distance from $x$ to $y$
  2. $h(y)$: plus the heuristic from $y$ to the goal
  3. $h(x)$: minus the heuristic from $x$ to the goal
  
  So, using this recalculation of the original edge-values ($1.$) in Dijkstra's algorithm you are inherently accounting for the heuristic component of A\* by incorporating it ($2.$) into the value of the edge traversed, and discarding ($3.$) the accumulated previous heuristic values of previous nodes in the path.
  
  The additional condition $h(x) ≤ d(x, y) + h(y)$ ensures the new edge-values are strictly positive.
  
  
  ---
  
  