2
$\begingroup$

I am going through Russel and Norvig's Artificial Intelligence: A Modern Approach (3rd edition). I was reading the part regarding the A* algorithm

A* graph search version is optimal when heuristic is consistent and tree search version optimal when heuristic is just admissible.

The book gives the following graph search algorithm.

enter image description here

The above algorithm says that pop the node from the frontier set and expand it (assuming not in explored set), and add its children to frontier only if child not in frontier or explored set.

Now, if I apply the same to A* (assuming a consistent heuristic) and suppose I find goal state (as a child of some node) for the first time I add it to the frontier set. Now, according to this algorithm, if the goal state is already in the frontier set, it must never be added again (this implies never be updated/promoted right?).

I have a few questions.

  1. I might as well stop the search when I find goal state for the first time as a child of some node and not wait till I pop the goal state from the frontier?

  2. Does a consistent heuristic guarantee that when I add a node to the frontier set I have found the optimal path to it? (because if I don't update it or re-add it with updated cost (according to the graph search algorithm, the answer to the question must be yes.)

Am I missing something? Because it also states that, whenever A* selects the node for expansion, the optimal path to that node is found and doesn't say that when a node is added to the frontier set, the optimal path is found.

So, I'm pretty confused, but I think the general graph search definition (in the above image) is misleading.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

No, the optimal path is found when you pop the goal state. If you stop the search when you first add the goal state then the final path may not be optimal.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yeah, got it. The definition in the pic doesn't apply for weighted graph. Update Step is missing there. That'll solve it. So yeah, pop will be optimal for goal. $\endgroup$
    – Fenil
    Commented Sep 26, 2019 at 8:35
  • 2
    $\begingroup$ I'm not convinced this is true given the OP's mandate that we are "assuming a consistent heuristic". An example would help. $\endgroup$
    – c z
    Commented Feb 2, 2023 at 10:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .