How can we check a solution to the Traveling Salesman Problem

[TakenItSeriously]

Assume that you have discovered a method that can determine a very efficient route for any given set of cities every time, but your not sure if its the most efficient route.

How can we know if the resulting route is the most efficient? i.e. how can we test the method we have discovered to be the solution without actually solving all permutations for every problem?

Is their some formula that produces the minimum distance without giving the route?

[Strange]

As far as I know, the only way of checking it is to test it on small problems where all routes can be generated. Then (because it is an algorithm) you can prove it works for larger cases. And, prove that it still runs in polynomial time.

 

[TakenItSeriously]

I wonder if anyone has created a set of patterns with known solutions that can be used to check a method?

It’s almost like any potential method would never be able to get beyond conjecture.

Edited January 6, 2018 by TakenItSeriously

[Strange]

It would take you a few seconds to generate a sample problem. It would take a few minutes to write a program to generate problems of any size.

[TakenItSeriously]

2 minutes ago, Strange said:

It would take you a few seconds to generate a sample problem. It would take a few minutes to write a program to generate problems of any size.

Not with the correct solution? Otherwise it wouldn’t be np-hard.

[Strange]

1 minute ago, TakenItSeriously said:

Not with the correct solution? Otherwise it wouldn’t be np-hard.

Oh, I see what you mean. Sorry.

[TakenItSeriously]

I think we could use the combin function to get the number of combinations between e.g. 2 of n cities produces c distances 

comb(n,2) = c

That list could be sorted.

Any random route would always require n segments.

But I dont see how the two lists could be correlated. I’m sure there are problems where the most efficient routes do not necessarily include all of the shortest distances. so it wouldn't just be the n shortest distances.

I wonder if it could be the average distance times n.

No, definately not. Any regular polygon like an octagon would show the shortest path between its verticies as the polygon itself, all diagonals would be longer than any side. so in that regards it would be the shortest n distances.

I think the proof has to be embeded in the method, i.e. axiomatically proving that each step is correct.

Edited January 6, 2018 by TakenItSeriously

[studiot]

Since you have posted this in computer science,

There is a valid mathematical method know as 'the method of exhaustion'

The method can even be refined to shorten it.

Which will completely satisfy your question.

Edited January 6, 2018 by studiot

[Strange]

5 minutes ago, studiot said:

There is a valid mathematical method know as 'the method of exhaustion'

Isn’t that for finding area? Not sure how/if it can be applied here. 

27 minutes ago, TakenItSeriously said:

I think the proof has to be embeded in the method, i.e. axiomatically proving that each step is correct.

Yes. You should be able to prove, mathematically, that the algorithm produces the shortest route. 

The implementation can then be tested on some small cases. 

[studiot]

2 minutes ago, Strange said:

Isn’t that for finding area? Not sure how/if it can be applied here. 

The method basically means (in this case since a version is used in many branches of Science)

Compute the time for every possible path.

Identify the minimum.

 

Two points.

I said the algorithm can be refined.

There may be more than one path with the minimum time.

There may be no minimum (all paths have the same length)

[Strange]

1 minute ago, studiot said:

The method basically means (in this case since a version is used in many branches of Science)

Compute the time for every possible path.

Identify the minimum.

OK. So what was discussed in the first two posts. 

[TakenItSeriously]

3 minutes ago, studiot said:

The method basically means (in this case since a version is used in many branches of Science)

Compute the time for every possible path.

Identify the minimum.

 

Two points.

I said the algorithm can be refined.

There may be more than one path with the minimum time.

There may be no minimum (all paths have the same length)

I’ve always been under the impression that the shortest path should always encompas the largest area, but I didn’t know how to prove it. Is that related to your first point? I mean, has someone proven the above hypothesis.

[studiot]

20 minutes ago, TakenItSeriously said:

I’ve always been under the impression that the shortest path should always encompas the largest area, but I didn’t know how to prove it. Is that related to your first point? I mean, has someone proven the above hypothesis.

