traveling salesman problem

[borealiss]

is there only one known method of solving this problem by brute force? or does a polynomial solution exist? the only solution that i know of is by brute force computation thats O(n!). is there another improvement on this?

 

[CTho9305]

i'll pay you if you find a polynomial solution

if a polynomial solution DOES exist, then P=NP and all current encryption schemes apparently go out the window.

 

[Moohooya]

Hey, whatever he pays you, I'll pay you twice as much, and throw in a vacation for two to Morocco.

Brute force is as good as it gets. However depending on the exact problem, huristics can perhaps be used to narrow the problem. Some huristics guarante that they do not remove the solution, while others are faster but may remove the best solution and leave you with an inferior one. Depends on what your needs are.

 

[Shalmanese]

Spelt Heuristics

Anyway, Brute force is for worst case scenarios, there are many optimisations

 

[borealiss]

if i figured out a solution to this, i'd probably be a millionaire. and about the optimizations for this problem, what type of optimizations? machine/application specific? or are they just optimizations to divy up the brute force approach better, but only having the problem remain brute force in nature regardless? these are the only optimizations i know of.

 

[Turkey]

A class I was in did a project with this... basically you use a genetic algorithm with the proper parameters and the computation time is dramatically reduced, but there's a risk you don't get the optimal solution. But if you use the genetic algorithm solution method enough times, eventually statistically there will be a high percentage you will find the optimal solution.

 

[Shalmanese]

Baiscally, for some permutations, its pretty freakin obvious what the solution is so you dont need to go through every step, while I am not aware of what optimisations are out for travelling salesman, I konw there are NP problems which can, with the use of very good optimisations, be reduced 4-5 orders of magnitude in computation size.

 

[MustPost]

I think I read somewhere about theoreticly using DNA computers to sole TS problem more efficiently, but I don't know the specifics.

 

[Shalmanese]

<< I think I read somewhere about theoreticly using DNA computers to sole TS problem more efficiently, but I don't know the specifics. >>



Ahh, that, basically it utilises massive parralelism. Each DNA strand is encoded with a random "path" and then certain enzymes are put in to cull the DNA with the least esirable paths. Eventually, you get the shortest path. Just imagine it as 1 billion computers working on the same problem.

 

[m0ti]

Yup, a genetic algorithm is definitely the way to go, though ant-colony-optimizations are equally good. While they guarantee an optimal solution, statistically speaking, if you run it several times you will get the optimal solution with a high probability as was already pointed out. Actually, for genetic algorithms, it's one of the more typical examples since it's very straight forward to code (link). That site actually has a pretty good intro to GA's. The whole site (it's framed hence the link to only a single frame) is here.

Here's one for an ant-based approach: link

 

[Locutus4657]

Build your self a fairly large q-bit quantom computer and that's your solution... There is no brute force way of doing this... It's too easy to make n too big for even the fastest super computer.

Carlo



<< is there only one known method of solving this problem by brute force? or does a polynomial solution exist? the only solution that i know of is by brute force computation thats O(n!). is there another improvement on this? >>

 

[Zuidera]

thinking of a solution

In terms of a random dispersal of cities eg shotgun scatter pattern.

I would suggest spirals (ala concentric circles) the descision to decide whether to complete the outer circle first or zig zag between two bordering circles (or a section of them) would not be that hard to figure out.

Remembering that as you add more cities you are more likely to end up where there will be more than one solution that will yield the same distance to travel between all cities. This in itself means that you have to examanine just about every possibility in case it is shorted than the previous route.

Rejecting this and setting a maximum distance will allow you to quickly zero onto range of probable values, which may or may not aid your calculations.

Even if you could solve the traveling saleman problem by an equation that would not render all / most / any encryption scheme redundant because you would still have to figure out an equation to break those schemes which could be difficult as they tend to like using RND numbers in their encoding.

ciao
Zuidera

 

[Carceri]

<< if a polynomial solution DOES exist, then P=NP and all current encryption schemes apparently go out the window. >>


No, most conventional encryption schemes won't be affected by a polynomial solution to NP complete problems.



<< I think I read somewhere about theoreticly using DNA computers to sole TS problem more efficiently >>


Yes, but to set up enough DNA molecules to do this you need to use exponential time in the problem size. For large enough problems DNA computing is still infeasible



