If h(n) is a perfect heuristic (that is, h(n) = h*(n)), then does it imply that A* will always take linear time complexity?

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.

• 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). – Omar Oct 20 '17 at 15:55
• Do you have an example where the cost of arriving is not monotone? – amitp Oct 23 '17 at 16:46