A* search at cost $g(n)=0$

Question

Wouldn't the answer be Greedy Best First Search since the path cost $= 0$?

Which search strategy is simulated by the $A*$ search algorithm if we take cost function$ g(n) = 0$ if one assumes no further restrictions on the heuristic function $h$?

1. Depth First Search
2. Greedy Best First Search
3. Uniform Cost Search
4. None of the above.

Edit: I believe it is Greedy Best First Search because the GBFS always looks for the lowest next heuristic, while the A* search looks for the lowest sum of the pathcost + heuristic. If pathcost is 0, then there would be no difference between the two?

Answer 1

Greedy Best First Search (GBFS) is the correct answer. To demonstrate this, we need to address the two properties that differ between A* and GBFS:

1. the order in which nodes exit from the OPEN LIST;
2. the fact that A* has a RE-OPEN subroutine, whereas GBFS does not.

Let $h(n)$ be the heuristic value of the search node $n$, and let $g(n)$ be the distance from the initial search node to $n$. Assuming similar tie-breaking for both algorithms, GBFS selects nodes from the OPEN LIST based on their heuristic value $h(n)$. A* selects nodes based on $f(n) = g(n) + h(n)$. Given the assumption that $g(n) = 0$ for every $n$, we have that $f(n) = h(n)$. Thus, the order of selecting nodes from the OPEN LIST is the same.

To demonstrate that the OPEN LIST and CLOSED LIST are similar for both GBFS and A* after each step of the algorithms, we need to show that the RE-OPEN subroutine is never activated for problems with a cost function of $g(n) = 0$.

The RE-OPEN subroutine is activated if the following conditions hold for the currently inspected node $n$: the search has already encountered and expanded the node $n$ ($n$ is in the CLOSED LIST), and the current path to $n$ is shorter than the path we previously expanded $n$ with. In this case, A* updates the path to $n$ and puts it back in the OPEN LIST. However, this is impossible in the case where $g(n) = 0$ for every $n$, as all paths to all nodes cost zero. Thus, the RE-OPEN subroutine is never activated.

Hence, A* behaves like GBFS for a zero-cost problem when using the same heuristic function and tie-breaking strategy.