What node to expand using A-star if the open list contains more than one node with the least cost value?

Question

Using the A-star algorithm to perform a search, if you have two (or more) nodes in the open list with the same value, which happens to be the least cost value, what node should you choose?

I know you should choose the one with the least heuristic value, but what if this cost is also the same?

For example:

I have two nodes expanded from the root. f(n1) = f(n2) and h(n1) = h(n2). Which node should I expand, n1 or n2? Should I expand randomly or use the first one added to the open list?

Answer 1

• A common strategy is to handle the tied nodes in a LIFO manner. This gives the algorithm a bit more depth-first character. In general this does not have to be most efficient solution.

• You can also use chance to break the ties.

• Or you choose the pragmatic strategy of picking the first node your algorithm produces in some way.