Thread: search cost

Breadth first search. Suppose you perform a breadth first search in a tree with branching factor b. But we don't know that the space
search is a tree, so we try to avoid expanding
nodes that have been already encountered and expand. Thus, for each new node
generated, we check whether it is the same as any other node that has been encountered.
How many tests will be done in a search to depth d; (expression
parameters b and d)

Any help on that will be appreciated...

edited

I think that i made a solution, we 'll see. I 'll write my solution here in a few days if nobody writes his solution to the problem.

The parameters make sense only if we assume that we know the graph does not contain any self-loops or multiple edges. For each vertex that we encounter we should check whether it is equal to any non-sibling vertex in that level. For each vertex, there will be (x-1)b such vertices, where x is the number of vertices in the previous level. Sum up for all vertices in the level, compute x for that level, and sum over all levels upto d.

Originally Posted by Traveller

The parameters make sense only if we assume that we know the graph does not contain any self-loops or multiple edges. For each vertex that we encounter we should check whether it is equal to any non-sibling vertex in that level. For each vertex, there will be (x-1)b such vertices, where x is the number of vertices in the previous level. Sum up for all vertices in the level, compute x for that level, and sum over all levels upto d.

Thank you very much for your reply...
The parameters make sense only if we assume that we know the graph does not contain any self-loops or multiple edges.
The graph is a tree. But suppose that we don’t know that, and we have to make all the appropriate tests...

For each vertex that we encounter we should check whether it is equal to any non-sibling vertex in that level.
why only in that level? Can you explain? I don't get it.. Why not ALL the nodes previous to this node in our searching? ( exept father and siblings )

Thanks again.

Originally Posted by liberty

The graph is a tree. But suppose that we don’t know that, and we have to make all the appropriate tests...

Sorry, my bad, I understood the question wrong. The parameters will be valid even if self loops and multiple edges are assumed to be present. Then we have to check the parent and siblings too.

why only in that level? Can you explain? I don't get it.. Why not ALL the nodes previous to this node in our searching? ( exept father and siblings )

Even if self loops are assumed to be present, outside of the same level, the checking will be limited only to the vertices in the previous level. This is
because the earlier levels had already had all of their edges exhausted due to the BFS.

Originally Posted by Traveller

"...the checking will be limited only to the vertices in the previous level. This is
because the earlier levels had already had all of their edges exhausted due to the BFS."

Is this the case (had already had all of their edges exhausted due to the BFS) and for some nodes in the previous level? So i have to count only previous nodes in the same level and some nodes in the previous level?

Thank you Traveller

A BFS moves to a certain level only if ALL the edges belonging to the previous level have been exhausted. So, if the BFS is creating level i+1 by exploring the edges from level i, then we can conclude that it has already exhausted all the edges from level i-1. Now, say the BFS is exploring the edges of the kth vertex in level i. This means that all the edges from the k-1 vertices that occur before this vertex in level i, have been exhausted. So there can be four cases for any vertex which we come across while exploring the edges of vertex k:

1) It is vertex k itself.

2) It is some other vertex in level i which occurs AFTER vertex k.

3) It is some vertex that is already in level i+1.

4) It is a new vertex.

ok

thanks

Hi Traveler ..hello to forum.
All the previous i think that requires that the graph is not directed...
If it is then... the first answer i gave, isn't it correct? (checking for all previous)

I hope you are fine. And thank you for all our previous discussion.