What do you mean by area?

 

I thought you had come from a programming background.

There is a certain method known as Little's algorithm

https://www.google.co.uk/search?q=little's+algorithm&ie=utf-8&oe=utf-8&client=firefox-b&gfe_rd=cr&dcr=0&ei=k6hQWozZI4X98weZ_oXIBA

But it may be "expensive computationally".

There are (n-1)! possible paths in a network with n nodes.

There are also methods that may well produce the correct path, since the minimum is often (but not always) Hamiltonian.

Since there are also allied network tour 'problems' such as the 'postman problem', it would also be good if you would clarify your question.

[TakenItSeriously]

3 hours ago, studiot said:

What do you mean by area?

The area encompased by any given route.

So one idea I had was that it could be the case that the shortest route would always encompass the largest area out of all routes.

3 hours ago, studiot said:

I thought you had come from a programming background

No, not formerly. In fact I wasnt formerly trained in anything.

My background was officially electrical engineering and my title was Sr Staff System Design Engineer and I was widely considered an expert in High Speed Digital Design though I never took any EE classes. it was a position I earned through my accomplishments in the field.

I may have said that if I had a choice in majors, my first choice would have been Physics because I was a fan of Einstein and his methods especially in his early years. My second choice would have been programming because I was naturally gifted at coding,

I do a lot of codding, though on a periodic bassis. Occasionally for a large project, I might do nothing but coding for several years, but it was nearly all self taught so my knowledge may be eclectic, incomplete, limited in languages, and out of date. 

3 hours ago, studiot said:

There is a certain method known as Little's algorithm

https://www.google.co.uk/search?q=little's+algorithm&ie=utf-8&oe=utf-8&client=firefox-b&gfe_rd=cr&dcr=0&ei=k6hQWozZI4X98weZ_oXIBA

But it may be "expensive computationally".

There are (n-1)! possible paths in a network with n nodes.

There are also methods that may well produce the correct path, since the minimum is often (but not always) Hamiltonian.

Since there are also allied network tour 'problems' such as the 'postman problem', it would also be good if you would clarify your question.

Actually, I think you answered it. I origionally thought their might have been a trivial method to check a potential solution , kind of like problems that are trivial one way, vs difficult the other way, but I guess thats a different class of p vs np. 

For the heuristic? solution, like I had posted a little while back, I was thinking the proof could be handled by proving the steps of the method.

As far as the algorithm for programming, I might choose a different approach from the mactrices that seem to be commonly used, in order to exploit the method I gave.

starting from a linked list of perimeter cities I could optimally insert cities into the linked list one at a time.

The order that the cities are processed in using a loop could be based on their radius to a centroid point (avg. x vs avg. y) So cities would begin in an array ordered by longest r to smallest r. 

Determining where each cities position in the linked list (route list) would be, would be determined by the difference between the line segment on the perimeter and the two new line segments that would replace that segment. then  comparing results for each segment on the perimeter.

However, there should be a way to narrow it down to compare only edges that are closest to the new city being added to the route determined through geometric relationships somehow.

Edited January 6, 2018 by TakenItSeriously

[Strange]

3 hours ago, TakenItSeriously said:

I’ve always been under the impression that the shortest path should always encompas the largest area, but I didn’t know how to prove it.

I would have thought it would be the smallest area. After all, if all the points lie on the convex hull, then that is the shortest route and also the smallest area (that encompasses all the points). 

49 minutes ago, TakenItSeriously said:

Actually, I think you answered it. I origionally thought their might have been a trivial method to check a potential solution , kind of like problems that are trivial one way, vs difficult the other way, but I guess thats a different class of p vs np. 

You should be able to prove that it is the shortest route by showing that swapping each point with any other produces a longer route. Off the top of my head, that seems be polynomial in the number of routes rather than exponential. So it should be quicker to check than generate the route.

