# Coefficients in cost function in A-star

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

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.

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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.88986444,"math_prob":0.99826306,"size":1107,"snap":"2023-40-2023-50","text_gpt3_token_len":284,"char_repetition_ratio":0.13145965,"word_repetition_ratio":0.011363637,"special_character_ratio":0.27009937,"punctuation_ratio":0.07305936,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999691,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-04T10:10:56Z\",\"WARC-Record-ID\":\"<urn:uuid:d12d1bd4-2253-47db-8c2a-c8444bb274a9>\",\"Content-Length\":\"170974\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:770731ec-c6dd-43fa-96ee-374547e71262>\",\"WARC-Concurrent-To\":\"<urn:uuid:5b0b32fd-6fe2-473f-a56e-4c81d45d753d>\",\"WARC-IP-Address\":\"104.18.43.226\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/114842/coefficients-in-cost-function-in-a-star\",\"WARC-Payload-Digest\":\"sha1:YMBOACANBDARONUM65UEZW5OWYGCGHYU\",\"WARC-Block-Digest\":\"sha1:VKI5FOS22XO6KLUMCWTTFWRIB2XZCDKK\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100527.35_warc_CC-MAIN-20231204083733-20231204113733-00580.warc.gz\"}"}