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

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

Expand Messages
  • 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 1 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.