[TakenItSeriously]

20 minutes ago, Strange said:

I would have thought it would be the smallest area. After all, if all the points lie on the convex hull, then that is the shortest route and also the smallest area (that encompasses all the points). 

I understand, it’s a very non-intuitive notion.

The easiest example to consider would be the vertices of a regular polygon of n sides. So if a city were located at each vertex, then the most efficient path is the origional polygon which is clearly describing the greatest area.

The same would be true for any irregular polygon with all obtuse angles pointing out from the center which describes a starting perimeter of cities.

As we add inner cities one at a time, you could look at the problem as adding the city by bisecting a perimeter segment  such that the area surrounded by the perimeter is reduced by the least amount.

Also note that as I explain it, it’s basically describing the proof I needed.

I think I have it all done except for the last optimization. I’ll try to rewrite the proof explaining the method, then provide some pseudo code for the algorythm.

This turned out to be a very productive thread.

Edited January 6, 2018 by TakenItSeriously

[Strange]

13 minutes ago, TakenItSeriously said:

The easiest example to consider would be the vertices of a regular polygon of n sides. So if a city were located at each vertex, then the most efficient path is the origional polygon which is clearly describing the greatest area.

This is exactly the case I was describing. The polygon is the convex hull that encloses the points. So I think this hinges on what you mean by the "greatest" area. From my perspective this is the smallest area that includes all the points. One could create a larger polygon that includes all the points but not a smaller one. 

 

[Rob McEachern]

4 hours ago, TakenItSeriously said:

I wonder if anyone has created a set of patterns with known solutions that can be used to check a method?

Are you familiar with TSPLIB: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

[dimreepr]

14 minutes ago, TakenItSeriously said:

I understand, it’s a very non-intuitive notion.

1

Are you describing this? 

[TakenItSeriously]

1 hour ago, Rob McEachern said:

Are you familiar with TSPLIB: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

I don’t think so. that looked like a list of alternative solutions but browsing through them the each seemed to describe something different from my solution.

1 hour ago, dimreepr said:

Are you describing this? 

The ant analogy seems a little bit abstract for describing a TSP solution. For one cities are located in fixed states while ants are communicating in a dynamic state. perhaps they may link up in a network remniscent to a TSP net? I DK. I didnt read the article in that much detail, but in anycase I would think it would have to be more a case of parallel processing while mine is still linear.

Edited January 6, 2018 by TakenItSeriously

[studiot]

I still don't understand you reference to area.

Particularly if minimum time is required.

Can you please demonstrate it with reference to the following diagram.

Can you also show any difference between starting at A,B,C,D or E?

 

Just list the node sequence will do.

[TakenItSeriously]

1 hour ago, studiot said:

I still don't understand you reference to area.

Particularly if minimum time is required.

Can you please demonstrate it with reference to the following diagram.

Can you also show any difference between starting at A,B,C,D or E?

 

Just list the node sequence will do.

I see where the confusion is comeing from. You need to treat the problem as a loop as the origional problem is stated, as in the salesman starts from his home city and returns back to his home city.

For the proplem as you showed it, there are four equally optimal paths due to symmetry so one example loop would be like: 

A, B, C, D, E, A

By the way I am treating it as the shortest distance not time which is really the same thing but area makes more sense in the context of its distance.

I had a paper route as a child so I might have taken the loop part for granted when describing the problem, sorry for the confusion.

 

edit to add:(late update)

I should meantion that the starting/ending city still doesnt matter though the way I wrote iit kind of implies it does. Its just the nature of loops because to show it literally, there would only be one city A designated, but it would have to be written in a circular fashion. I use the designation twice to show it needs to be connected to E as well as B.

But you could treate the problem as

C, D, E, A, B, C

Just as easily as

A, B, C, D, E, A

as you sugested in your example.

Edited January 6, 2018 by TakenItSeriously

[TakenItSeriously]

