Traveling Salesman Algorithm

How has nobody come up with a way to solve the traveling salesman algorithm efficiently? Why cant you just use a powerful computer to brute force it quickly?

Other urls found in this thread:

en.wikipedia.org/wiki/Fast_multipole_method
people.sc.fsu.edu/~jburkardt/c_src/tsp_brute/tsp_brute.c
en.wikipedia.org/wiki/Backtracking
twitter.com/AnonBabble

The point is that there is no way to solve it other than by brute force

so whats the problem with using brute force? does it really take that long to solve when using a lot of destinations?

If your list of places is billions long, then yes. Travelling salesman and cities is just an example, its the structure of the question and the inability to solve it without brute force that makes it interesting

What the fuck are you asking?
They have come up with ways to solve the travelling salesman algorithms efficiently, they're called Local Optimization Algorithms, or NLP algorithms - Genetic Algorithm, Particle Swarm Optimization, Simulated Annealing, Ant Colony Optimization... They all solve the TSP problem within a reasonable amount of time.
Do they solve it by finding the global minimum, the absolute best solution? No.
The only way to do it is by checking all possible permutations - by brute forcing it.
The more powerful computer you have, the faster it will solve, but considering the number of points you have in the problem, even the most powerful computer will only help so much.
If you consider that by adding only 1 vertex to the problem, the complexity increases by a factor of O(n!), when you have to many vertices it's idiotic to brute force.
I don't know what you're asking. The solution is easy - brute force, but since you can't find the solution during your own lifetime if you have too many vertices in the problem, you fall back on Local Optimization Algorithms - which work incredibly well if you ask me.

For any real problem that I could formulate as a TSP problem, I would run it through a couple of different algorithms couple of times, playing with parameters, and then just take the best solution I got and seal the deal. I'd even put my signature on it, no matter what the consequences were. That's just the way it is.

A* or dijkstra now fuck off

>want to find shortest path between the 20 starbucks in my town
>have to do literally 2432902008176640000 computations
this is why we dont like brute force

> places is billions
no that is the whole problem mate
50 cities is allready a problem

Quantum computers would find the solution with a single iteration using cone tracing per vertex method.

what is that

"Efficiently" is generally taken to mean polynomial time, ie like O(n^3) or something
meaning that if your input is of size n then it will take in the worst case kn^3 for some constant k that doesn't change with n time to solve. The brute force way to solve TSP is
O(n!) time which is a lot worse and not even remotely polynomial (the polynomial must be fixed and have constant powers).

Even for 100 locations that's 100! which is a 158 digit number.

Keep in mind there are still practical ways to in general solve it without it completely exploding (ie you can solve for more towns doing this *usually* than compared to a naive bruteforce) if you can do things like attach geometric coordinates to the places, but even then there's no known way to get a polynomial time in the worst-case.

Also keep in mind that there are such things like approximation schemes. A k-approximation scheme is an algorithm such that it always returns an answer to within k*opt where opt is the actual optimum. So you see things like 3/2-approximation schemes so if the true shortest path is 200 then it will always return an answer of at most 300 and that can be proven, and these approximation schemes are usually polynomial time (otherwise why bother). I don't know much about actual TSP approximation algorithms or what k would be if there even are any, but I would imagine they would benefit from attaching geometric coordinates instead of just looking at a graph.

More like anything past n=20 or so

Do you know the psudocode for the brute force way? I'd be interested in seeing what the skeleton of an O(n!) algorithm looks like

people.sc.fsu.edu/~jburkardt/c_src/tsp_brute/tsp_brute.c

dijkstra's can't really solve the travelling salesman problem though

it can return a pretty reasonable answer, but not the true solution

An O(n!) naive one would literally just be like:

for each permutation:
if cost < best
update best

However more likely you'd write a backtracking algorithm which would cut off as soon as it realized that even on the path it's considering so far it won't do as well as the best known path so far. Lots of intractable problems are tackled this way.
It's usually done via a recursive call. something like

backtrack(v, visited, cost):
{
visited[u] = true
if all vertices visited, update best if possible

for u in neighborhood of v:
if visited[u] == false and best > cost + weight(v, u):
backtrack(v, visited, cost + weight(v, u))

visited[u] = false
}

as a naive backtrack (or something like that, just writing this in the comment box)
see: en.wikipedia.org/wiki/Backtracking

It can return a pretty reasonable answer? How would you adopt it? I mean, you'd want to visit every single vertex at least once, so...?
I thought about looking at a start vertex then for every other vertex pair doing dijkstra to them and back, but even that won't even get you every vertex. Do you look through all paths P generated by dijkstra and then choose one that maximizes [math]\frac{|P|}{cost(P)}[/math] or some other heuristic, then try and build on that? I'm trying to see how you'd come up with a reasonable approximation scheme using dijkstra but I don't get it, although I only thought about it for less than a minute.

You kinda caught me in a corner.

I do distinctively remember explaining why Dijkstra's can be used to at least approximate a solution to the TSP, but that was a long time ago and I haven't touched the algorithms in almost a year now.

