5992Re: [decentralization] random walk searches
- Jul 7, 2002Thanks for the clarifications.
At 19:43 -0400 2002/07/07, Lucas Gonze wrote:
> > Otherwise, it would be interesting if someone found an effective wayGoes back to AI in the 70's as far as I know (but then, I'm just an
>> of implementing an A* -type algorithm in a p2p system. Anyone ever
>> done that?
EE so I might not know). I read about it first in Winston's
Artificial Intelligence, MIT 1979. (I quoted it in my PhD thesis but
don't actually own the book so this is from -- weak -- memory)
It's basically a search algorithm that selects the next node based on
an estimate of the distance between the current node and where the
result may be. As far as I recall, it is proven to be optimal (with
respect to the number of nodes traversed) for "good-enough"
estimation functions. Depending on what the estimate says, it turns
out to be breadth or depth first at the extremes. Surprisingly, "good
enough" does not need to be particularly good. I think
underestimation of distance was always okay, overestimation was bad,
but I would think that one should be able to distribute data over a
p2p network in a way that a corresponding "appropriate" estimation
function could be constructed?!?
- << Previous post in topic Next post in topic >>