<< Build your self a fairly large q-bit quantom computer and that's your solution >>


If you can do that you'll be just as famous as if you prove that P=NP (or the opposite). Quantum computers can't solve NP complete problems in less than exponential time. Although they can reduce the computation time significantly for some NP complete problems, they still have to give up on sufficiently large instances of the problem. There exists a provable lower bound on the time needed to solve a NP complete problem on a quantum computer, which is the squareroot of the time it would take to brute force the problem on a conventional computer.

Evolutionary algorithms are the best for very large instances of the problem, but you can never be sure to get the optimal solution. There are optimizations where you get the correct answer with probability 1, but they are not very efficient (since they still require exponential time in the problem size to solve)

 

[tweakmm]

::whoosh::
that was the sound of this post going waaaaay over my head

 

[RagManX]

Like others have said, no way to get the optimal solution other than brute force, and as you know, that can take a weeeee bit longer than you'd want to wait, for a modest sized problem set. There are some solutions that are known to have a high success rate for finding 'near optimal' solutions that are much faster than O(n!), but all of them can be tricked with odd data sets, and none of them consistenly generates the near optimal solutions. They tend to rely on multiple runs to get close. Sorry I can't be more specific, but I haven't looked into this problem in years, so my recall of the attempts to improve the speed to solution is limited. I'm pretty sure one of Knuth's _Art of Computer Programming_ books has info on this (volume 3, I think). Might want to hit the local bookstore and see if you can find anything.

RagManX

 

[Carceri]

Here are some documents we used in a course on these subjects. Not all are related to the TSP, but I hope they can be useful anyway.

Satisfiability is probably the most fameous NP-Complete problem (at least it was the first discovered) and really worth studying to get a feel for NP-Completeness and how to optimize these problems

Algorithms for satisfiability

Approximation algorithms describes a group of algorithms that does not nessesarily yield an optimal solution, but are a lot faster

Approximation algorithms

We used a lot of other interesting material about techniques such as Local Search, Heuristics and Evolutionary Algorithms, but unfortunately that's not available electronically so the links above will have to do

 

[CSoup]

There are optimal algorithms that have lower complexity than the O(n!) of pure brute force. One algorithm I know of has running time of O(n^2 * 2^n). This one uses dynamic programming to reduce the amount of overlapping work that is redone over the search space. There are likely other algorithms that have < O(n!) running time.

 

[kulki]

how is the travelling salesman problem used in encryption?

 

[CTho9305]

<< how is the travelling salesman problem used in encryption? >>


it isn't directly.... but there is some way to convert every NP problem into the other types. if you can solve one, you can solve them all.

 

[Carceri]

<< it isn't directly.... but there is some way to convert every NP problem into the other types. if you can solve one, you can solve them all. >>



To be more precise: You can reduce every NP-Complete (and easier) problem to any NP complete problem you might want. You cannot, however, reduce an NP-Complete problem to a problem in NP that is not NP-Complete.

An example: Lets look at factoring integers and the travelling salesman problem.

TSP is NP-Complete
Factoring is in NP, but not NP-Complete

You can solve the factoring problem by solving the TSP problem since factoring can be "converted" to TSP. Hence solving TSP efficiently would give us an efficient method for factoring integers and breaking the RSA.

However, finding an efficient way to factor an integer would not lead us to an efficient soution to the TSP.

Edit: I'm assuming that P != NP

 

[Locutus4657]

A GA is such an algorithm. What this type of algorithm does is generate a random pool of "chromosomes" (usually just a bit string) then merge 2 pairs of bit strings (like genetics) and sometimes (though some GA people like my advisor would say it's not neccesary) mutate a chromosome.



<< Like others have said, no way to get the optimal solution other than brute force, and as you know, that can take a weeeee bit longer than you'd want to wait, for a modest sized problem set. There are some solutions that are known to have a high success rate for finding 'near optimal' solutions that are much faster than O(n!), but all of them can be tricked with odd data sets, and none of them consistenly generates the near optimal solutions. They tend to rely on multiple runs to get close. Sorry I can't be more specific, but I haven't looked into this problem in years, so my recall of the attempts to improve the speed to solution is limited. I'm pretty sure one of Knuth's _Art of Computer Programming_ books has info on this (volume 3, I think). Might want to hit the local bookstore and see if you can find anything.

RagManX >>