title: Studying some variants of the A* algorithm
body: <p>I recently started learning about the A* algorithm and its variants and came across this paper [1]. It basically has three variants of the algorithm with the heuristic value changed in each one of them.</p>
  <p>For the A*(1) it has <code>f(i) = g(i) + h(i)</code>, where <code>g(i)</code> denotes the path-cost function from the start point to the current position <code>i</code>, heuristic function <code>h(i)</code> is  the  Euclidean distance from the current point to the target point.</p>
  <p>And for the A*(2) it has <code>f(i) = g(i) + h(i) + h(j)</code>, where <code>j</code> the parent node of current point, <code>h(j)</code> is the Euclidean distance from the partent node of current point to target point.</p>
  <p>The results show that A*(2) is generally faster than A*(1) when tried on randomly generated mazes. I am not able to explain why is this the case. I tried to compare the two heuristics and was able to conclude the contrary.</p>
  <p>My logic says that if we travel from a point that is farther from the target to a nearer point, the <code>f(i)</code> value would be higher than when we travel from a point closer to the target to one that is far because we are considering the Euclidean distance of the parent node. Basically, to reach a specific node the path that is leading away from the target will have a lower <code>f(i)</code>.</p>
  <p>And since the <code>f(i)</code> value is lower, it would go up on the priority queue. This is against our goal, as a path that is going away from the target is prioritized over the path that is getting closer.</p>
  <p>What is wrong with this logic and why does it not align with the results cited in the paper?</p>
  <p>[1] - <a href="https://www.researchgate.net/publication/238009053_A_comparative_study_of_A-star_algorithms_for_search_and_rescue_in_perfect_maze" rel="nofollow noreferrer">https://www.researchgate.net/publication/238009053_A_comparative_study_of_A-star_algorithms_for_search_and_rescue_in_perfect_maze</a></p>