CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 2 of 2 FirstFirst 12
Results 16 to 19 of 19
  1. #16
    Join Date
    Oct 2008
    Posts
    1,456

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

    Quote Originally Posted by dinodinoni View Post
    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. #17
    Join Date
    Jan 2015
    Posts
    10

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

    Quote Originally Posted by superbonzo View Post
    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. #18
    Join Date
    Jul 2013
    Posts
    576

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

    Quote Originally Posted by dinodinoni View Post
    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. #19
    Join Date
    Jul 2013
    Posts
    576

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

    Quote Originally Posted by dinodinoni View Post
    Razzle,
    Please contact me on dinodinoni@hotmail.com
    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.

Page 2 of 2 FirstFirst 12

Tags for this Thread

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