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.

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

Yes But that isn't the right algorithm for such a problem.

If all the ships travel at the same speed, you should seek the smallest maximum distance between a pair of ships, not the smallest sum.

Let me give an example.



if you use the smallest sum algorithm, it will pair (B,C) and (A,D) because the sum is 80, otherwise it would be 100.

if you use the smallest maximum, it will pair (A,B) and (C,D) because the maximum is 50, otherwise it would be 70.

Now if your ships move at the same speed, all the ships will be fastest in a pair if you take the smallest maximum.

However, if you had a problem where you need to connect pairs of points with the least length of rope, you should use the smallest sum algorithm.

I hope this can be useful for enyone.

Greets

I think either problem is applicable. Minimizing total distance will minimize the, uh, number of templar-seconds, if we multiply the number of templars by the time that they exist before merging (maximizing the amount of archon-seconds). Minimizing maximum distance will minimize the time it takes for all templar to merge.

Minimizing maximum distance is a much easier problem. Build a complete graph, then put all the edges in a priority queue sorted by decreasing edge weight. For each edge in the queue, if both of the vertices have degree greater than 1, remove the edge from the graph; otherwise, skip that edge. The resulting graph will be a perfect matching with minimum maximum weight.

Ok Vorpy, if you put it that way.

But if you didn't multiply the number of templars by the time that they exist before merging, and we just say:
"I want all poins in pairs a.s.a.p.",
than the time it takes for all the points to be in pairs is the time it takes for the pair of points who are the farest away from each other. So, the minimum maximum distance.

I know what you mean, and I also hope that you know what I mean. [wink]

Greets

Quote: Original post by delta user

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

Yes But that isn't the right algorithm for such a problem.

If all the ships travel at the same speed, you should seek the smallest maximum distance between a pair of ships, not the smallest sum.

Interesting observation. However, in this example what's wanted, depending on strategic and tactical consideration, is minimizing the minimum distance (i.e. the time between the order and having the first archon available) or more generally minimizing the Nth smallest distance (the time it takes before having N archons, with the other merging pairs not needed immediately); usually one wants to use archons, not to destroy templars.