# Given an admissible/consistent heuristic $h(n)$, would the tree and graph search versions of A* return the optimal path with $g(n)=2h(n)$?

I know that, if the heuristic function is admissible and consistent, then the A* algorithm always returns an optimal solution. But for the following situation, does A* search return optimal solution?

1. Assume I have an admissible heuristic function $$f(n)$$ for all states, now I change it to another one $$g(n) = 2f(n)$$

• Does A* tree search using $$g(n)$$ return an optimal path?
• Does A* graph search using $$g(n)$$ return an optimal path?
2. Assume I have a consistent heuristic function $$f(n)$$ for all states, now I change it to another one $$g(n) = 2f(n)$$

• Does A* tree search using $$g(n)$$ return an optimal path?
• Does A* graph search using $$g(n)$$ return an optimal path?

I guess they are all false, no matter it is a graph or tree search. But I am not sure. Any help is appreciated.

• Hello. I would split this post into 4 posts (or at least 2: one for the admissible case and one for the consistent one), one for each of your questions, because the complete proof may require some elaboration and research effort, so, currently, I think your post is asking the reader too much. Having said that, I can say a few potentially useful things. The tree version of A* is optimal if the heuristic is admissible, while the graph version of A* is optimal if the heuristic is consistent. Moreover, consistency implies admissibility. Having this info will be useful to answer your questions. – nbro May 15 at 21:44