Partial path known in Single source shortest path problem

Question

I'm using the A* algorithm with a consistent heuristic on a graph to determine the shortest path.

If the algorithm is exploring a node $p_1$ for which there is a existing knowledge about the optimal $k$ ($p_q,p_r,p_t,p_5$) successive nodes, then can we store $p_5$ directly into the open list? Or do we have to store the intermediate milestones (each node in the known successive optimal nodes) into the open list?

Weights are positive real numbers.

Answer 1

Your question is strongly related to the idea of macro-moves which are defined as follows: $M(p, q)=\langle p, n_1, n_2, \ldots, n_k, q\rangle,ドル i.e., as a list of successive states which are known to get to $q$ from $p$. Additionally, macro moves might guarantee that the path they store is also optimal, i.e., that the path $\langle p, n_1, n_2, \ldots, n_k, q\rangle$ is the shortest path between $p$ and $q$. Let us denote such macro-moves as $M^*(p, q)$.

In the following I'll assume you are interested in computing the optimal path from a start state $s$ to an arbitrary goal state $t$ ---as you actually mention the "shortest path" at the beginning.

So now, regarding your question:

1. In case that $M^*(p,q)$ is known to be a subpath of the optimal path from $s$ to $t,ドル or if alternatively, it is known that the optimal path from $s$ to $t$ does not go through $p,ドル then you can safely substitute each generation of $p$ in OPEN by $q$ with a cost equal to the cost of the path to generate $p$ plus the cost of the path $M^*(p,q)$.
2. In case none of the preceding conditions hold then you can still use the macro-moves but you have then to store each node in $M(p,q),ドル but $p$ of course, into the OPEN list ---i.e., the intermediate milestones you mention.

Hold on! You might think then that the second case is a waste of time/space, but it ain't if you break ties in favour of nodes with larger $g$-values, i.e., while nodes in OPEN are sorted in increasing order of their $f$-value, breaking ties in favour of nodes with larger $g$-values place those nodes with larger $g$-values first ---within the same $f$-layer. This way, in case that an optimal path (as there might be several paths with the same cost and equal to the minimum cost) goes through $p$ there is an opportunity that you will find it without generating other descendants.

To see why, consider that a subpath of $M^*(p,q)$ is part of the optimal path from $s$ to $t,ドル $\langle p, n_1, n_2, ...,n_\ell\rangle,ドル such that $\ell\leq k,ドル and let $g(n)$ denote the cost of the path from $s$ to $n$ and $g(p, n_i)$ denote the cost of the path $\langle p, n_1, n_2, ..., n_i\rangle$ where $\langle p, n_1, n_2, ..., n_i\rangle\subset M^*(p,q)$. The second case suggests to insert into open $n_1, n_2, ..., n_\ell$ each with a cost equal to $g(p)+g(p,n_i),ドル 1ドル\leq i\leq\ell$. If the heuristic function is consistent (as you mention) there is a good opportunity that $f(n_\ell)=f(n_i),ドル $\forall i, 1\leq i<\ell$. Now, breaking ties in favour of nodes with larger $g$-values, $n_\ell$ will be placed before the others so that A$^*$ will expand it first. If $f(n_\ell)$ equals the cost of the optimal path then A$^*$ will find the optimal solution with out expanding nodes $n_i$.

Maybe you think there are many "maybes and ifs" here but consider: first, breaking ties in favour of larger $g$-values is customary practice; second, inserting the intermediate states of $M^*(p, q)$ causes no harm so that proceeding as in the second case is usually a good idea.

Hope this helps,

• letsBeePolite: Yes, that helps. Just curious, can you elaborate on the part "if you break ties in favour of nodes with larger g-values."?
• Carlos Linares López: I certainly tried ... hope it is more clear now