enter image description here

This space graph fulfilled the monotone condition of :

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

enter image description here

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* ?

  • $\begingroup$ 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? $\endgroup$ – Morgan Rodgers May 25 '18 at 1:15
  • $\begingroup$ 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. $\endgroup$ – 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).

| cite | improve this answer | |
  • $\begingroup$ 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 !! $\endgroup$ – raisa_ May 26 '18 at 12:17

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.