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:
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);
}
Thanks so much everyone~
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.