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

Re: sorry,not the 3.14 in the 1st version,but 2st version

Expand Messages
  • chenyu468
    ... for ... find a ... engine ... 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?
    Message 1 of 8 , Dec 7, 2003
    • 0 Attachment
      --- In aima-talk@yahoogroups.com, Paolo Amoroso <amoroso@m...> wrote:
      > Chenyu writes:
      >
      > > I have the 1st vesion AIMA. Could you write down the 3.14 here
      for
      > > discussion?
      >
      > 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?
      >

      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?

      kind regards/chenyu




      >
      > Paolo
      > --
      > Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
    • Paolo Amoroso
      ... [...] ... [...] ... It s a function that, given a node N, returns all nodes that have links to N. Paolo -- Why Lisp?
      Message 2 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
      • Brandon Corfman
        ... 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!
        Message 3 of 8 , Dec 8, 2003
        • 0 Attachment
          --- 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
        • 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 4 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 5 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.