Hello !!!
I am a bit confused with A* time complexity. I can not understand why the complexity depends on the Heuristic function , according to the wikipedia
What’s the time complexity damn it :twisted: :twisted: :twisted: :twisted: :twisted:
I’m working on A* too and i’ve understand the more your Heuristic evaluation is good, the more your pathfinding will be fast, but i don’t remember exactly why.
http://www.policyalmanac.org/games/aStarTutorial.htm may explain it better than me
Time complexity is an analytical assessment of how the amount of time an algorithm takes to execute is related to the number of inputs or data points the algorithm runs over. In the case of A*, the heuristic function is invoked for each pair of nodes in the search graph, so the higher its execution cost, the higher the execution cost of the entire A* algorithm.
Put in much simpler terms: the more expensive/inefficient your heuristic function is, the slower your A* searches will run.
Well, i just use the Euclidian distance for Heurestic :? :? :? :? :?
A* has other uses beyond pathfinding, so the heuristic can be very abstract in some cases. For pathfinding, the Euclidean distance is a good choice when searching through waypoints at arbitrary positions in space. However, if the game is played on a grid where only horizontal and vertical moves are allowed, then the rectilinear or “Manhattan” distance is a better estimate. There may be other factors you can take into account, too. Say, for example, that all paths to a target go through a single waypoint, a narrow bridge between two riverbanks, perhaps. You could just use the Euclidean distance from start to target, but in reality, the path will have to go across the bridge. You can therefore get a more accurate estimate in this case by getting the distance to the bridge and then from the bridge to the target and adding them together. This will speed up the search because the algorithm is less likely to try positions along the riverbank that are near to the target in Euclidean terms, but are nowhere near the bridge.
Andeeee your thoughts on Manhattan-Euclidian distance are correct but what i’m trying to find out is different.
Let’s take A* step by step:
At first we search the openList(simple Linked List) for the least cost node we have a complexity of O(n)
Then we searh the closed list to see if that node is already searched.Complexity O(n)
Finally we add a new node to the open list O(1)
So the overall complexity is O(n).
The Heurestic has no complexity at all, it is just multiplication.
Maybe there is a connection between the Heurestic method and how many loops are done in order to get our result.
I think it is very weird that there is no explanation for the | h(x) − h * (x) | = O(logh * (x)) :? :? :? :?
If your heuristic is an oracle for distance that doesn’t need to check every element at a particular depth, you can do better than O(n). Look at the part of the page where it talks about optimal heuristic. If your heuristic is perfectly optimal, then your complexity is Theta( log(n) ).
Also note that an assumption of O(n) complexity for searching the open list is only valid if the heuristic cost can be determined directly from the node; in more abstract search graphs, it’s possible more nodes would need to be considered to generate a reasonable heuristic – especially if the graph has a higher order dimensionality, which isn’t hard once you get away from (2- or 3-dimensional) spatial graphs.
ETA: also, look at Theta*, a path optimizing variant of A*, which needs to do line-of-sight tests and euclidean distance calculations for path relaxation at each expansion…
Ok, I’m starting to get the picture 
, and i’ve found a very usefull link which explains a lot :
http://www.ai.mit.edu/courses/6.034b/searchcomplex.pdf
So my conclusion is that the worst case for A* is O(b^(d+1)) but practically is less than that because of the heurestic. In order to make the A* run in polyonimal time we have to satisfy | h(x) − h * (x) | = O(logh * (x)) but we cannot calculate h*(x) , cause if we could we would use it !.
Finally a quote from the book: Artificial intelligence, a modern approach
To make the long story short O(b^(d+1)) :shock: :shock: :shock: :shock: