0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – nbro May 15 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.