1
$\begingroup$

That is, if h(n) = h*(n), then A* only expands nodes that lie on an optimal path to the goal. But does this imply that A* will always take a linear time in the solution length to find an optimal solution?

I suspect I may be overthinking this problem, but if h(n) = h*(n) then we are measuring the exact heuristic cost of arriving at a goal node $n$ from x. But I can't see why this would be true, because even though you have a perfect heuristic, it is not monotone, and so you may have a cheaper f-value that may be expanded at a later point in the search, which no longer means the search space is linear.

Improve this question
$\endgroup$
2
  • $\begingroup$ I don't think so. Suppose you have a binary tree representing the state space, with unit edge weights, such that all the leaves are optimal goals (at the same depth). I suppose you can have A* expand the entire graph, unless it somehow also breaks ties in $f = g + h$ by selecting the deepest node to expand (which A* doesn't do in general, I believe). $\endgroup$ – Omar Oct 20 '17 at 15:55
  • $\begingroup$ Do you have an example where the cost of arriving is not monotone? $\endgroup$ – amitp Oct 23 '17 at 16:46
2
$\begingroup$

First, to be specific I’m going to assume your heuristic function runs in constant time and we have a graph G with n nodes, and that you are asking about linearity with respect to n.

I claim that in the worst case A* will run in quadratic time.

Suppose G is a complete graph where every edge has a weight of 10000 except for the “true path” which winds from the starting node along every other node until the final node, and these edges have weight 1.

By definition of A*, every time we visit a node, we look across all its edges to queue up nodes into our priority queue of paths to explore. By construction, we visit every node and hence consider every edge. It is a complete graph on n nodes, so there is roughly n^2 edges, thus this process takes quadratic time

Improve this answer
$\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.