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$
0

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .