Two salesmen - one always visits the nearest neighbour, the other the farthest

Question

Consider this question relative to graph theory: Let G a complete (every vertex is connected to all the other vertices) non-directed graph of size N x N. Two "salesmen" travel this way: the first always visits the nearest non visited vertex, the second the farthest, until they have both visited all the vertices. We must generate a matrix of distances and the starting points for the two salesmen (they can be different) such that:

• All the distances are unique Edit: positive integers
• The distance from a vertex to itself is always 0.
• The difference between the total distance covered by the two salesmen must be a specific number, D.
• The distance from A to B is equal to the distance from B to A

What efficient algorithms cn be useful to help me? I can only think of backtracking, but I don't see any way to reduce the work to be done by the program.

Answer 1

Geometry is helpful.

Using the distances of points on a circle seems like it would work. Seems like you could determine adjust D by making the circle radius larger or smaller.

Alternatively really any 2D shape, where the distances are all different could probably used as well. In this case you should scale up or down the shape to obtain the correct D.

• Edit: Now that I think about it, the simplest solution may be to simply pick N random 2D points, say 32 bit integer coordinates to lower the chances of any distances being too close to equal. If two distances are too close, just pick a different point for one of them until it's valid.

Ideally, you'd then just need to work out a formula to determine the relationship between D and the scaling factor, which I'm not sure of offhand. If nothing else, you could also just use binary search or interpolation search or something to search for scaling factor to obtain the required D, but that's a slower method.