Homework 1 Clarification

anthonyh3

unread,

Oct 13, 2011, 5:05:45 PM10/13/11

to Stanford AI Class

With regards to Homework 1, has anyone gotten any clarification as to
what "expanded" means when talking about nodes in Search Tree and
Search Tree 2? I was hoping someone would have "official"
clarification...

Does "expanded" mean expanding the nodes attached to the current
state, or does it mean visiting the current node (state)? There could
be a big difference in answers based on the definition of expanded.
Consider:

A
/ | \
B C D

Assuming B is the goal state, and the search is left-to-right, if
"expanded" means expanded, when node A is the current state, nodes B,
C, and D are _expanded_ and placed on the frontier. Next, node B is
visited, reaching the goal state and stopping the search. 4 nodes have
been expanded when the search stops. In contrast, if "expanded" means
visited, then only 2 nodes would be expanded when the search stops, as
only A and B were visited.

Based on the simplicity of the trees in question for these homework
questions, I am going to assume that "expanded" actually means
visited, otherwise, 3 of the 4 searches would have the same answer.

Thanks for any clarification anyone can give.

Graeme Humphrey

unread,

Oct 13, 2011, 5:29:51 PM10/13/11

to Stanford AI Class

My thought (and hope as this was how I did it) is that their
definition of "expanded" is visited. I'm mildly confident of this
because the last question (A* search) refers to sequential nodes being
expanded, rather than a set of nodes being expanded. However the last
question differs as they do not include the root node in the count, so
who knows.

Mark Rampton

unread,

Oct 13, 2011, 6:02:13 PM10/13/11

to stanford...@googlegroups.com

In the "Search Network" question (like the others), he tells you to count the root and goal node in the count -- just an FYI because it sounds like you interpreted it differently.

http://www.ai-class.com/course/video/quizquestion/37

--
You received this message because you are subscribed to the Google Groups "Stanford AI Class" group.
To post to this group, send email to stanford...@googlegroups.com.
To unsubscribe from this group, send email to stanford-ai-cl...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/stanford-ai-class?hl=en.

deepakjnath

unread,

Oct 14, 2011, 1:21:32 AM10/14/11

to stanford...@googlegroups.com

I am assuming that he expects to count all the nodes which are touched, including the root node and the goal node.

Graeme Humphrey

unread,

Oct 14, 2011, 3:35:22 PM10/14/11

to Stanford AI Class

After re-watching the video and reading the text, I'm reasonably
confident that "expansion" occurs when the node is chosen, removed
from the frontier, and the child nodes are placed on the frontier.

Graeme Humphrey

unread,

Oct 14, 2011, 5:19:06 PM10/14/11

to Stanford AI Class

I'm doubting my logic in Q6 now. We are told our choice of equal
frontier nodes is to be made left to right, or vice versa. That's all
fine and dandy when traversing down a tree in one direction. But what
happens when you start going back up in the opposite direction. Are
our node choices still the same? If it was solely a decision of me
looking at the graph to ascertain which is left or right, it would be
an impossibility as some child nodes are aligned vertically. So my
assumption was that the "left" and "right" changes as my heading
changes.

Any thoughts?

Bruce Seely

unread,

Oct 14, 2011, 5:21:36 PM10/14/11

to stanford...@googlegroups.com

Isn't that part of what you are supposed to be figuring out as part of
the homework?

N G

unread,

Oct 14, 2011, 5:37:40 PM10/14/11

to stanford...@googlegroups.com

I have the same problem but there is a figure in AIMA book that expanded nodes are highlighted and the highlighted ones are the nodes which were visited not nodes and their children. So I think If we have for example this tree:

a

/ \

b c

/ \ / \

d e f g

and if the goal is e then expanded nodes in BFS are a,b,c,d,e.

--
You received this message because you are subscribed to the Google Groups "Stanford AI Class" group.

To post to this group, send email to stanford-ai-class@googlegroups.com.
To unsubscribe from this group, send email to stanford-ai-class+unsubscribe@googlegroups.com.

Graeme Humphrey

unread,

Oct 14, 2011, 5:42:41 PM10/14/11

to Stanford AI Class

@Bruce I hadn't considered it to be and I hope you are not accusing me
of cheating. I thought the question was designed for me to prove my
understanding of BFS and DFS algorithms. If I was cutting code to do
this I would have some logic to pick evenly ranked frontier nodes, and
the outcome, because they are evenly matched would be a moot point.
Each of the nodes are all candidates to be expanded and we could
quite as easily pick them from a hat.

I was NOT asking for any help in deriving the answer to the question,
I was only asking for help in defining the question and thought it was
useful for discussion.

noisewaterphd

unread,

Oct 14, 2011, 9:49:28 PM10/14/11

to stanford...@googlegroups.com

That is the problem with a good number of the homework questions. BFS and DFS are ideas, not some kind of spec down to the last detail. The method of implementation is up to you and your code, and I can't find anywhere where he has specified the missing details. Additionally, we can't just assume we are to just do it how WE would code it, because he is asking for specific counts as an answer, and how can you grade that without taking into account a specific algorithm?

Graeme Humphrey

unread,

Oct 15, 2011, 2:07:31 AM10/15/11

to Stanford AI Class

The answer to both questions in this discussion have now been
clarified at ai-class.com below the relevant homework questions

gurinder gill

unread,

Oct 16, 2011, 3:00:14 PM10/16/11

to stanford...@googlegroups.com

Guys , Where is the Homework Assignment 1 , i cannot see the Link ?

--
You received this message because you are subscribed to the Google Groups "Stanford AI Class" group.

To post to this group, send email to stanford...@googlegroups.com.
To unsubscribe from this group, send email to stanford-ai-cl...@googlegroups.com.

For more options, visit this group at http://groups.google.com/group/stanford-ai-class?hl=en.

--
Regards,

Gurinder Singh Gill

MSP, MCP

E-Mail : gu...@live.in

gurinders...@gmail.com

Mob. : 7827339919

gurinder gill

unread,

Oct 16, 2011, 3:00:48 PM10/16/11

to stanford...@googlegroups.com

The Link Which I see is Homework 1(Closed) and i cannot click it

Graeme Humphrey

unread,

Oct 16, 2011, 3:07:35 PM10/16/11

to Stanford AI Class

Gurinder - Are you logged in, I'm expanding the link with no issue?

On Oct 16, 12:00 pm, gurinder gill <gurindersinghgi...@gmail.com>
wrote:

> The Link Which I see is Homework 1(Closed) and i cannot click it
>
> On Mon, Oct 17, 2011 at 12:30 AM, gurinder gill <
>
>
>
>
>
>
>
>
>
> gurindersinghgi...@gmail.com> wrote:
> > Guys , Where is the Homework Assignment 1 , i cannot see the Link ?
>

> > gurindersinghgi...@gmail.com

> > Mob. : 7827339919
>
> --
> Regards,
>
> Gurinder Singh Gill
> MSP, MCP
> E-Mail : gu...@live.in

> gurindersinghgi...@gmail.com
> Mob. : 7827339919