3 ms·
Neural networks are not magic. You can't solve the travelling salesman problem in polynomial time just by throwing machine learning at it... On a mathematical
by dagss 8y ago
Neural networks are not magic.
You can't solve the travelling salesman problem in polynomial time just by throwing machine learning at it...
On a mathematical level you can prove that machine learning will do a bad job for certain things, and this is what the parent talked about.
- amluto 8y agoBut you can solve TSP pretty well with a TSP solver. I’d be impressed if a neural network did that well. But maybe it’s possible.
- currymj 8y agoSee Dai et al, "Learning Combinatorial Optimization Algorithms Over Graphs", experiment section A.1.3 "Traveling Salesman Problem". https://www.cc.gatech.edu/~lsong/papers/arxiv_rl_combopt.pdf https://www.cc.gatech.edu/~lsong/papers/arxiv_rl_combopt.pdf It does at least respectably well against the Concorde TSP solver although (unsurprisingly) doesn't beat it. Note that this also isn't a neural network that just maps a graph to a TSP solution; instead, the neural network function is a heuristic that guides the greedy construction of a solution one vertex at a time.
- lmm 8y agoIs there any reason to believe generating 2D video with the properties that a recording of a 3D world has is a difficult mathematical problem though?