How to trim the returned nodes of Greedy Best First Search and A* Algorithms?

Question

I am trying to implement GBFS and A* with a grid (2D array). I think before we go any further...do both of the algorithms remember previous locations and if so, does this therefore mean that it will jump to that location if the heuristics are better i.e. would it jump to a node of a sibling's child if the sibling's children has better heuristics than the current node's children? Better explanation would be for example, if I had a 8x8 grid and I was on coordinates 7,7, and I check the cells next to it but in the PriorityQueue, we have a coordinate 3,5 which has better heuristics than the cells next to 7,7...would we jump to 3,5?

if the answer is yes, then my problem is how would I create the correct path from the returned nodes that have been removed from the PriorityQueue given that we can jump from one location to another? I.e. how do we trim down the nodes to create the actual path?

Answer 1

Do both of the algorithms remember previous locations and if so, does this therefore mean that it will jump to that location if the heuristics are better i.e. would it jump to a node of a sibling's child if the sibling's children has better heuristics than the current node's children?

Yes to both.

When you insert nodes into the priority queue you should keep track of their "parent" node, the node that preceded them. For example, if you're at 7,7 and then add 8,7 to the queue you should set 8,7's parent to 7,7.

This way you can backtrack from any node back to the start node by following the chain of parents.

If I had a 8x8 grid and I was on coordinates 7,7, and I check the cells next to it but in the PriorityQueue, we have a coordinate 3,5 which has better heuristics than the cells next to 7,7...would we jump to 3,5?

Yes. Considering 3,5 after 7,7 doesn't mean the player is "jumping" to 3,5. It means he's now considering an alternate path since the path that goes through 3,5 seems more promising than the one through 7,7, at least momentarily.

How would I create the correct path from the returned nodes that have been removed from the PriorityQueue?

Eventually you will reach the goal node. Let's say the goal node is 6,6 and you got there from 6,5. How do you reconstruct the path that got you there?

• Look at 6,5's parent.
• Look at 6,5's parent's parent.
• Look at 6,5's parent's parent's parent.
• etc.

This will eventually get you back to the start node, and that is your path (in reverse).

Take this example image based on your previous question. Each arrow represents one of the parent pointers you'd have. I changed colors each time the search "jumped" from one path to another. Notice how you can start from any of the nodes visited during the search and follow the arrows back to the start node.