How does A* search select the next node, when nodes with the same heauristic value get added?

Question

I have a basic understanding of the concept but a model answer given by a lecturer confused me,

I'm confused over the fact how (2,3)B node is expanded ahead of (2,3)A node which in theory gets added to the queue first(Before node B is added)

This tree is a graphical representation of the shortest path evaluation of a grid. This tree does not mean that (2,3)A node Do not have children actually they refer to the same location in the grid, Can someone clarify what I'm missing? Thanks in advance :)

Answer 1

The answer is that it is up to the priority queue implementation.

Take the usual heap implementation with an array. The elements are ordered like this:

0 1 2 3 4 5 6 7 8 9 10

But below position i the next two are 2i+1 and 2i+2. So the array is a tree structure that looks like this:

[0,
  [1,
    [3, [7, 8]],
    [4, [9, 10]]]],
  [2, [5, 6]]]

Now suppose that 3, 5 have the same priority as each other and so to 6, 7. And those 4 were added in that order. Also suppose that the heap drops the top (left, however you think of it) element first on ties. Then as you extract, we will eventually get 3 and 5 to the bottom and 3 drops first. But as you continue extracting, you eventually get a tie between 6, 7 and now 7 is on the top (left, however you orient your thinking) and so it drops first.

The result is that the priority queue guarantees that things come out in priority order, but do NOT have other guarantees on the order. So things of the same priority can come out in any order.

This is directly related to why Heapsort is not a stable sort.