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$
  • 1
    $\begingroup$ What is your greedy strategy exactly? It seems your greedy path does not follow the immediate lowest cost edge.. $\endgroup$ – Curious_Dim Jan 26 '18 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$ – David Richerby Jan 26 '18 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 '18 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$ – Curious_Dim Jan 26 '18 at 0:50
  • 1
    $\begingroup$ Did you mean to ask about planar TSP, rather than traveling by plane? ​ ​ $\endgroup$ – user12859 Jan 26 '18 at 1:18
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, privacy policy and cookie policy

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