Finding path back from the goal does not work when the graph has loops about astar HOT 3 OPEN

x shouldn't be considered adjacent to x, should it?

from astar.

That depends entirely on the underlying state space. In general, graphs can have loops, i.e. nodes which are their own successors. The original A* paper does not exclude such graphs, and to my knowledge most other A* implementations work for graphs that have loops. The original A* paper is unfortunately behind a paywall, so I'll cite the relevant definition here

A graph G is defined to be a set nodes and a set {e_ij} of directed line segments called arcs. If e_pq is an element of the set {e_ij}, then we say that there is an arc from node n_p to node n_q and that n_q is a successor of n_p.

Note that this does not exclude arcs e_ii for node n_i. Of course, using such an arc would yield a suboptimal solution (assuming it has cost > 0), but the algorithm should still work regardless. Indeed, as formulated in the paper it does work. I'd argue that it should at least be noted somewhere (e.g. Haddock documentation) that this implementation only works for graphs without loops.

from astar.

Ah I wasn't aware of the terminology there, thanks.

from astar.