Results 1 to 10 of 10

Math Help - search cost

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    23

    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
    Last edited by liberty; October 13th 2010 at 02:07 PM. Reason: corrections in terminology
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2009
    Posts
    23
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2009
    Posts
    23
    Quote Originally Posted by Traveller View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Quote Originally Posted by liberty View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2009
    Posts
    23
    Quote Originally Posted by Traveller View Post
    "...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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2009
    Posts
    23
    ok
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Nov 2009
    Posts
    23
    thanks
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Nov 2009
    Posts
    23
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Process cost systems,total cost under the FIFO Method.
    Posted in the Business Math Forum
    Replies: 0
    Last Post: December 5th 2009, 12:13 AM
  2. Marginal Cost/Demand and Cost
    Posted in the Calculus Forum
    Replies: 4
    Last Post: November 4th 2009, 07:45 PM
  3. search For f - 1
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: October 28th 2007, 07:11 PM

Search Tags


/mathhelpforum @mathhelpforum