Here's an easy solution (solutions are easy if the problem is hard because you don't have to try too hard since it will be very difficult to prove your solution isn't worse than an alternate)
1. Choose some number k < N the number of points
2. Choose the k closest pairs and connect them.
3. for each of the rest of the points, find the closest one to one of the endpoints of the k groups and add it in. Also include the endpoints of the groups (this results in a merge)
4. Repeat until all points added in.
5. Find "closest" group pairs and merge them. The closest group pair is the pair that can be merged with the least increase to the distance (you can connect endpoints, or do variations where you cut the groups in half and glue the 2 halves to another group).
6. Repeat (5) until all groups merged.
7. Repeat 1-6 experimenting with different values of k.
8. Simmer well until done to taste :)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment