a searching algorithm in a circle: 1 unidirectional, 2- Bididirectional

Quote:

---

Originally Posted by dinodinoni

Would it be possible to give me the formula? or show me where to get it from?

---

BTW, for big N,M, that's the avarage of the shortest path ( that is the euclidean distance ), that is, for a square region NxN :

(1/N^2) * integral_from{-N/2}to{N/2} integral_from{-N/2}to{N/2} sqrt( x^2 + y^2) dxdy

that is

(N/8) integral_from{-1}to{1} integral_from{-1}to{1} sqrt( x^2 + y^2) dxdy

that should equal N * ( sqrt(2) + arcsinh(1) )/6 = N * 0.382598...

EDIT: sorry, I misread OReuben's post; as it's defined that distance does NOT approach the euclidean distance at all, so the calculation above as referred to the OReuben's reply is wrong ... ( the calcaulation in itself is correct though )

Quote:

---

Originally Posted by superbonzo

so, the routing algorithm would be, pseudocodishly:

if destination_address is current node address, stop
else if destination_address is in neighbourhood, forward to neighbour
else forward to some neighbour, computed ONLY in term of current node and destination address, let's call this the addressing function

...

---

Element A will know the addresses of his 8 direct neighbors only.
All elements are present. No gaps between elements.
Each element is smart enough to know the direction it should send or forward the message to.
The forwarding will only be to the element that has an address closest to the destination.

Quote:

---

Originally Posted by dinodinoni

would it be logical to consider the average path length in this case as the diameter of the network?

---

Well, topogically you're on a torus and since a torus can be view as two circles and they're equal in this case because the grid is square, I guess you can speak of a diameter.

Your grid has so called Chebychev metrics (rather than Euclidian) and here the circumference to diameter ratio is 2 (rather than pi). I would say the circumference of an N by N grid most naturally is N and that would mean the diameter be N/2.

I see what you're hinting at. For symmetry reasons the average placement of any A and B then should be diametrically opposite of each other, that is N/2 apart right? But the analysis in my first post shows somewhat counter-intuitively that the average (Chebychev) distance is rather 2N/3 in the unidirectional case and N/3 in the bidirectional case. I cannot find anything wrong with my reasoning so I stick with those figures for the time being until proved wrong.

Quote:

---

Originally Posted by dinodinoni

Razzle,
Please contact me on [email protected]

---

Well, I don't have time to get too involved so I prefer to discuss in public. Then also you reach more people and get better help. :)