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
    View Source
    • 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 2 of 8 , Dec 8, 2003
      View Source
      • 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 3 of 8 , Dec 9, 2003
        View Source
        • 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 4 of 8 , Dec 10, 2003
          View Source
          • 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.