A star algorithm: using Heuristic value to act as Tie-breaker where nodes have identical F-values

Question

Background: I am currently working on an 8-puzzle implementation of the original A Star algorithm and comparing this with a slightly modified algorithm which intends to improve node expansion (using additional information, ofcourse A Star in an equally informed unidirectional search has been proven optimal). The Open List of nodes are currently ordered by their F values (G-Cost+ H-Cost).

So in implementing this in Java I have set up a comparator which orders the List by their F-Values in ascending order.

       @Override
    public int compare(PNode o1, PNode o2) {
        return Integer.compare(o1.costF, o2.costF);
    }

Question: My question is whether:

1. Is it permitted under A-star to implement a further Tie-breaker in A-Star using the Heuristic cost (H-Value) to break any deadlock with the F-Value among many nodes (where nodes exist with the same F-value in the Open List they will be ordered by the Heuristic value (H-Cost) in ascending order instead). The reason I am confused about this as the actual A star algorithm pseudocode only sorts the Open List by the F value.

Extending the same code above, the implementation will be:

        @Override
    public int compare(PNode o1, PNode o2) {
        if (o1.costF == o2.costF) {
            return Integer.compare(o1.costH, o2.costH);
        }
        return Integer.compare(o1.costF, o2.costF);
    }

2. If this is permitted, are there any reasons why I should be wary of doing this? Logically I appreciate that ordering the Open List will be more costly. But from my experiments the difference do not seem significant enough to prevent me from using this.

Thanks so much everyone~

Answer 1

Yes it is allowed, pretty much for the reasons stated in mcdowella's answer.

However, I'd like to add that it is often actually a very good idea, and much more beneficial than implied in that answer. This kind of tie-breaker can result in much more significant gains in performance than only finding the goal slightly earlier. See, for example, this page, which visualizes how A* still explores a rather massive area without the tie-breaker, and only a very narrow band along the optimal path with the tie-breaker.

Intuitively, you can understand that it is so effective by thinking of the different levels of "reliability" of G costs versus H costs. G costs are very reliable, they are ground truth, they are precisely the cost you have really already had to pay to reach a node. H costs are much less reliable, they are heuristics, they can be wildly wrong. By implementing the tie-breaker you propose, you are essentially saying "whenever two nodes have the same value for F = G + H, I prefer those with greater G and smaller H over those with smaller G and greater H". This is wise because, when the more reliable G component of F dominates the less reliable H component, F itself will also be more reliable.

Another major advantage is, as described on the page I linked to, that this tie-breaker can avoid exploring large portions of lots of different paths that are all equal and all optimal.