u-dmfloy%ug.utah.edu@wasatch.UUCP (Daniel M Floyd) (03/09/89)
In article <18088@iuvax.cs.indiana.edu> dave@duckie.cogsci.indiana.edu (David Chalmers) writes: >Given integers n and k, we construct k 'circles'... ...[refer to article for reference]... >The problem is to find the construction of k circles which minimizes >this 'maximal least distance' D. In particular, we want to find >F(n,k) which is the smallest possible value of D. Another way of >saying this is that we want the 'cosiest' possible construction - that >construction that lets every pair of integers be as close together >(somewhere) as possible. I'm interested to know how exactly it applies to genetic algorithms, and why, as you said, it is so important. (I do believe you, I'm just curious.) I think that F(n,k) = [n/(2^k)] ([i] means smallest integer greater than or equal to i) So for the example n=6, k=2, 6/4 = 1.5 ; [1.5]=2. For F(n,k) n k 2^k n/2^k [n/2^k] 6 1 2 3 3 6 2 4 1.5 2 6 3 8 .75 1 7 1 2 3.5 4 7 2 4 1.75 2 7 3 8 .675 1 8 2 4 2 2 8 3 8 1 1 Now, I suppose someone will want a proof. As I wrote, I 'think'; I don't have a formal proof. However, I can outline a proof that someone might be able to develop into a theorem. As a matter of fact, I think if you follow this, it will suggest an algorithm to create the circles. Furthermore, you may be able to develop some closed form to tell in the kth circle where integer n belongs. The 'pseudo-proof'(note this is INFORMAL and not precise): A) Consider any single circle with integers 1..n. The maximum distance from any node to any other will be INT(n/2). B) Each such circle, k, has two directions with wich to make the maximum smaller with another circle, k+1. C) Take half of the nodes all adjacent and rotate once(in either direction). For example: 1 2 1 3 6 3 ==> 6 4 Notice how 2,3,4 rotated while 1,6,5 didn't. 5 4 5 2 This single half-rotation will cause all of the maximum distances from each node to decrease by at least one. The one that fliped over (2 in the example) will suddenly drop its previous maximum to 1. (That means the distance 2-5 was three and is now 1). D) Make another rotation in the same direction (don't make another k circle). This will mean for all nodes except the ones that flip over you will decrease again by one the max distances. The ones that flip increase by one. E) You can do this until the max distances on the second circle are all about half of what they were. So, you've rotated the half circle about half way. This make half of the half circle decrease by half, while the other half jumped to 1 and increased to the half way point. F) Next you select two quarter circles to rotate for the 3rd k-circle (k=3). These quarters should be in the same half. This will decrease the maxes by half again. G) Continue halving the rotation sections and the distances rotated until, of course, you have k circles. I hope that's clear. I don't really want to give a formal proof because I've got other things to do. It may be that I've made a mistake and that there's a flaw somewhere in my reasoning. Even if someone does see a flaw, at least it would make a good heuristic. Anyway I hope this helps. Dan Floyd 8<D=
lambert@cwi.nl (Lambert Meertens) (03/10/89)
) I think that F(n,k) = [n/(2^k)] ) ([i] means smallest integer greater than or equal to i) ) F(n,k) ) n k 2^k n/2^k [n/2^k] ) 8 3 8 1 1 In a ring an element has (at most) two immediate neighbours. If it participates in 3 rings, it together has at most 6 immediate neighbours. So at most 7 (counting the element itself) are within distance 1. Conclusion: if F(n,3) = 1, then n <= 7. Generalizing this argument to F(n,k) = d, we have n <= 2kd+1. Hence F(n,k) >= (n-1)/(2k). -- --Lambert Meertens, CWI, Amsterdam; lambert@cwi.nl
u-dmfloy%ug.utah.edu@wasatch.UUCP (Daniel M Floyd) (03/11/89)
In a previous article I wrote "I think that F(n,k) = [n/(2^k)]". I was wrong. It only takes one exception to disprove something like that. I easily found more than one exception when I thought about it some more. Then, I got back on the network to find I'm not the only one that realized the formula was wrong. Oops! <:*) In article <7946@boring.cwi.nl> lambert@cwi.nl (Lambert Meertens) writes: > [..good argument ...] >Hence F(n,k) >= (n-1)/(2k). You are clearly correct. Dan Floyd 8<D=