One more item to add. 

when we are talking about the complete state solution when treating the route as an open route you had correctly expressed it as (n-1)!

However by treating it as a loop:

• first we need to get rid of the -1 because a loop has the same number of segments as their are cities
• we need to divide by 2 because their are two directions which is redundant 
• we need to divide by n because while you can designate any city as the starting city, permutations would count all starting states as different when they only need to count once. so:

number of different combinations = n!/(2n)

 

I’m sure you’re aware of this but for others who may be reading this, note that I wrote combinations instead of permutations. Combinations is like permutations only after we ignore the redundancies which isn’t required in this situation.

(quick review of the combin function for calculating distances)

If you want to know the number of distances between any pair of city’s that we need to calculate for a complete solution method we use the combin function, which has a proper expression that I cant recall and couldnt write anyway because I dont have access to math syntax using the iPad. but I always use the combin function provided by Excel written as: combin(n,m) or how many combinations of m objects are possible from a total of n objects .

where

n is the total number of cities

m = 2  because distances are based on city pairs. 

example:

for a total of 4 cities, the number of possible city pair combinations (distances) = 6

combin(4,2) = 6 

(A,B) (B,C) (D,A) (B,D) (C,A) (C,D)

those are again combinations.

permutations would be double the number because then order would count  i.e. (A,B) is redundant to (B,A)

if you dont have the combin function its expressed as 

combine(x,y) = x!/y!(x-y)!

Or it may be easier to remember as the first y factors of x!

so combin(6,3) = 6*5*4

 

Edited January 6, 2018 by TakenItSeriously

[TakenItSeriously]

1 hour ago, TakenItSeriously said:

One more item to add. 

when we are talking about the complete state solution when treating the route as an open route you had correctly expressed it as (n-1)!

However by treating it as a loop:

• first we need to get rid of the -1 because a loop has the same number of segments as their are cities
• we need to divide by 2 because their are two directions which is redundant 
• we need to divide by n because while you can designate any city as the starting city, permutations would count all starting states as different when they only need to count once. so:

number of different combinations = n!/(2n)

 

I’m sure you’re aware of this but for others who may be reading this, note that I wrote combinations instead of permutations. Combinations is like permutations only after we ignore the redundancies which isn’t required in this situation.

(quick review of the combin function for calculating distances)

If you want to know the number of distances between any pair of city’s that we need to calculate for a complete solution method we use the combin function, which has a proper expression that I cant recall and couldnt write anyway because I dont have access to math syntax using the iPad. but I always use the combin function provided by Excel written as: combin(n,m) or how many combinations of m objects are possible from a total of n objects .

where

n is the total number of cities

m = 2  because distances are based on city pairs. 

example:

for a total of 4 cities, the number of possible city pair combinations (distances) = 6

combin(4,2) = 6 

(A,B) (B,C) (D,A) (B,D) (C,A) (C,D)

those are again combinations.

permutations would be double the number because then order would count  i.e. (A,B) is redundant to (B,A)

if you dont have the combin function its expressed as 

combine(x,y) = x!/y!(x-y)!

Or it may be easier to remember as the first y factors of x!

so combin(6,3) = 6*5*4

 

correction

it may be easier to remember as the first y factors of x!/y!

combin(6,3) = 6*5*4/3*2*1 

possible permutations of y given a total of x is the first y factors of x!

perm(6,3) = 6*5*4

 

Edited January 6, 2018 by TakenItSeriously

[studiot]

Thanks, but you haven't explained the area question.

Further suppose we consider the path ABACADAEA.

This encloses zero area, althoug it is not the shortest.

Again suppose we remove C, D and E so we only have AB.

How much area does the optimal solution enclose?

And since n now = 2, your formula becomes

No of paths  = 2!/2*2 = one half.

What is one half of a path?

My formula, by contrast reads number of paths = (2 - 1)! = 1! = 1 path, which I think to be correct.