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?
>>8029203
The point is that there is no way to solve it other than by brute force
>>8029212
so whats the problem with using brute force? does it really take that long to solve when using a lot of destinations?
>>8029220
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
>>8029203
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.
>>8029203
A* or dijkstra now fuck off
>>8029220
>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
>>8029233
> 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.
>>8029243
what is that
>>8029233
>If your list of places is billions long, then yes.
You don't really need billions for this to be a problem,
Total solutions are (n-1)!/2
So if n = 100, there are 4.6663 E+155 solutions.
If n = 20, there are 608,225,502,044,160 solutions.
n=billions is a pipe dream.
Also: if someone invented a non-brute-force solution, it might go a long way towards solving P vs NP.
>>8029303
which is?
>>8029308
The fast multipole method used in physics to speed up simulations https://en.wikipedia.org/wiki/Fast_multipole_method we could pretend cities close to each other to attract each other stronger than those far away (like gravity).
>>8029314
Make it yourself!
The algorithms that solve TSP problems are generally very easy to implement and program.
If you can make out the idea from that link, go ahead try and see what you come up with.
You don't even need to be a good programmer, you can do it in MALTAB probably if you formulate your solution well.
>>8029319
Yes I suppose it's about time I take some swings at it while I'm in that mode of thinking.
>>8029203
Are you just putting words together without knowing their meaning?
>solve the traveling salesman algorithm efficiently?
>brute force it
>>8029448
everyone else knew what i meant
>>8030144
The time complexity of a naive TTSM approach (AKA "brute-forcing it") is O(n!). So if you have a million spots, you have to do 1000000! passes.
>>8029203
"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.
>>8029233
More like anything past n=20 or so
>>8030155
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
>>8030171
https://people.sc.fsu.edu/~jburkardt/c_src/tsp_brute/tsp_brute.c
>>8029236
dijkstra's can't really solve the travelling salesman problem though
it can return a pretty reasonable answer, but not the true solution
>>8030171
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: https://en.wikipedia.org/wiki/Backtracking
>>8030237
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.
>>8030262
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.
>>8029203
theta(n!)
that's why you can't just "brute force it quickly"
>>8029248
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.
>>8030303
I just figured out how to do it
>>8029203
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.
>>8029203
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?
>>8030412
>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
>>8030502
Let's see a cute little kindergartner girl get the optimal route between 1000 cities then!
>>8030144
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.
>>8030504
>is so mentally decent that he doesn't know the difference between elementary and kindergarten.
>Mathematicians
>>8030522
>mentally decent
>>8030522
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.
>>8030532
>You mean deficient? Because that describes you more than me.
Wife with automobile correct is marsh sometimes.
>>8030502
2/10
>>8030502
>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
>>8030502
what the fuck is this supposed to be
>>8030583
>He can't see the clear riemannian manifold
brainlet detected
>>8030583
looks like danny davito hiding behind a very flamboyant fox
>>8030313
Then by all means publish and reap your rewards! I'll be waiting on the edge of my seat to read your paper.
>>8030583
>in charge of not being trolled
>Mathematicians
>>8030619
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
>>8030720
4/25/2016.
The day a random anon solved P vs NP problem on /sci/
>>8030737
I know, right? Jesus, why couldn't I have been smart enough to figure that out? I humbly bow to anon's brilliance.
>>8030720
Hello, I am from /b/. Your post means nothing to me, and I think you make up big words. Good day.
>>8030720
>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
>>8030516
wasnt trying to sound smart? i used what i thought were basic terms but apparently werent the right ones
>>8030255
>>8030155
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
>>8030854
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.
>>8029203
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
>>8029235
>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
>>8031156
>They have algorithms that are 99+% which is good enough
[citation needed]
