- Joined
- Oct 12, 2008
- Messages
- 1,570
Given 2n points in a metric space (X, d), (just think of d as "the" distance function), I desire a set (or list, array, whatever) of size n of sets (these really need to be sets, as in order does not matter, but content does) of size 2 of given points such that all the size 2 sets are pairwise disjoint (thus make up the entire set of 2n points), and such that the sum of the distance between all pairs is minimal.
On a more mathematical note:
Given: set A, |A|=2n
Result: set B, |B| = n
B = {B1, ... , Bn}
where, for all i in {1, ... , n}: |Bi|=2,
for all i, j in {1, ..., n}: Bi and Bj are disjoint if i /= j,
Sum from k = 1 to n of: d(Bk, 1, Bk, 2) is minimal
(where Bk = {Bk, 1, Bk, 2} )
The attached PDF file contains the above with more strict notation.
I have been thinking, but only a little, and the best I could come up with is an O(n2) algorithm, a brute force one, first calculating all distances between all points, taking O(n2), and then taking the n smallest, which would take at most O(n2), depending on what method one takes, for instance first sorting and then just taking the first n elements.
More info on how I think this problem could be generalised and the origin of the problem will come in an edit.
EDIT:
A generalisation of the problem (though already quite abstract by using d, instead of a simple minded Euclidean distance function), would be to not create sets of 2, but sets of k. How would one go about generalising to the "distance" of those k elements in each set? I was thinking about a path through all k points, and measuring the distance of that. Then, however, to get the minimal distance, one would again have to get the shortest path through all elements. Graph theory would come in hand here. However, when one can come up with a satisfying function f : B -> R+ (real positive numbers, or 0 included when desired) one could just formalise the problem to minimalise the sum of all f(Bk)
EDIT2:
Where did I come up with such a problem? My job. I see maths and algorithms everywhere. We bake baguettes, and then pack them in pairs. When cooled down enough, we throw a pile of baguettes onto a table, and start packing. I was thinking, how can I take pairs of two and pack them, without having to move my arms more than neccessary? Well when there are only a few, it is quite intuitive and easy, but I then started to set loose my mathematical mind. This problem is all in Euclidean 2-dimensional space, but what about other spaces? Or what about when we start packing in 5's when there is some sort of discount when buying a pack of 5? All these thoughts created this problem.
Now I could of course start to devise my own algorithm, and I would sure enjoy it, but I think I would even more enjoy the discussion created by multiple people thinking about this problem and coming up with varying solutions!
So, now, all and every thought, please share!
On a more mathematical note:
Given: set A, |A|=2n
Result: set B, |B| = n
B = {B1, ... , Bn}
where, for all i in {1, ... , n}: |Bi|=2,
for all i, j in {1, ..., n}: Bi and Bj are disjoint if i /= j,
Sum from k = 1 to n of: d(Bk, 1, Bk, 2) is minimal
(where Bk = {Bk, 1, Bk, 2} )
The attached PDF file contains the above with more strict notation.
I have been thinking, but only a little, and the best I could come up with is an O(n2) algorithm, a brute force one, first calculating all distances between all points, taking O(n2), and then taking the n smallest, which would take at most O(n2), depending on what method one takes, for instance first sorting and then just taking the first n elements.
More info on how I think this problem could be generalised and the origin of the problem will come in an edit.
EDIT:
A generalisation of the problem (though already quite abstract by using d, instead of a simple minded Euclidean distance function), would be to not create sets of 2, but sets of k. How would one go about generalising to the "distance" of those k elements in each set? I was thinking about a path through all k points, and measuring the distance of that. Then, however, to get the minimal distance, one would again have to get the shortest path through all elements. Graph theory would come in hand here. However, when one can come up with a satisfying function f : B -> R+ (real positive numbers, or 0 included when desired) one could just formalise the problem to minimalise the sum of all f(Bk)
EDIT2:
Where did I come up with such a problem? My job. I see maths and algorithms everywhere. We bake baguettes, and then pack them in pairs. When cooled down enough, we throw a pile of baguettes onto a table, and start packing. I was thinking, how can I take pairs of two and pack them, without having to move my arms more than neccessary? Well when there are only a few, it is quite intuitive and easy, but I then started to set loose my mathematical mind. This problem is all in Euclidean 2-dimensional space, but what about other spaces? Or what about when we start packing in 5's when there is some sort of discount when buying a pack of 5? All these thoughts created this problem.
Now I could of course start to devise my own algorithm, and I would sure enjoy it, but I think I would even more enjoy the discussion created by multiple people thinking about this problem and coming up with varying solutions!
So, now, all and every thought, please share!
Last edited:
