Does admissibility even matter in A* search if the heuristic function overestimates in a consistent manner?

Question

What if the heuristic value of a node is, let’s say, actual cost of getting to goal x 10^5? The node with the least f cost is still popped from top of the priority queue.

for example: f(n) = g(n) + h(n), where h(n) = h1(n) x 10^5, where h1(n) = h1′(n)

By definition, h here is the overestimate of the actual cost of getting to goal.

The reason I asked is because I could not really see the difference in performance of the algorithm with or without that constant factor. If then why should it matter that if h is admissible or not?

Answer 1

Yes:

1. In general: Admissibility is a sufficient condition for the optimality of A*, not a necessary one. Of course you might find an inadmissible heuristic exists that also returns an optimal result; it's just that A* doesn't provide any guarantees at that point.

2. In particular: "In a consistent manner" is vague, but if you consider "scaling" to fit this description, then note that your scaling heuristic can fail if the costs are not additive. Note that A* does not require the evaluation function to be f = g + h. While unintuitive at first glance, it is entirely possible and realistic for a problem to have other evaluation functions where it doesn't even make sense to add path costs (e.g. your costs might be probabilities).

Also note that "consistency" has an entirely different meaning than the one you are using, so be careful when using that term. Under the usual definition, it is impossible for a consistent heuristic to be inadmissible.