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
    ... 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
    Message 1 of 8 , Dec 7, 2003
    • 0 Attachment
      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?


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