Hacker News Reader

Comment by walker_tw | Hacker News Reader

Ah hello thanks for looking at the app. The reason that we state that Euclidean does not always find the shortest path is because the way the distance heuristic is calculated. Euclidean will not work on a quad-directional traversal grid such as this (we cant use diagonals) so instead the Manhattan distance is used to override this issue.

View on HN

I don't think this is true. From Wikipedia [1]:

> The heuristic function is problem-specific. If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal.

In this case the euclidean does not overestimate so I would guess there is a bug in the implementation.

[1] https://en.wikipedia.org/wiki/A*_search_algorithm

Edit:

Having taken a look at the source code I believe the problems mostly stem from the `addNeighboursToOpen` function [2]. It sets the distance and parent of unvisited neighbors of the current node. However this may happen multiple times for a node before it is actually visited. Meaning that the distance and parent is updated multiple times and the value at the end is not the optimal one. A simple fix would be to do a if check to see if the node already has a distance assigned.

[2] https://github.com/Walker-TW/Algorithm-Visualizer/blob/maste...

Thanks for the help. Can you expand on what you mean? The function called on line 35 (heuristicNodeCheck) will compare the heuristic to the new total created every time a node is checked or listed as a neighbour. Therefore the heuristic will always be kept relevant. Are you suggesting that when a node is labelled with a heuristic to keep it as its first value?

I suggest you re-read the parent comment. The issue is not with the heuristic value, it is with the distance and predecessor (parent).

Cool app! However shouldn't using the Euclidean heuristic still result in finding the shortest path, as it will not overestimate the distance to the goal when evaluating a node, even if it is not possible to travel diagonally in the grid?

Also - is the behavior shown in the screenshot working as intended, as the shown path includes a detour?

Reply on news.ycombinator.com