Find the optimal way [closed]

Question

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 $23$ points with the following coordinates: $$(i,0), \text{ for } i=0, 1, \dots , 10, \\ (i,2), \text{ for } i=0, 1, \dots , 10, \\ (13, 0)$$

I want to give the optimal TSP-Tour.

We have the following grid, or not?

To find the optimal TSP-Tour (without the approximation-algorithms) from which point do we start? From which point we want?

If we choose one point to start, lets 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)$ ?

Or is this not the correct way to find the optimal TSP-Tour?

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?

If this is true, is the optimal TSP-Tour the following? $$(0,0)\rightarrow (1,0) \rightarrow (2,0) \rightarrow \dots \rightarrow (10,0)\rightarrow (13,0)\rightarrow (10,2) \rightarrow (9,2) \rightarrow \dots \rightarrow (1,2) \rightarrow (0,2) \rightarrow (0,0)$$ But how do we get from the point $(13,0)$ to the point $(10,2)$ ?

$$$$

EDIT:

I have to find also 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 (10,0)\rightarrow (10,2) \rightarrow (9,2) \rightarrow \dots \rightarrow (1,2) \rightarrow (0,2) \rightarrow (13,0) \rightarrow (0,0)$$

So is the length of this Tour equal to $10+2+10+15+13=50$ ?

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?

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

Answer 1

Your question is not fully clear to me,

however if it boils down to, is the tour that you propose the optimal one, the answer is yes.

You can easily prove it:

Your tour has a total distance of 30. If you would consider the problem of finding the shortest tour where the only points are (0,2) and (13,0) then the answer is trivially (0,2) -> (13,0) -> (0,2) which also has a total distance of 30. Since the Manhattan distance respect the triangle inequality, then you know that the tour traversing 23 points including (0,2) and (13,0) has a distance greater or equal to 30. Since your tour has a distance of 30 it is optimal.

Answer 2

You can easily find a path that is a valid path for the problem, and an optimal path for the three locations (0, 0), (13, 0) and (2, 0) which shows immediately that it must be the optimal solution for the problem. (Move from (0, 0) to (13, 0) to (13, 2) to (0, 2) to (0, 0)).