Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

If I shortcut an optimal TSP solution, is still optimal?

Let's have a complete undirected metric graph with k nodes; metric graph is a graph that satisfy the triangle inequality, so being w the weight function the for all nodes a, b, c it is true that w(a, c) is less or equal to w(a,b) + w(b,c).

Wlog let's say that the cycle: <1, 2, 3, ..., k, 1> is the optimal TSP solution for that graph.

My question is: if I remove one node from the graph (for example the n-th) and I shortcut the cycle just skipping n is the resulting cycle still an optimal TSP solution?

n.b., The cycle would become <1, 2, ..., n-1, n+1, ..., k, 1>

like image 991
Paolo.Bolzoni Avatar asked Oct 02 '22 01:10

Paolo.Bolzoni


1 Answers

No, this does not hold. A rather handwaving counterexample is given below. I trust you can add the numbers, do the math, and formally verify this (I used this online solver to verify my claims).

Consider these points:

enter image description here

The top point is clearly far away, so it has to be connected to the closest points. The other links then follow, as shown here:

enter image description here

If we exclude the top point, it is more optimal to have the two top points connect to the center point, as shown below. So just short-cutting is not optimal:

enter image description here

like image 159
Vincent van der Weele Avatar answered Oct 12 '22 15:10

Vincent van der Weele