Content deleted Content added
complexity |
|||
Line 110:
polynomial... what polynomial, n^2 is mutch mutch better than n^3
: I would doubt the correctness of that paragraph as a whole... First of all I do not see any exponential running time of the algorithm. It has to visit each vertex in a graph exactly once, as well as it has to consider every edge once. That is linear in the number of vertices and edges. You get some overhead from maintaining the priority queue, but still nothing exponential. Furthermore: If you have a graph that is a list, you can have the best heuristic, but still will do no better than with no heuristic at all, since you have to go the complete path up to the goal node. E.g. <math>s \rightarrow a_1 \rightarrow a_2 \rightarrow \dots \rightarrow a_n \rightarrow g</math> where s is the start node and g the goal node. Here you may have a perfect heuristic, but the running time does not change at all since you cannot skip any nodes. [[User:Regnaron|Regnaron]] 17:24, 14 July 2006 (UTC)
| |||