0
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.