Hiya buddies, I've seen that most blind search algorithms are exponential in complexity. But when we implement the A* search, with breadth-first searching, so that no state is never tested twice (a simple hash array makes this O(1)), won't it be linear in time even in the worst case (considering n=the number of tiles in the "game area")? Or will this kind of simple pruning of states result in non-optimal or even incomplete (ie. non-converging) A* pathfinding? Or should the pruning be implemented so that when we back up in tree, the hash elements of the discarded tree node are discarded too? If I read AIMA (Artifical Intelligence: Modern Approach) correctly, this shouldn't be required... - Mikko Kauppila [edited by - uutee on April 12, 2003 7:09:06 PM]

Typically this exponential complexity is refering to an infinite tree with constant branching factor. If the tree is finite, many blind searches(bfs, dfs) will run in O(V+E)

quote: Original post by uutee
But when we implement the A* search, with breadth-first searching, ...

There''s something very wrong with this statement... A* does not implement breadth-first search... so obviously you meant something else by this. Could you explain what you actually meant please?

Thanks,

Timkin

Perhaps my understanding of the problem ain''t perfect but surely if you enforce the condition that you can only visit any node once then if your distance evaluation ain''t perfect (which it is going to be if there is a kink in the path) then when there is an alternative path you might find yourself on a non-optimal path.

Alternatively a dead-end will possibly result in not finding any solution at all.

Timkin: whoops sorry, my fault. Of course I meant that when a node is expanded, its children are added to the fringe queue. Then we find the fringe node with the smallest f=g+h on which we continue. The standard AIMA copy

- Mikko Kauppila

One way to think of this problem is in the following way...

A* guarantees to expand all nodes within a given cost contour before moving on to a higher contour... so that it expands nodes in order of increasing f. The number of nodes within the goal contour will be exponential in the length of the optimal path unless the error in the heuristic grows no faster than the logarithm of the actual path cost. For heuristics like straight line distance or Manhattan distance (or any of the Euclidean norms), the error is proportional to the path cost, resulting in exponential growth.

Timkin