If you want to brute force the travelling salesman problem and you have 15 different cities, will this take 15^15 instruction cycles? Meaning it would take an intel i7 which can do 82,300 million instructions per second over 5 million seconds to compute?
i.e. (15^15)/(82,300*10^6)
Other urls found in this thread:
wolframalpha.com
math.uwaterloo.ca
twitter.com
...
actually my thread is more computer science related than 90% of the threads here
>Sup Forumsee
>computer science
thats why you use a gpu farm
computer science is technology at its most fundamental. you dont want to go too deep, eh? does it make you feel uncomfortable?
or The only Sup Forums thing in this post is the computational speed of an i7, which may or may not even be right since you didn't specify the model. The rest is mathematics.
>n^n
>not n!
Retard. Now go away.
>computer science is technology at its most fundamental
lel
Electronical engineering is technology at its most fundamental
Fuck off. This is not a tech support thread and I seriously doubt it's homework.
Those aren't the minimum conditions for a post to be welcome here. Sup Forums spam is neither tech support nor homework as well, but it's still off-topic garbage.
oh, well that means it will only take 15 seconds
>implying ttp is O(n^n)
topkek, kiddo
you deserve all the trash you get
i realized that just before this guy posted
>brute force
screw this, heuristics are good enough
The posts I replied to are falsely directing him to /wsr/ because they somehow think this is a tech support thread. I suppose it could be homework, but it reads more like someone asking a question about computer science.
isn't brute force quicker to write?
heuristics provide 1.5 times longer solution worse case scenario
Hello OP, I will help you.
TL;DR: you're wrong.
Bruteforcing TSP (normally) means that you will evaluate the length of each unique path and check which one is the shortest. Since the path will start and stop in the same node, you can pick any node as your first node. From the first node you will have to try out each of the 14 remaining nodes as the second node. From each second node you will have to try out each of the 13 remaining nodes as the third node, and so on. This means that you will have to try 14*13*12*11*...*1 = 14! unique ways, which means that the problem is in O(n!). 14! is much less than 15^15.
If you want to follow up this post by asking "then, will it take 14! instruction cycles to compute?", you would still be wrong. You can't possibly expect to compute and evaluate a potential path in a single instruction cycle. The exact amount of instructions depends on your implementation.
>isn't brute force quicker to write?
No shit.
>he doesn't use his time machine to solve NP-hard problems in constant time
kek you fucked up. it's 15! not 14!
it would only be 14! if your starting point was known
The starting point doesn't matter since the length of the cycle a-b-c-d-e-...-a doesn't change, independently of the starting point.
Kek no its not, that's quantum physics
not true
perform a delaunay triangulation in nlogn and work from there
given the delaunay will orient any quad the best way for the salesman problem, it should be a good start to solve the problem, no?
TSP is N!, but has been "solved" using heuristics and approximations for a subset of N to the point that is useful. These approaches are the ones in uses by computation engines like wolfram-alpha.
Good, now divide N! by the number of Ryzen CPUs you have.
Traveling salesman considered deprecated we just use the Internet nowadays
A better question is, given TSP is NP-Hard and SAT is NP-Complete, how you would convert it to a SAT problem.
>2017
>Computers are beating people at Go
>Still can't solve a fucking travelling problem.
It's nice to know when Skynet happens, all we need to do is give it google earth and ask it "where's your Neural Net now?".
make a population of random paths.
like 100 of them.
evaluate them.
take 2 among the best (~randomly)
make those 2 reproduce.
For example, only take two three random chains from one : abcdef + beacfd -> take ab*d** from the first, complete with the second = abedcf
you now have a population of 101.
evaluate the new born.
Kill the worst of the population.
Repeat for 5minute.
The best of the population should be close to the best solution (if not the best)
different class of problems. SAT is a decision problem (answer yes or no), TSP is not. You can ask if there is a cycle through all the cities with length
can you fuck off
I'd rather this thread over another pointless "what phone should I buy gyuise??" thread
Or fucking amd nvidia consolewar bullshit
go fuck yourself you are the reason Sup Forums is shit
what if I can do more than one factorial per instruction cycle huh
What about using a monte carlo algorithm to aproximate the best solution?