Content deleted Content added
Hart~enwiki (talk | contribs) Intuition about why A* is not computationally optimal |
|||
Line 100:
: Well, use A* with the heuristics h(x) = 0 for all x. (meaning using no heuristics at all)
: What you will get is just Dijkstras Algorithm. So in this sense Dijkstra is a special case of A* (namely one where the heuristcs is 0 for all nodes) [[User:Regnaron|Regnaron]] 21:14, 26 May 2006 (UTC)
== Intuition about why A* is not computationally optimal ==
This section points out that A* may not be computationally optimal for non-planar graphs.
The proof of the optimality of A* relies on the fundamental assumption that the triangle inequality is satisfied for every 3-node subset of the graph being searched. A non-planar graph may violate this assumption.
| |||