0
$\begingroup$

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? enter image description here

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?

Improve this question
$\endgroup$
  • $\begingroup$ The distance is 0,1,2 or greater, whatever the distance function you gave returns. The distance from (13,0) to (10,2) is $|13-10| + |0-2| = 5$. $\endgroup$ – adrianN Jul 27 '16 at 10:22
  • $\begingroup$ The distance is 0 when we stay at the same point, 1 when we go one point to the right, 2 when we go one point up, and greater when we go to an other point? @adrianN $\endgroup$ – Mary Star Jul 27 '16 at 10:24
  • 3
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Tom van der Zanden Jul 27 '16 at 10:51
  • 3
    $\begingroup$ You're the one asking the question, so you are supposed to tell us whether we can go diagonally... How could we know what you mean by your question? I don't think it matters, because you're using the Manhattan distance. $\endgroup$ – Tom van der Zanden Jul 27 '16 at 10:53
  • 1
    $\begingroup$ @MaryStar for TSP problems it is common to assume that you can go from any point to any point, but you need to ask the person who gave you the problem. $\endgroup$ – adrianN Jul 27 '16 at 10:55
2
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you for your answer!! Is the optimal solution unique? Also could you take a look at my edit part? $\endgroup$ – Mary Star Jul 28 '16 at 3:15
1
$\begingroup$

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)).

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you for your answer!! Is the optimal solution unique? Also could you take a look at my edit part? $\endgroup$ – Mary Star Jul 28 '16 at 3:15

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