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

  • Thread starter Thread starter mathmari
  • Start date Start date
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 

Attachments

  • tsp.png
    tsp.png
    1.3 KB · Views: 97
Last edited by a moderator:
Physics news on Phys.org
mathmari said:
Hey! :o

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)
 
I like Serena said:
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)
I like Serena said:
in this particular case your solution will be optimal.

How do we know that? (Wondering)
 

Attachments

  • tsp.png
    tsp.png
    2 KB · Views: 88
  • tsp.png
    tsp.png
    4.4 KB · Views: 98
mathmari said:
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)
 
I like Serena said:
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:
Code:
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)
 
Last edited by a moderator:
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.
Back
Top