Question

Expand Messages
• I have a doubt related to Breadth-first Search . In this strategy you first verify if a node is the goal and, if it is not, you create its children and then
Message 1 of 7 , Sep 5, 2013
I have a doubt related to "Breadth-first Search". In this strategy you first verify if a node is the goal and, if it is not, you create its children and then verify the next node at the same level. In the worst case, you create the children of all the nodes at a level, except for the last one, which is the goal, that is,           b^(d+1)-b nodes.  The question is: wouldn't it be better to create the children after all the nodes of a determined level have been verified? What is the advantage of creating nodes that may not be verified? I think it would be useful a brief explanation about this in the book Artificial Intelligence.

Jarbas Joaci de Mesquita Junior

• Hi, I am not sure which edition of the book you have, but in the third edition BFS is modified to test for goal when the node is generated not when expanded.
Message 2 of 7 , Sep 9, 2013
Hi,
I am not sure which edition of the book you have, but in the third edition BFS is modified to test for goal when the node is generated not when expanded. With this, the complexity is O(b^d) instead of O(b^(d+1)). This also implies that no level is generated if the goal is contained in the previous level.

Regards,

H.B.

From: Jarbas Joaci <jarbas_joaci@...>
To: "aima-talk@yahoogroups.com" <aima-talk@yahoogroups.com>
Sent: Thursday, September 5, 2013 8:01 PM
Subject: [aima-talk] Question

I have a doubt related to "Breadth-first Search". In this strategy you first verify if a node is the goal and, if it is not, you create its children and then verify the next node at the same level. In the worst case, you create the children of all the nodes at a level, except for the last one, which is the goal, that is,           b^(d+1)-b nodes.  The question is: wouldn't it be better to create the children after all the nodes of a determined level have been verified? What is the advantage of creating nodes that may not be verified? I think it would be useful a brief explanation about this in the book Artificial Intelligence.

Jarbas Joaci de Mesquita Junior

Your message has been successfully submitted and would be delivered to recipients shortly.