# Open Nodes More Than Twice during A* Search? 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* ?

• If I understand correctly, you add (y) to closedSet when you first use it and then you don't open it again. Are you saying you obtain a more optimal solution if you omit using closedSet? – Morgan Rodgers May 25 '18 at 1:15
• The page I cited above explain about monotone condition for optimal search. There's also condition where the graph is non-monotone, you open the previous node and we reach more optimal solution. – raisa_ May 25 '18 at 1:20

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).

• Yes, I found the shortest distance 9 too. But I was tracing the wrong path and went with Y first instead of X. That's why I ended up reopen Y when I went with X. Thanks !! – raisa_ May 26 '18 at 12:17