Search code examples
algorithmgeometrycomputer-sciencegraph-algorithmtraveling-salesman

What if the travelling salesman travelled by plane?

It seems intuitive to solve a 2D dot-to-dot travelling salesman problem by eye using a greedy strategy. However we can only solve the TSP by eye if the graph is topographically accurate e.g. if A to B is 10 and A to C is 10 then B to C can't be 1000.

Is the greedy strategy still sub-optimal when we obey 2D scaling, ie travelling by plane? Below I managed to create a topographically accurate example where the greedy strategy is indeed sub optimal:

enter image description here

Starting at S:

  • Greedy: S B C A S => 2.83 + 4 + 5 + 2.2 => 14.03
  • Optimal: S A B C S => 2.2 + 3 + 4 + 3.16 => 12.36

Is there something special about the example above that will be common to all suboptimal greedy routes? Can geometry be used to minimize error?

Solution

  • I'm going to expand the comment of @Dukeling into a full answer since it seems to address the questions asked fairly well:

    A graph is called a Euclidean graph if the vertices of the graph are associated with points in a plane and edges have weights equal to the distance between the points.

    Solving TSP on Euclidean graphs is no easier than on general graphs.