help with shortest path/nearest neighbor (a bit like multiple traveling salesmen)

ottenm

I have about 100 points spread randomly across the screen (set A), and a small cluster of about 10 points randomly distributed on the same screen (set B). I need to connect each point in B to it's nearest neighbor in A using the shortest total distance possible. Each point in B has to connect to a unique point in A. It seemed easy enough: for each point in B find the closest point in A, connect and repeat. Not working. Suppose the first point in B (say, B0) finds the first point in A (A0) to be the closest. Good enough. But suppose I move on to B1 and find that A0 was actually closer to B1 than B0 (but is already taken). Struggling to find a clear way of structuring the search. Suggestions greatly welcome!

quark

The problem resolves into having two sets of points
A0-Am (where m ~ 100) and
B0-Bn (where n ~ 10)

Now according to your description you need to find i and j where the distance Ai to Bj is the smallest distance between two points, one in set A and 1 in set B and then repeat until all B points are used up.

Algorithm
1) Create a 2D array of floats e.g. d[m,n] and calculate the distances between each A and each B. Once the array is full

1) find the smallest value in the array, this corresponds to the smallest A-B distance. Note the indices i and j for this A-B combination

2) make all column values (d[0-m], j) = Float.MAXIMUM_VALUE

3) make all row values (d[i, 0-n]) = Float.MAXIMUM_VALUE

4) go back to (1) until there are no unused B points.

Note this algorithm requires m>n.

ottenm

Thanks a million quark!! Couldn't get my head around some minimal approach and didn't notice the obvious: calculate the distance for every pair and work your way from the shortest -> longest. Can't thank you enough for taking the time to understand the problem and provide such a great, thorough solution! I hope it's a smooth week for you wherever you're at!!