0
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ What is your greedy strategy exactly? It seems your greedy path does not follow the immediate lowest cost edge.. $\endgroup$ Jan 26, 2018 at 0:07
  • 1
    $\begingroup$ I don't understand your question. Nothing in the definition of the TSP alters in any way if you change the mode of transport. There's still a cost of travelling between any two cities and you're still trying to minimize the overall cost. $\endgroup$ Jan 26, 2018 at 0:21
  • 1
    $\begingroup$ What 'geometry' gets you is the triangle inequality. Approximation algorithms for TSP use this, and without that assumption TSP becomes significantly harder to approximate. $\endgroup$
    – orlp
    Jan 26, 2018 at 0:22
  • $\begingroup$ What I guess david is trying to do is to convert costs into lengths on paper, and then try to solve TSP by just inspecting the edges with the eyes. But if this is the case costs may not end to be proportionally right like your SB edge which is less in length than SA edge but still has greater cost $\endgroup$ Jan 26, 2018 at 0:50
  • 1
    $\begingroup$ Did you mean to ask about planar TSP, rather than traveling by plane? ​ ​ $\endgroup$
    – user12859
    Jan 26, 2018 at 1:18

1 Answer 1

6
$\begingroup$

I suggest you read more about the Traveling Salesman Problem. All of your questions are answered in other standard references (such as the Wikipedia link I gave). No, the greedy algorithm is not optimal. You may be interested in the Euclidean TSP, which remains NP-hard. The greedy algorithm is not optimal for that case, either. No efficient algorithm is known that can always find the optimal solution, though there are algorithms that may be useful in practice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.