Thanks for the clarifications.

At 19:43 -0400 2002/07/07, Lucas Gonze wrote:

<snip/>

> > Otherwise, it would be interesting if someone found an effective way

>> of implementing an A* -type algorithm in a p2p system. Anyone ever

>> done that?

>

>A*, Johannes?

Goes back to AI in the 70's as far as I know (but then, I'm just an

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?!?