Jump to content

Diffrence between ATSP and TSP


Greenmachine17

Recommended Posts

Hello!


this might be a slightly foolish question, but what is the exact diffrence in solving TSP and ATSP.


I've always thought that in ATSP you need to compute the way back(since the input matrix is assymetric).


So the path for ATSP is twice as long as TSP. Am i correct?


I do understand this is a very simple question, but doubt has gotten into my mind. Thank you.


Link to comment
Share on other sites

I assume travelling salesman problem

https://en.wikipedia.org/wiki/Travelling_salesman_problem#Asymmetric_TSP

 

 

this might be a slightly foolish question, but what is the exact diffrence in solving TSP and ATSP.

 

The difference is that the distance between nodes of the graph depends on the direction you travel.

 

So the distance from A to B is not the same as the distance from B to A.


This obviously makes it harder to find the shortest route.

Link to comment
Share on other sites

You can't really plan ahead on these things. I might take the motorway from a to b then find after I have done my shopping that the motorway b to a is flooded. Google maps doesn't chart the next shortest route automatically because it doesn't know the road flooded.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.