CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

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

1. Senior Member
Join Date
Oct 2008
Posts
1,456

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

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 )
Last edited by superbonzo; January 18th, 2015 at 04:27 AM. Reason: added corrigendum

2. Junior Member
Join Date
Jan 2015
Posts
10

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

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.

3. Member +
Join Date
Jul 2013
Posts
576

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

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.
Last edited by razzle; January 19th, 2015 at 05:43 AM.

4. Member +
Join Date
Jul 2013
Posts
576

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

Originally Posted by dinodinoni
Razzle,
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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Click Here to Expand Forum to Full Width

Featured