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?