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.
--- In email@example.com, shi pu <pu_shi2003@y...> wrote:
> 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 firstname.lastname@example.org, "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."
> Yahoo! Groups Sponsor
> To unsubscribe from this group, send an email to:
> 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