Lets say that i have a set of points (an even number of points). Is there any algorithm that lets me divide them into pairs so that the sum of the distances between the two points in each pair will be minimum? Thanks.

I have no idea how to solve your problem, but you can get a mediocre solution by finding the nearest point to each point and then pairing up points that have each other as their nearest points. Then you remove those points from the list and repeat the process until all the points are paired up. It's nowhere near the true minimum, but it seems to give me mostly short lines(with only a couple not so short lines). Given 1000 random points in a 500 by 500 area I get between 6000 and 6500 total distance.

There are a lot of algorithms for that problem, but I dont know if any of them is optimal except the greedy one.

I believe that class of problems is called "least squares clustering", you can google for that and you will find several references. In your case, you have the additionnal constraint of having exactly N/2 clusters of 2 points.

Do you need an optimal solution, or just a good one?

Quote:

Original post by daniel_i_l Lets say that i have a set of points (an even number of points). Is there any algorithm that lets me divide them into pairs so that the sum of the distances between the two points in each pair will be minimum? Thanks.

Yes, there is an algorithm that does that: try all possible pairings (there are (2n)!/(n!*2^n) of them) and pick the one that has a smallest sum of distances. This can be organized in something like a tree search. The question then is if that's good enough or you need something faster. With a little memory, you can speed it up significantly, although the time it takes would still be exponential. Then you can start with some approximated solution and use it as a bound to abort branches that are guaranteed to have a larger sum of distances than the bound. Or maybe the approximated solution is good enough for your purpose and you should look for something like simulated annealing...

In any case, you didn't say much about your requirements. If the question is strictly whether an algorithm exists (computability), the answer is affirmative.

EDIT: Oh, and what is this question doing in the "Artificial Intelligence" forum?

[Edited by - alvaro on January 16, 2007 2:25:05 PM]

It took a bit of searching, but I found the name of a slightly more general problem than this that has known polynomial time algorithms. Minimum weight perfect matching. Perfect matching = subgraph of a graph such that each vertex has exactly one edge. Minimum weight = the sum of the weights (in this case, distances between vertices) is minimal.

I'm not sure if there are better solutions available for when the graph is complete and/or uses euclidean distance or some other distance metric, but this shows there are at least polynomial time algorithms available for this problem.

Quote:

Original post by alvaro EDIT: Oh, and what is this question doing in the "Artificial Intelligence" forum?

It's quite closely related to loads of AI problems.

As a demonstration, let me paraphrase the original post:
"Lets say that i have an RTS game, with a set of workers and resources (an equal number of each). Is there any algorithm that lets me match workers to resources so that the sum of the time taken for workers to reach the resources will be the minimum?"

Quote:

Original post by Kylotan Quote: Original post by alvaro EDIT: Oh, and what is this question doing in the "Artificial Intelligence" forum? It's quite closely related to loads of AI problems. As a demonstration, let me paraphrase the original post: "Lets say that i have an RTS game, with a set of workers and resources (an equal number of each). Is there any algorithm that lets me match workers to resources so that the sum of the time taken for workers to reach the resources will be the minimum?"

Oh, that makes sense.

I found a library that seems to implement a solution to this problem. This is the relevant part of the documentation: http://www.algorithmic-solutions.info/leda_manual/mw_matching.html.

Thanks for the replies. I asked the question only out of curiosity to see if there was an efficient way to solve it or if it was like the TSP with no efficient optimal solution.

I thought of a game where something like this actually happens. If you select 12 templar in starcraft and tell them to merge into archons, they automatically pair off in a semi-intelligent way. It probably just uses some heuristic like choosing an arbitrary templar and finding the closest match to choose the pairs since normally the player isn't going to arrange the templars in some contrived way to see if they pick the optimal matching.

Quote:

Original post by daniel_i_l Thanks for the replies. I asked the question only out of curiosity to see if there was an efficient way to solve it or if it was like the TSP with no efficient optimal solution.

It is an all-pairs minimization problem. It belongs in the same complexity class as similar problems.

The optimal solution that minimizes it globally is an NP class problem. It is going to take a lot of computation, but that isn't a problem if your network is small or if you can precompute it.

A near optimal solution that minimizes individual pairs is a P class problem. Several good solutions are already posted. Also, you could select any of the "all pairs shortest path" algorithms and use every other pair. It won't be optimal, but it will pair each node with another nearby node for very little computational work.

Keep in mind that in games a near-optimal or monte carlo solution that is easy to implement and runs quickly is generally preferable to an optimal solution that is more difficult to implement, maintain, or compute.