## Theoretical problem about traveler salesman

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Theoretical problem about traveler salesman

Hi,

Imagine that someone coming from another planet smartest than all human beings come and tell you :
Here is a map with 10.000 citires. The shortest path is equal to some distance let us say 25321 kilometers.
Now you have the map with the matrix of distances between cities and you have to find the path. I mean the order of visit of each city and coming back to the starting point.
How the complexity of such hard problem will be affected?
Will it be easy to find the path knowing the target :25312 kilometers or will it change nothing to the algorithmic complexity of the problem?
What algorithm will you apply then knowing the exact length of the shortest path?

Thank you for any comment.

notzeb
Without Warning
Posts: 629
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

### Re: Theoretical problem about traveler salesman

The problem doesn't get much easier when you know the exact length of the shortest path ahead of time. You can prove this by imagining you had a magic box (aka oracle) which could solve the problem if it was told ahead of time the exact length of the shortest path, and then use the magic box to solve problems where you aren't told the length of the shortest path. A straightforward method would be to just give the box every possible length as a shortest length and see when it starts working, but if you are clever you could probably use some sort of binary search variant to speed things up (rounding distances between cities to nice round numbers, maybe).

A similar, but trickier, argument can be used to show that solving a puzzle doesn't become too much easier if you are told ahead of time that there is exactly one solution (as is common with Sudoku).
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Theoretical problem about traveler salesman

notzeb wrote:The problem doesn't get much easier when you know the exact length of the shortest path ahead of time. You can prove this by imagining you had a magic box (aka oracle) which could solve the problem if it was told ahead of time the exact length of the shortest path, and then use the magic box to solve problems where you aren't told the length of the shortest path. A straightforward method would be to just give the box every possible length as a shortest length and see when it starts working, but if you are clever you could probably use some sort of binary search variant to speed things up (rounding distances between cities to nice round numbers, maybe).

A similar, but trickier, argument can be used to show that solving a puzzle doesn't become too much easier if you are told ahead of time that there is exactly one solution (as is common with Sudoku).

In some unusual cases there is information that you can glean from the known path length. If all but one of the edge lengths are integers, then you can easily tell whether the non-integer edge is included in the solution or not. Similarly, if they are all integers, you can work modulo n for various n and maybe get some information that way if you are lucky. Regardless, knowing the path length lets you turn this travelling salesman problem into a subset sum problem. Unfortunately that is still an NP-hard problem in general, but the particular instance might be easier than the corresponding travelling salesman problem. If the subset sum problem has a unique solution, you can immediately recover the original travelling salesman problem from it. If not, you have some more work to do to find which solution corresponds to a looped path.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Theoretical problem about traveler salesman

Assuming that we know the "exact length of the shortest path ahead of time" here is an idea of lagorithm solving the problem quickly.
The path is hamiltonian : we start from one city and we come back to it visiting only once the other cities.
So we can get in some city A coming from a city B and then leaving it to another city C.
For each city we compute what I call the GIGO (Get in get out).
GIGO (A) = distance from city B to city A + distance from city A to city C.

For n cities we will have to compute n*(n-1)*(n-2) GIGO values.
For each city we are going to have (n-1)*(n-2) values.
For each city we sort those values from the lowest to the largest.
We pick the lowest value (noted min GIGO(X) where X is the city name).
At the end we will have n selected "bridges" linking 3 cities.
We color in red all the selected "bridges" in our map.
If all the bridges form a hamiltonian path then for sure it will be the shortest path. We have to prove anyway mathematically.
If not then we will have to find some bridge to complete our hamiltonian path such as the sum of all distances will be equal to the shortest path.
What I want to know is the probability that those selected bridges form exactly a hamiltonian path no matter what the network of cities? We can do it for n not large (allowing a use of brute force to compute exactly the shortest path) and simulating random points representing the cities.
Some configurations of cities will not give 100% hamiltonian path but less.
Brute force will be easy for 5<=n<=8 (?)
What I presented above is an idea of algorithm. So I did not estimate its complexity nor did I implemented it.

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

### Re: Theoretical problem about traveler salesman

My intuition tells me this problem is still NP hard but I'm not completely convinced yet.

Notzeb's algorithm gives you a TSP PTAS, but i'm not sure if it's possible to select your guesses so that you'll find the optimal solution in polynomial time.

Jaap mentions subset sum but I don't think exactly reduces. Formally, Subset sum asks whether such a subset exists whereas here, we already know the subset exists and we want to find it, which is a different problem.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Theoretical problem about traveler salesman

Thank you.
Because I still think that if we know ahead of time the shortest path the complexity will change drastically.
Someone has to convince of the contrary.

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

### Re: Theoretical problem about traveler salesman

If your algorithm always runs in polynomial time, it does not work.

Suppose your algorithm runs in polynomial time given G and cost C.

To solve TSP(H,K) in polynomial time, feed H and K into your algorithm.
Suppose the answer to TSP(H,K) is yes (there does exist such a path). Then this algorithm will return that path in polynomial time.
Suppose the answer to TSP(H,K) is no. Now you're using your algorithm to find the shortest TSP with cost K when one doesn't exist.

Then the worst that could happen is the algorithm crashes or takes more than polynomial time.
Simply have the algorithm terminate once it has reached it your polynomial time bound.
You now know that TSP(H,K) is no in polynomial time.

Therefore TSP, which is NP hard, can be reduced to finding the TSP with known cost.

edit: this doesn't actually work because TSP asks if there's any path with cost less than or equal to K, not exactly K.

edit edit: Actually I think notzeb's algorithm works if distances are all integers as is how it usually is. Therefore, finding a TSP tour given the distance is still NP-hard.