Traveling Salesman Algorithm

>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.

anyone tried a multipole kind of approach?

which is?

The fast multipole method used in physics to speed up simulations 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).

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.

Well then there you go

Yes I suppose it's about time I take some swings at it while I'm in that mode of thinking.

Are you just putting words together without knowing their meaning?
>solve the traveling salesman algorithm efficiently?
>brute force it

everyone else knew what i meant

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.

"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