theta(n!)

that's why you can't just "brute force it quickly"

This post kinda says it all. If you can come up with a way to solve TSP in polynomial time, you will be a very wealthy fellow.

I just figured out how to do it

basically, to put it in very simple terms,

there is no way to find *the MOST optimal solution without looking at every single possible path. it's an n! problem. Of course, it can be approximated much more efficiently.

place oats on a table in the relative positions of your cities, and let slime mold have a go at it

hmm...so why wouldn't a greedy approach work for TSP?

>hmm...so why wouldn't a greedy approach work for TSP?

Greedy would take /sic but the shortest is /sci.

>needing to brute force something an elementary kid does on a weekly basis
>Mathematicians

Let's see a cute little kindergartner girl get the optimal route between 1000 cities then!

No. You proposed a solution that indicated you were more interested in sounding smart if you were right than doing even preliminary research on the problem or the terms in your post.

>is so mentally decent that he doesn't know the difference between elementary and kindergarten.
>Mathematicians

>mentally decent

Kindergartner sounds cuter than elementary schooler! Although both are nice...

Also

>mentally decent

You mean deficient? Because that describes you more than me.

Although it's pretty obvious that you're just shitposting.

>You mean deficient? Because that describes you more than me.

Wife with automobile correct is marsh sometimes.

2/10

>let's find the optimal route out of many possible routes
>posts a puzzle with one fixed route

1/10 if bait
please commit sudoku/10 if srs

what the fuck is this supposed to be

>He can't see the clear riemannian manifold

brainlet detected

looks like danny davito hiding behind a very flamboyant fox

Then by all means publish and reap your rewards! I'll be waiting on the edge of my seat to read your paper.

>in charge of not being trolled
>Mathematicians

For every possible number of n, have a subroutine that does it thatcmany number od times, and at the beginning call the currect subroutine based on n. Voilà, polynomial time complexity

4/25/2016.

The day a random user solved P vs NP problem on Veeky Forums

I know, right? Jesus, why couldn't I have been smart enough to figure that out? I humbly bow to user's brilliance.

Hello, I am from /b/. Your post means nothing to me, and I think you make up big words. Good day.

>Voilà

and just like that a millenium prize problem was solved

rest assured i will be on the phone to the clay institute within minutes to register your discovery

>tfw going to sleep every night thinking about Hamiltonian cycles for the last 10 years

want off this ride

wasnt trying to sound smart? i used what i thought were basic terms but apparently werent the right ones

i still cant belive the only way to find the best solution is by brute forcing it. say you had 10 destinations. isnt there a way you could get the distance between any 2 destinations and use that to figure out the best route? i know its not that simple otherwise someone wouldve solved it already

It's a hard problem. It's not even in NP since you can't verify a solution in polynomial time, although it is NP-hard. (so not even in NP-Complete it's so hard).

You have to remember that simply coming up with a Hamilton cycle (cycle with same order as graph - visits every node) in a graph is NP-Complete, and TSP is doing not only that, but finding the shortest Hamilton cycle out of all Hamilton cycles. Even the decision problem of Hamilton cycle ("Does this graph have a Hamilton cycle? Yes or no.") is NP-hard in general. Of course for special classes of graphs you can do it efficiently (proper circular arc graphs (which are equivalent to local transitive tournament orientations of digraphs IIRC) come to mind, but I'm sure there's others), even in low-polynonial time (like O(n^2)).

You might be able to come up with a polynomial approximation scheme that gets a "good enough" solution though.

> isnt there a way you could get the distance between any 2 destinations and use that to figure out the best route?

Well first off, which variant of the TSP are we talking about? When you say distance, do you mean min-distance (ie Dijkstra, or I guess Floyd-warhsall to get all-pairs) in the graph, or are you talking about an embedding of a graph where distances between cities correspond to Euclidean distances? And is it a labelled complete graph, or is the diameter of the graph greater than 1? If you impose enough restrictions on the graph you can get an algorithm for whatever restricted class of graphs that might be polynomial time.

the algorithm that is the only known 100% solution is the brute force algorithm and that takes a lot of time when you have 100+ routes to consider. The purpose of algorithms is to solve real world problems with real world time constraints. They have algorithms that are 99+% which is good enough

>solve
>Genetic... Annealing..
AI doesn't solve squat, it makes guesses that can't be proved rigorously by anyone ever.

Saying that you can "solve" an NP-complete problem is dangerous because you'll give stupid or uneducated people the wrong idea.

You should say that "we can derive a reasonable approximation within polynomial time", or "we can get the answer some percentage of the time", or "we can program this AI to solve it but we have no way to prove that it can actually do it with any degree of certainty

>They have algorithms that are 99+% which is good enough
[citation needed]

P vs NP solution is under the assumption that there is no parallel processing. The algorithmic complexity is measured in number of steps complete, not actual seconds of run time. Splitting the steps into subroutines doesn't eliminate steps or step growth