a variation on the traveling salesmen problem
I’m thinking about a variation of the traveling salesmen problem called the Euclidean traveling salesmen problem. In it the distances between the cities are a set of straight, coplanar lines. I’m also only concerned with a set of complete cities (so there is a road between every city)
Given a set of such distances my fist task might be to check that distances meet the geometric requirements for a Euclidean TSP.
If there are n cities there are n(n-1)/2 roads. But, how much work will it take to find out if a set of distances between cities is Euclidean?
If we have only one city no check is needed. With two cities no check is needed … but with three we need to check that triangle inequality is not violated.
The fourth city will require some kind of verification using the distance formula. There will be two possible locations for the 4th city.
The addition of a 5th city adds 4 new edges and each must be checked.
Here is a table of what will happen:
Vertices ---edges---checks
1-------------0----------0
2-------------1----------0
3-------------3----------1
4-------------6----------2
5-------------10----------6
6-------------15----------10
7-------------21----------15
8-------------28----------21
9-------------36----------28
At this point I want to stop and ask if my thinking so far makes sense?
The progression of these numbers seems to be the same as the number of edges, but for some reason it doesn’t start out the same way. Should I be concerned about that?
Given a set of such distances my fist task might be to check that distances meet the geometric requirements for a Euclidean TSP.
If there are n cities there are n(n-1)/2 roads. But, how much work will it take to find out if a set of distances between cities is Euclidean?
If we have only one city no check is needed. With two cities no check is needed … but with three we need to check that triangle inequality is not violated.
The fourth city will require some kind of verification using the distance formula. There will be two possible locations for the 4th city.
The addition of a 5th city adds 4 new edges and each must be checked.
Here is a table of what will happen:
Vertices ---edges---checks
1-------------0----------0
2-------------1----------0
3-------------3----------1
4-------------6----------2
5-------------10----------6
6-------------15----------10
7-------------21----------15
8-------------28----------21
9-------------36----------28
At this point I want to stop and ask if my thinking so far makes sense?
The progression of these numbers seems to be the same as the number of edges, but for some reason it doesn’t start out the same way. Should I be concerned about that?