Optimal TSP-Tour in Grid-City: Let's Find Out

[mathmari]

Hey!

We consider the TSP in Grid-City.
The roads in Grid-City have the form of a grid, so that the intersection points can be described by an integer coordinate system.
The distance of $2$ points $C=(x,y)$ and $D=(x',y')$ is defined as $d(C,D)=|x-x'|+|y-y'|$.
An input for the TSP consists of $203$ points with the following coordinates:
$$(i,0), \text{ for } i=0, 1, \dots , 100, \\ (i,2), \text{ for } i=0, 1, \dots , 100, \\ (103, 0)$$
I want to give the optimal TSP-Tour. We have the following grid, or not?
View attachment 5787
(Wondering)

To find the optimal TSP-Tour from which point do we start? From which point we want? (Wondering)
If we choose one point to start, let's consider the $S=(0,0)$.
The second point will be either $A=(0,2)$ or $B=(1,0)$, right? Since $2=d(S,A)>d(S,B)=1$, the second point is $B=(1,0)$.
Or can we consider for the second point also the diagonal one, $(1,2)$ ? (Wondering)
Or is this not the correct way to find the optimal TSP-Tour? (Wondering)

When the roads are just the vertical and horizontal lines, we have that the distance of a point $(i,j)$ to an other is either $d_1=1$ or $d_2=2$, or not? (Wondering)
If this is true, is the optimal TSP-Tour the following?
$$(0,0)\rightarrow (1,0) \rightarrow (2,0) \rightarrow \dots \rightarrow (100,0)\rightarrow (103,0)\rightarrow (100,2) \rightarrow (99,2) \rightarrow \dots \rightarrow (1,2) \rightarrow (0,2) \rightarrow (0,0)$$
But how do we get from the point $(103,0)$ to the point $(100,2)$ ? (Wondering)

 

[I like Serena]

Hey!

We consider the TSP in Grid-City.
The roads in Grid-City have the form of a grid, so that the intersection points can be described by an integer coordinate system.
The distance of $2$ points $C=(x,y)$ and $D=(x',y')$ is defined as $d(C,D)=|x-x'|+|y-y'|$.
An input for the TSP consists of $203$ points with the following coordinates:
$$(i,0), \text{ for } i=0, 1, \dots , 100, \\ (i,2), \text{ for } i=0, 1, \dots , 100, \\ (103, 0)$$
I want to give the optimal TSP-Tour. We have the following grid, or not?

(Wondering)

To find the optimal TSP-Tour from which point do we start? From which point we want? (Wondering)
If we choose one point to start, let's consider the $S=(0,0)$.
The second point will be either $A=(0,2)$ or $B=(1,0)$, right? Since $2=d(S,A)>d(S,B)=1$, the second point is $B=(1,0)$.
Or can we consider for the second point also the diagonal one, $(1,2)$ ? (Wondering)
Or is this not the correct way to find the optimal TSP-Tour? (Wondering)

When the roads are just the vertical and horizontal lines, we have that the distance of a point $(i,j)$ to an other is either $d_1=1$ or $d_2=2$, or not? (Wondering)
If this is true, is the optimal TSP-Tour the following?
$$(0,0)\rightarrow (1,0) \rightarrow (2,0) \rightarrow \dots \rightarrow (100,0)\rightarrow (103,0)\rightarrow (100,2) \rightarrow (99,2) \rightarrow \dots \rightarrow (1,2) \rightarrow (0,2) \rightarrow (0,0)$$
But how do we get from the point $(103,0)$ to the point $(100,2)$ ? (Wondering)

Hey mathmari! (Smile)

That looks all correct to me. (Nod)
In principle any point could be connected to any other point, but in this particular case your solution will be optimal.
We can get from $(103,0)$ to $(100,2)$ with a normal transition that has distance $5$. (Emo)

 

[mathmari]

In principle any point could be connected to any other point

So the road aren't just these gray lines, right? (Wondering)
View attachment 5792

Are the roads also the red lines:
View attachment 5793
? (Wondering)

in this particular case your solution will be optimal.

How do we know that? (Wondering)

 

[I like Serena]

So the road aren't just these gray lines, right? (Wondering)


Are the roads also the red lines:

? (Wondering)

Yep! (Nod)
That's pretty much the problem with TSP - we have to consider all possible roads to find the solution, which is why it is so hard to find an optimal solution.

How do we know that? (Wondering)

It follows from common sense.
If we pick any of your red lines, the total path length will surely increase.
I'm not exactly sure how to prove it though. (Worried)

 

[mathmari]

That's pretty much the problem with TSP - we have to consider all possible roads to find the solution, which is why it is so hard to find an optimal solution.

Ah ok... (Thinking) After that I have to find the approximation for the TSP-Tour through the NEAREST-NEIGHBOR and then through the NEAREST-INSERTION with starting point $(0,0)$.

Do we get the following result through the NEAREST-NEIGHBOR?
$$(0,0)\rightarrow (1,0) \rightarrow (2,0) \rightarrow \dots \rightarrow (100,0)\rightarrow (100,2) \rightarrow (99,2) \rightarrow \dots \rightarrow (1,2) \rightarrow (0,2) \rightarrow (103,0) \rightarrow (0,0)$$
(Wondering)

Is the length of this Tour equal to $410$ ? (Wondering) The NEAREST-INSERTION algorithm is the following:

T <- {1} 
while |T|<n do 
   j <- vertex with minimal d(T,j), j notin T 
   insert j with minimal cost into T 
return T

So, we have the following:
T={(0,0)}
j=(1,0)
T={(0,0), (1,0)}
...
T={(0,0), (1,0), ... , (i,0), ... , (100,0), (100,2), ... , (j,2), ... , (1,2), (0,0)}
or not? (Wondering)

So, do we get the same result with both approximations? (Wondering)