Loading ...
Sorry, an error occurred while loading the content.

Re: [aima-talk] Re: sorry,not the 3.14 in the 1st version,but 2st version

Expand Messages
  • shi pu
    Hi,all: Thanks for your discussion. I have (kind of) implemented this problem. I scanned the starting URL,search for the key work link ,expand again and again
    Message 1 of 8 , Dec 9, 2003
    • 0 Attachment
      Hi,all:
      Thanks for your discussion.
       
      I have (kind of) implemented this problem.
       
      I scanned the starting URL,search for the key work "link",expand again and again with breadth-first order,and search the goal tree whether it contains the same Node; for the predecessor function,I used the Google's API because if you use "link:URL" as search query,then results will be the predecessor URLs.
       
      I don't know whether the bidirectional algorithm is best for this problem.The successful probability is about 40% using my program.
       


      Brandon Corfman <bcorfman@...> wrote:
      --- In aima-talk@yahoogroups.com, "chenyu468" <chenyu468@y...> wrote:
      > By the way, I have 2 stupid pre-questions:
      > 1. Why it is necessary to search a path of links from one URL to the
      > other URL? When we search through google, we always entry "key word"
      > not "URL". If we know the "URL" already, what's the need to search
      > through "google?
      >
      > 2. What's the meaning of "predecessor function"?
      > 2.1 In the version 1 of AIMA, I can't find this concept in the Index
      > table?

      1. This is not supposed to be an implementation of a search engine,
      but I think more of a "six degrees of websites" question. (Apologies
      to Kevin Bacon! See http://www.geocities.com/theeac/bacon.html )
      The question is just saying that for this problem a search engine can
      be used to implement a predecessor function.

      2. From the text,
      "Let the predecessors of a node n, Pred(n), be all those nodes that
      have n as a successor. Bidirectional search requires that Pred(n) be
      efficiently computable."

      Brandon




      To unsubscribe from this group, send an email to:
      aima-talk-unsubscribe@yahoogroups.com



      Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.

      __________________________________________________
      Do You Yahoo!?
      Tired of spam? Yahoo! Mail has the best spam protection around
      http://mail.yahoo.com

    • Brandon Corfman
      A bidirectional algorithm IMO would _have_ to be better because the branching factor is cut down significantly. The only drawback I can see is that Google s
      Message 2 of 8 , Dec 10, 2003
      • 0 Attachment
        A bidirectional algorithm IMO would _have_ to be better because the
        branching factor is cut down significantly. The only drawback I can
        see is that Google's "link:URL" feature does not necessarily do a
        great job of finding predecessors. (There seem to be a lot of holes in
        its page indexing with this feature.) But for a problem this large, it
        is probably the only practical alternative. You probably don't have
        gigabytes of storage at your disposal. :-)

        There is one thing : you mention using breadth-first search for node
        expansion. You would only have to use that technique for one
        direction, of course. The other direction could use a less
        memory-intensive approach like depth-limited search that would allow
        you to search more links.

        As I mentioned previously, another option is to try to come up with
        some sort of indication of how relevant a linked page is to the goal
        page (perhaps by indexing relevant keywords on the sites). However,
        that falls more under informed search, and that is a later chapter.

        Brandon


        --- In aima-talk@yahoogroups.com, shi pu <pu_shi2003@y...> wrote:
        > Hi,all:
        > Thanks for your discussion.
        >
        > I have (kind of) implemented this problem.
        >
        > I scanned the starting URL,search for the key work "link",expand
        again and again with breadth-first order,and search the goal tree
        whether it contains the same Node; for the predecessor function,I used
        the Google's API because if you use "link:URL" as search query,then
        results will be the predecessor URLs.
        >
        > I don't know whether the bidirectional algorithm is best for this
        problem.The successful probability is about 40% using my program.
        >
        >
        >
        > Brandon Corfman <bcorfman@a...> wrote:
        > --- In aima-talk@yahoogroups.com, "chenyu468" <chenyu468@y...> wrote:
        > > By the way, I have 2 stupid pre-questions:
        > > 1. Why it is necessary to search a path of links from one URL to the
        > > other URL? When we search through google, we always entry "key word"
        > > not "URL". If we know the "URL" already, what's the need to search
        > > through "google?
        > >
        > > 2. What's the meaning of "predecessor function"?
        > > 2.1 In the version 1 of AIMA, I can't find this concept in the Index
        > > table?
        >
        > 1. This is not supposed to be an implementation of a search engine,
        > but I think more of a "six degrees of websites" question. (Apologies
        > to Kevin Bacon! See http://www.geocities.com/theeac/bacon.html )
        > The question is just saying that for this problem a search engine can
        > be used to implement a predecessor function.
        >
        > 2. From the text,
        > "Let the predecessors of a node n, Pred(n), be all those nodes that
        > have n as a successor. Bidirectional search requires that Pred(n) be
        > efficiently computable."
        >
        > Brandon
        >
        >
        >
        > Yahoo! Groups Sponsor
        > To unsubscribe from this group, send an email to:
        > aima-talk-unsubscribe@yahoogroups.com
        >
        >
        >
        > Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.
        >
        > __________________________________________________
        > Do You Yahoo!?
        > Tired of spam? Yahoo! Mail has the best spam protection around
        > http://mail.yahoo.com
      Your message has been successfully submitted and would be delivered to recipients shortly.