1
$\begingroup$

In the original paper of A* algorithm, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, the author proved the optimality of A* in Theorem 2, page 105.

However, I cannot understand the proof. The assumption is that we have a node in $G_s$ which is not expanded by algorithm A, but in the proof we change the graph to $G_{n,\theta}$, isn't it a problem?

$\endgroup$
4
$\begingroup$

No, it isn't a problem.

The whole idea is that the algorithm doesn't operate on a single graph, but rather on a family of graphs (with costs), determined by what the algorithm knows from the heuristic and the explored nodes. That family is denoted by $G_{n,\theta}$ in the paper.

The admissibility of the heuristic basically means that the actual graph is amongst the family $\{G_{n,\theta}\}_\theta$ for some $\theta$.

The proof of Theorem 2 says, that if the other algorithm established that the shortest path form $s$ to $t$ has cost $f(t)$ and $A^*$ expanded the node $n$ which the other hasn't, it means that the estimate of cost of $s \rightarrow t$ path via $n$ was lower than the actual $f(t)$, which means there is some graph in the $\{G_{n,\theta}\}_\theta$ family where the shortest path from $s$ to $t$ passes through $n$. Because the other algorithm didn't expand $n$, it is not admissible for the assumed graph family (because that particular graph would break it).

In other words, if the problem was eg. going from Madrid to Paris, the algorithm might have discovered that (for simplicity) you can get to Barcelona and Valencia in 300 km. Then you know the distance to Paris is $>$1000 km from Valencia, and $>$800 km from Barcelona. If the other algorithm hasn't expanded Valencia and tells you that the shortest path goes through Barcelona with distance 300 km$+$1100 km (for the stretch Madrid-Barca and Barca-Paris), it hasn't ruled out an (alternative universe) situation where the distance between Valencia and Paris was only 1050 km (and would be therefore shorter).

Apologies for distorting Europe a bit

$\endgroup$

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.