2
$\begingroup$

Nodes in the open list in A* will be sorted by their f-cost, but if the f-cost of two nodes are equal, will their h-costs instead be compared? I'm asking because I've seen implementations where the h-costs are compared and where they aren't, so which version is the right one? What is the benefit of doing either?

g-cost: Cost from start to node

h-cost: Heuristic from node to end

f-cost: g-cost + h-cost

Edit: From Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"

"Select the open node n whose value of f is smallest. Resolve ties arbitrarily, but always in favor of any node n ∈ T."

It is stated that "T" is the goal set (I thought there was only one goal node?)

My interpretation is that if the goal node is in the open set, then it should be picked first, meaning resolving ties via h-cost is certainly a correct way because h(end) = 0.

$\endgroup$
1
$\begingroup$

It's not problematic to have more than one goal node in A* if you just want to reach any goal node. You simply keep running the search until you have expanded the first goal node.

Provided that your $h(x)$ function is consistent (or just admissible if your graph is a tree) the way of breaking ties does not affect the optimality of the search. As A* always expands all nodes with $f(x) \lt C^*$ where $C^*$ is the true cost of the optimal solution, and never expands nodes with $f(x) \gt C^*$, the number of nodes that gets expanded will end up being the same (or almost the same, as we will see).

Consider this case: We have two nodes $a$ and $b$, who are both on the open list, and we have that $f(a) = f(b)$ and $h(a) \lt h(b)$. We choose to expand $a$ because of the lower $h$-value and discover that a goal node $g$ is a neighbor to $a$. As $h(x)$ is at least admissible the actual distance between $a$ and $g$ can not be shorter than $h(a)$ and therefore $f(g) \geq f(a)$. There are now two cases:

- If $f(g) \gt f(a)$, then we also have that $f(g) \gt f(b)$ and we therefore need to expand $b$ before we can conclude that we have found the fastest way to $g$.

- If $f(g) = f(a)$, then we also have $f(g) = f(b)$, but this only happens if the distance between $a$ and $g$ is $0$ and in that case $h(a)$ must also be $0$. We now have both $b$ and $g$ on the open list and their $f$-value is the same and so we expand $g$ as it is a goal node. In this case we do not need to expand $b$.

Had we expanded $b$ first, the exact same thing would have happened and we would have had to expand $a$ as well unless $h(b)$ was $0$. In other words, taking the lowest $h$-value first has no influence on the number of nodes expanded unless it is the case that $h(x) = 0$, in which case it does make sense to expand this node first. Note however, that only if the actual distance from $x$ to the goal is also $0$ (it could be more that $h(x)$) do we actually save a node from being expanded. So while A* always expands all nodes with $f(x) \lt C^*$ and never expands nodes with $f(x) \gt C^*$, the nodes with $f(x) = C^*$ could be expanded or not expanded depending on your tie-braking and the structure of the graph.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think you have a typo in the third paragraph where you say "the actual distance between a and g can not be shorter than $f(a)$". I think you mean $h(a)$ instead of $f(a)$. $\endgroup$ – Blckknght Jun 3 '18 at 23:40
  • $\begingroup$ Yes, you are right. Thanks. I've edited it. $\endgroup$ – AstridNeu Jun 4 '18 at 4:36

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.