2
$\begingroup$

How is the cost of the path to each node $n$ computed in the A* algorithm? Do we need to add the cost of the path to the parent node $p$ to the cost of the path of the child node $n$?

$\endgroup$
3
$\begingroup$

The evaluation function in A* is $f(n) = g(n) + h(n)$, where $g(n)$ is the cost of the path from the starting node to $n$ and $h(n)$ is an estimate of the distance from $n$ to the goal node. To compute $g(n)$, you simply do $g(n) = g(p) + c(p, n)$, where $p$ is the parent node, and $c(p, n)$ is the $c$ost of the edge between $p$ and $n$. So, yes, to compute $g(n)$ you use $g(p)$.

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