Open Nodes More Than Twice during A* Search?

Question

This space graph fulfilled the monotone condition of :

h(v) ≤ h(u) + c(v, u) and  h(t) = 0

But during A* searching in a space graph, I have one a node (y) which is opened twice. Is the graph non - monotone then ?

Also in case of a graph has admissible heuristic function h but not monotone, is it possible if nodes is opened more than twice during a run of A* ?

Answer 1

Your graph is monotone. Notice that the algorithm does not state that a vertex does not come up twice in the algorithm, just that you do not need to reconsider vertices added to closedSet.

I get five steps, following the pseudocode described for monotone graphs.

1. current = s, openSet = {}, closedSet = {s} neighbors are x and y, neither in closedSet after considering both have cameFrom = [-ss--], gScore = [0,2,7,infty,infty], fScore = [3,4,8,infty,infty].
2. current = x, openSet = {y}, closedSet = {s,x} neighbors are z and t, neither in closedSet after considering both have cameFrom = [-,s,s,x,x], gScore = [0,2,7,5,12], fScore = [3,4,8,6,12].
3. current = z, openSet = {y,t}, closedSet = {s,x,z} neighbors are y and t, neither in closedSet after considering both we have cameFrom = [-,s,z,x,z], gScore = [0,2,6,5,11], fScore = [3,4,7,6,11].
4. current = y, openSet = {t}, closedSet = {s,x,y,z} only neighbor is t, not in closedSet after considering we have cameFrom = [0,s,z,x,y], gScore = [0,2,6,5,9], fScore = [3,4,7,6,9].
5. current = t, which is the goal so we finish.

This gives us our (optimal) path of $sxzyt$ having distance 9. We do not discover $y$ twice because our algorithm doesn't allow us to discover vertices twice.

There are more complicated algorithms that can apply to nonmonotone graphs, you certainly are allowed to use these algorithms. I think they will have you discover $y$ twice, but they will not give a better solution than the one we discovered above (in a nonmonotone graph you may need this more complicated algorithm to find an optimal solution).