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
  • Paolo Amoroso
    ... [...] ... [...] ... It s a function that, given a node N, returns all nodes that have links to N. Paolo -- Why Lisp?
    Message 1 of 8 , Dec 8, 2003
    • 0 Attachment
      Chenyu writes:

      > --- In aima-talk@yahoogroups.com, Paolo Amoroso <amoroso@m...> wrote:
      [...]
      >> Here is the text of exercise 3.14 from the 2nd edition of AIMA:
      >>
      >> Write a program that will take as input two Web page URLs and
      > find a
      >> path of links from one to the other. What is an appropriate search
      >> strategy? Is bidirectional search a good idea? Could a search
      > engine
      >> be used to implement a predecessor function?
      [...]
      > 2. What's the meaning of "predecessor function"?

      It's a function that, given a node N, returns all nodes that have
      links to N.


      Paolo
      --
      Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
    • 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 2 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 3 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.