11–20 of 21 posts
From the title I was expecting a more general purpose algorithm visualizer. I think this is more accurately described as "Graph Traversal Algorithm Visualizer".
https://github.com/hediet/vscode-debug-visualizer/blob/maste...
The site states that the A* algorithm with the Euclidean heuristic does not always find the shortest path. This appears to be true for the implementation [0], but should not be true in general, as it should be guaranteed that A* will provide a shortest path when used with an admissible heuristic such as the Euclidean distance. [0] https://imgur.com/a/UCAFHA4
The site states that the A* algorithm with the Euclidean heuristic does not always find the shortest path. This appears to be true for the implementation [0], but should not be true in general, as it should be guaranteed that A* will provide a shortest path when used with an admissible heuristic such as the Euclidean distance. [0] https://imgur.com/a/UCAFHA4
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.
Also - is the behavior shown in the screenshot working as intended, as the shown path includes a detour?
The site states that the A* algorithm with the Euclidean heuristic does not always find the shortest path. This appears to be true for the implementation [0], but should not be true in general, as it should be guaranteed that A* will provide a shortest path when used with an admissible heuristic such as the Euclidean distance. [0] https://imgur.com/a/UCAFHA4
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.
> 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...
Earlier quoted context omitted.
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.
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_…
This would've been very useful in my college days. A 300-person lecture plus a professor with horrible chalk handwriting who didn't host any TA sections was not conducive to learning.
From the title I was expecting a more general purpose algorithm visualizer. I think this is more accurately described as "Graph Traversal Algorithm Visualizer".
Even the use of “graph traversal algorithm” is not accurate. Dijkstra and A* aren’t for graph traversal. These are pathfinding algorithms.
I still agree that comparing a DFS and an A* is a bit strange, they have different use cases.
Earlier quoted context omitted.
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_…
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?