Coefficients in cost function in A-star

Question

I'd like to expand on this question :

https://stackoverflow.com/questions/52420788/why-does-the-a-star-algorithm-need-gn

Dijkstra's algorithm uses cost function $f(n) = g(n)$ whereas A* uses cost function $f(n) = g(n) + h(n)$, with $g(n)$ being the cost of the path from the start node to node $n$, and $h(n)$ is a heuristic function that estimates the cost of the cheapest path from node $n$ to the goal.

It is clear from the linked question's answer that A* needs its $g(n)$ function in the cost function. My question however is the following. Can one use the cost function :

$f(n) = \alpha g(n) + (1-\alpha)h(n)$

for some alpha $0<\alpha<1$ ?

I ask because in some cases I observed it can be much faster to prioritize (through a coefficient) estimated cost over already traversed cost. I am not sure however if this still results in an optimal path?

EDIT : multiplying the heuristic $h(n)$ by some alpha $0<\alpha<1$ is allowed, since this operation still underestimates if $h(n)$ already did (which is necessary to obtain the resulting optimal path). I am more concerned about the multiplying of $g(n)$.

Answer 1

For A* to get the optimal path it requires that $f(n) \leq g(goal)$. In other words that the heuristic underestimates the cost from the node to the goal.

Multiplying a valid hueristic with $0 \lt\alpha\lt 1$ will not violate this requirement.

Multiplying $g(n)$ is not allowed because you can end up with $f(goal) = \alpha g(goal) < f(n)$ which would violate the requirement for getting the optimal path.

Answer 2

This question has been answered here :

https://stackoverflow.com/questions/57974474/coefficients-in-cost-function-in-a-star/57978082#57978082

As user Harold states :

The global scale factor of f, assuming it is a positive scale, does not matter, because f is only used in a relative sense. Numbers scaled by some positive scale stay in the same order.

Therefore, f(n) = αg(n) + (1-α)h(n) may be rewritten as f'(n) = f(n)/α = g(n) + ((1-α)/α)h(n), which is not equal but equivalent. So while you are interested in scaling g, effectively that is equivalent to scaling h anyway, after factoring out the global scale.

The effect is scaling the heuristic by some amount, which is OK only as long as (1-α)/α ≤ 1 (so: α ≥ 0.5), and otherwise leads to the same trouble as usual with an inadmissible heuristic.