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

I have 9 numbers: 4 3 2 1 0 -1 -2 -3 -4 they are placed in a circle. Consider them as addresses. that means: every element knows that it has a neighbor that is greater in value on the left, and another neighbor that is smaller in value on the right.
If for example element 0 wants to send a message to element 2, it knows it has to go 2 steps on the left. And if it is searching for -3, it knows it has to go 3 steps on the right.
Each element can perform a search for any other element.
Each element can forward the query to its adjacent neighbor.
IN that case, the worst case scenario would be for element 0 is to search for element 4 or -4, which is 4 steps either way.
Now, if I want to compare the search with this one: The same numbers are arranged in the same circle, however, the search has to go clockwise only, i.e., if I am at 0 and I want to search for 1, I have to walk through all elements clockwise.
Comparing to the first scenario, which one performs better? Should not the first one take half the time of the second one?

Quote:

---

Originally Posted by dinodinoni

that means: every element knows that it has a neighbor that is greater in value on the left, and another neighbor that is smaller in value on the right.

---

Are you sure it means that? What I can see, if the numbers are on a circle, both neighbors of 4 are smaller and both neighbors of -4 are bigger!

It means that in the bidirectional case the decision rule for which direction to take won't always give the shortest way. For example if -4 wants to 4 it will go to the left which is 8 steps away while to the right it's just 1 step. In fact in half of all possible cases you will take the longer way. And this is what happens also in the unidirectional case.

So the bidirectional case with bogus information will be identical to the unidirectional case.

Quote:

---

Originally Posted by razzle

Are you sure it means that? What I can see, if the numbers are on a circle, both neighbors of 4 are smaller and both neighbors of -4 are bigger!
.

---

You are correct.

I will try to explain more here:

If I have 64 elements arranged in a 2 dimensional space (8*8). Each element has 8 neighbors and the system wraps around. (01 can forward to 02 10 09 08 57 58 64 16) like shown. would not the routing performance be log n
please note that they are ordered and structured. And each element knows which direction to go when routing for another element. If A is sending msg to B, it already knows which direction to choose based on the ordering, and it knows that in worst case scenario B is within specific number of steps. Either vertical, horizontal, or diagonal.

01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

Quote:

---

Originally Posted by dinodinoni

I will try to explain more here:

---

I'm not sure I understand what you're asking but lets say you still want to compare the unidirectional and bidirectional cases. And lets say "performance" is defined as the expected (average) distance in steps between two random positions A and B. Each step takes place from one element to its next neighbour either horizontally, vertically or diagonally (on an 8 by 8 grid which wraps around at the edges).

Lets start with just one direction, say the horizontal. That's basically the example from your first post. In the unidirectional case the possible step distances from A to B will be [1,2,3,4,5,6,7]. In the bidirectional case the step-set will be [1,2,3,4] because the shortest of going left or right can always be chosen. If this is generalized we see the unidirectional case has a step-set of roughly N step distances and the bidirectional case has N/2 (N is 8 in this 8 by 8 example).

A step-set really is a uniform random distribution where each step distance has equal probability of being selected. It means that when one step distance is picked at random the expected outcome is the middle distance. We get 4 in the unidirectional and 2.5 in the bidirectional case. Generalized that would be N/2 and N/4 respectively.

Now lets add the horizontal direction. To get from A to B you can take any zig-zag combination of horizontal and vertical steps but as long as you get closer to B in each step there will always be the same total number of steps, namely the horizontal step distance plus the vertical step distance. It will be 4+4=8 unidirectionally and 2.5+2.5=5 bidirectionally. Generalized it will be N and N/2 steps respectively.

Finally we add the diagonal direction. Starting in A the shorter direction vanishes in diagonal steps. The longer direction first shrinks equally much then what's left of it leads up to B. So the step distance between A and B changes from the sum of the horizontal and vertical distances to the longest (maximum) of those distances. Quite cool.

So what we're looking for is the expected maximum (longest) of two step distances drawn at random from a step-set. Without further ado I claim it will not be the middle distance anymore but the two-third distance. This link is not scientifically validated but seems solid,

http://math.stackexchange.com/questi...m-distribution

Unidirectionally it will be 5.3 and bidirectionally it will be 2.7. Generalized it will be 2/3*N = 2N/3 and 2/3*N/2 = N/3 respectively.

---

The overall result is that in the bidirectional case the average number of steps from any A to any B is N/3. The unidirectional case requires twice as many namely 2N/3. (If diagonal movement is disallowed the corresponding numbers are N/2 and N respectively.) Just like it was on a line, the bidirectional case is half of the unidirectional also on a grid.

Thank you for this detailed reply.
If I am considering the worst case scenario. For the Unidirectional, the worst case would be if the A and B are on different edges of the string. That means, it is going to take O(n).
This is not very interesting. However, if we consider the grid I have shown above, and keep in mind that they are structured and organized in specific manner. My worst case scenario for example would not be going from 64 to 01, because at the end 01 is one step from 64 (not 7). That means the worst case is if the element is in the middle between 64 and 01. I would consider that 1/2 n^1/2

Note: each element is capable of analyzing the direction the query should go based on the address it recieves.
Say If 55 is routing a segment to 12, it deduces that it needs to forward it to 46. 46 will fwd to 37-> 28-> 20-> 12.
OR: 55-> 62-> 05-> 12

What do you think?

Quote:

---

Originally Posted by dinodinoni

If I am considering the worst case scenario.

---

With "structured and organized in specific manner" I assume you mean what I decribe at the beginning of my previous reply? Otherwise all bets are off.

I have given the average number of steps for the unidirectional and bidirectional cases. They are 2N/3 and N/3 steps respectively. These numbers are only approximate but becomes better the bigger the N (N=8 in this case). This is okay especially when you look at the big O complexity because it deals with big N.

