Hi all,
Been trying to access the “I’m ready for an extra challenge…” link above, to do an A* review. However, even though I am logged in, I keep getting blocked with a message saying “Sorry, you don’t have access to that topic!”
Has anybody else had this experience, and know how to fix it? Thanks!
How does heap pop works in A*??
When we select one vertex and starts moving in that direction after popping it, its brother sibling still remains in our heap while we continue adding other vertex as we proceed?
What if the sibling vertex that we didn’t choose gets popped of later?
I don’t understand this bit
The implementation on Codecademy might be flawed. I just came to realize this, about 8 months after doing the exercise. Growth
The total distance is calculated wrongly. This happens right at the end of the code: heappush(vertices_to_explore, (new_distance, neighbor))
The above is wrong, since the result from the heuristic calculation is included in new_distance.
In real life, we are not moving the distance between locations AND the distances between coordinates. We are only moving the distance between locations. Therefore the code should be replaced with:
I have tested this and it does not break the algo. The distance traveled is greatly reduced and the traveled path remains the same. The heuristic naturally remain in the calculation happening before, since it is only after comparing the different directions that we apply the distance in the correct direction.
This is of course based on the fact that the distance is the edge weight only.
What you say makes sense , but when I run:
a_star(manhattan_graph, thirty_sixth_and_sixth, grand_central_station)
with your fix, it tells me:
Found a path in 40 steps:…
When I run it with the original code, I get:
Found a path in 35 steps:…
There might be an issue with your suggestion in that the pathfinding no longer is an A* algorithm. I tested it out with a_star(manhattan_graph, thirty_sixth_and_sixth, grand_central_station).
8 - 37th Street and 6th Avenue
10 - 35th Street and 6th Avenue
10 - 36th Street and 5th Avenue
12 - 36th Street and 7th Avenue
The distance includes the heuristic distance and so 37th Street and 6th Avenue would be heappopped next which would follow an A* algorithm search pattern.
I couldn’t confirm it but your suggestion might make the code Dijkstra-esque hence why it takes 38 steps compared to CA’s which takes 35 steps.
Although you’re right in noting that paths_and_distances[target][0] == 40 which is not the actual distance of the shortest path because the value has been combined with heuristic distances along the way. It should be 12.
) below!
) to up-vote the contribution!