NeverFlight
commented
4 years ago In my view, if we start from one node, assuming name A, among all its neighbor B1, B2, ... Bn, B1 is the smallest f-value, and we pick that node as our next iteration. So is any possibility that we can never go back to any node among B2 and Bn? If B3 is the smallest f-value node among B1's neighbor, but if we consider B3 as the dead-end at A node step, it will lead to the error A* search.
BTW, in case I might get wrong, I post the algorithm of A* search here, and it didn't mention that we need to put all other nodes as the dead-end.
1. Create an empty map of nodes to pairs of distances (g, h). g is the distance so far, and h
is the estimated distance to the goal using the heuristic. Initialize every node to map to
infinity g.
2. Calculate the heuristic value for the origin h and set the distance for the origin to (0, h).
Let curr be the origin.
3. While curr is not the destination node:
a. “Finalize” curr.
b. Iterate over its neighbors, “relax” each neighbor:
c. For each neighbor that is not finalized, update its distance (if less than the current g
value) to the sum of curr’s distance and the weight of the edge between curr and this
neighbor. Calculate the heuristic value for this neighbor and assign it to h.
d. Set curr to the next min node – the node with the smallest g+h value not yet finalized.
4. Return the g value for the destination node.
The astar method is currently picking the best node by selecting from the nodes adjacent on the current node. The other nodes that were discovered also need to be considered in case a dead end is meet while traversing through the "best" node. https://github.com/NeverFlight/CS435-Project2-Part2/blob/d2214e6197e00763e03a18aacb510f210ff396cb/src/com/cs435/part2/Main.java#L201-L233