Since both average cases are linearly dependent on N they have O(N) complexity.

What about the worst case? As I deduced in my previous reply the distance between any two A and B is the maximum of the horizontal and the vertical step distances. So the worst case is when either of these directions is the longest it can be. In the unidirectional case it's N and in the bidirectional case it's N/2. (As I said these numbers are approximate and becomes better with bigger N. In your example the exact numbers are 7 and 4 (which are the rightmost step lengths in what I called step-sets in my previous reply)).

Also here we have a linear dependency on N. This means the worst case complexity in both the unidirectional and bidirectional cases is O(N) just like the average cases.

Finally the best case. In the best case A and B are next neighbours both in the unidirectional and bidirectional cases. This is independent on N so this complexity is constant, that is O(1).

Now it seems worse. I still can not see why it is O(n)!
MY point is: if N is the number of all elements in the grid, I do not need to visit all of them in the worst case, right?
Because once I know in which direction the element I am walking to is located I would walk on a straight line towards that element. Which is N^1/2 in length.
So my worst case would be O(N^1/2).. What do you think?

Hey, Can I give you my email address??
I can give you details on what I am working on.

Quote:

---

Originally Posted by dinodinoni

So my worst case would be O(N^1/2).. What do you think?

---

Well, in my replies I've defined N to mean the side length of the grid (N=8 in your example). It seemed most natural to me but of course you can use the total number of elements instead. Then your N is my N squared. and if you put N^2 into O(N^1/2) you get O(N) and we have arrived at the same complexity.

Are you just trying to find the average time/steps ?

if you're going linear (numerical next) than the average will be N/2 where N is the number of items. (worse case is N-1)
if you're going only down and only right with wrapping. it's (N+M)/2, where N is the width and M is the height of the matrix. (worst case is (N-1)+(M-1))
if you're going up/down and left/right, it's (N+M)/4 (worst case (N+M)/2)

if you can do diagonals (any direction), worst case is max(N/2, M/2), average is a bit complicated to count, I have the formula somewhere, but I don't have it at hand. It's 'difficult' because there's 8 times as many cells outside of the N/2,M/2 rectangle as there are inside it, making it a more complex formula.

Quote:

---

Originally Posted by razzle

... N^2 into O(N^1/2) you get O(N) and we have arrived at the same complexity.

---

I must have missed that..
Makes alot of sense.
Thank you.

Quote:

---

Originally Posted by OReubens

Are you just trying to find the average time/steps ?

---

Thank you!
I am interested in the big O for this case.

Quote:

---

Originally Posted by dinodinoni

I am interested in the big O for this case.

---

I have deduced the average cases and given the O complexity in previous posts.

The average number of steps between any A and any B in the unidirectional and bidirectional cases are 2N/3 and N/3 respectively. This means they're both O(N). N is the grid side length.

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

Quote:

---

Originally Posted by OReubens

.... but I don't have it at hand. It's 'difficult' because there's 8 times as many cells outside of the N/2,M/2 rectangle as there are inside it, making it a more complex formula.

---

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

Quote:

---

Originally Posted by dinodinoni

please note that they are ordered and structured. And each element knows which direction to go when routing for another element. If A is sending msg to B, it already knows which direction to choose based on the ordering, and it knows that in worst case scenario B is within specific number of steps. Either vertical, horizontal, or diagonal.

---

do you mean that when A is "commanded" to send a message to B, A knows both A's and B's address (01,02,...) and the topolgy and ordering of numbers in the grid ? moreover, by "routing" do you mean that A "passes" the command to one of it neighbour until the message is received ?

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

if this is the case, then the algorithmic complexity depends on the choice of that function. This is bounded from below by the shortest distance between two nodes, but it's not bounded from above ( it could be choosen to give an infinite loop, for example ).

So, in order to fix an algorithmic complexity you should specify more requirements on the addressing function ... for example, if we choose the addressing function that picks the neighbour nearest to destination, then, unless I'm missing something, the message route will always have the form of a (possibly empty) diagonal followed by a (possibly empty) straight path;

now, given source and destination addresses i and j in [1,N=MxK], hence with i and j having "grid" coordinates (ix,iy):=( i%M, floor(i/M) ) and (jx,jy):=( j%M, floor(j/M) ), if i and j are indipendent and uniformly distributed so are ix,iy and jx,jy, and being the system invariant with respect to (wrapping) translations the avarage number of routing steps is equal to the conditional avarage number of steps given (ix,iy)==(ceiling(M/2),ceiling(K/2)) ( assuming M and K odd ).

so, in this case the routing step count will be "abs(jx-ix) + abs(jy-iy) - min(abs(jx-ix),abs(jy-iy))" that has a uniform distribution with avarage ceiling(M/2)/2 + ceiling(K/2)/2.

But, note that it's far from obvious that the addressing function defined above is the optimal one ...

Moreover, note that things change a lot if you allow the message to pass the original source address as well; in this case, say, the addressing function can implement the midpoint algorithm used in computer graphics to rasterize a line with the property of staying as close as possible to the true line, hence the resulting routing steps ( with M,K big enough ) will approach the avarage shortest path distance ... ( EDIT:(*))

interestingly, the fact that the midpoint algorithm is the simplest line-rasterization algo I'm aware of, makes me think that an optimal ( = asymptotically approaching shortest path ) addressing function depending only on current and destination addres either does not exist or it's non computable ( for example, via pseudo-randomization ) ...

(*)EDIT: sorry I'm wrong, even in that case the path distance ( as calculated by taking the length of each discrete segment ) won't approach the euclidean distance at all ...

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. :)