4 ms·
What I find interesting about the knapsack problem, and the traveling salesman problem as well, is that they're fast to satisfy, but incredibly time-consuming t
by samatman 7y ago
What I find interesting about the knapsack problem, and the traveling salesman problem as well, is that they're fast to satisfy, but incredibly time-consuming to solve.
Once upon a time, I had a 4x8 sheet of small plastic parts to route out on a ShopBot. The naive layout from the vector drawing program was incredibly inefficient, and we ended up downloading a general-purpose traveling-salesman-solver written in Java.
It converged upon a dramatically better solution in a few seconds, and didn't really improve it in the next few minutes. So we just stopped it and ran the good-enough route, while leaving the solver running for two days out of pure curiosity.
Now, it was visibly not perfect, there were a couple skips where we could see a shorter way to do it. And it did eventually find those routes.
So if all you need is a reasonable route for your traveling salespersons, or an acceptably efficient packing arrangement for your shipping container, this is achievable and easy, if you're willing to leave that last 1-2% sitting on the table.
- alexcnwy 7y agoInterestingly related to my favorite approach at a solution: genetic algorithms. You don’t know if you’ve converged on THE solution but you can know you have a solution.
- Jedd 7y ago> It converged upon a dramatically better solution in a few seconds, and didn't really improve it in the next few minutes. Which in turn is, I think, a manifestation of the Secretary Problem. https://en.wikipedia.org/wiki/Secretary_problem https://en.wikipedia.org/wiki/Secretary_problem
- karussell 7y agoI think this is more the general behaviour of heuristics. They are not guaranteed to give you the optimal solution as they are forced to 'converge'.
- karussell 7y agoThere is software like concorde that solves traveling salesman problems really fast and optimal: http://www.math.uwaterloo.ca/tsp/methods/opt/opt.htm http://www.math.uwaterloo.ca/tsp/methods/opt/opt.htm Still these type of problems are much trickier in practise, e.g. with time windows or even with multiple salesmen (then it is a vehicle routing problem). For these problems still specialized software exists like jsprit (shameless plug!) and others: https://github.com/graphhopper/jsprit/blob/master/docs/Other-Projects.md https://github.com/graphhopper/jsprit/blob/master/docs/Other...
- gumby 7y agoHumans have bin packing hardware in the visual systems. They very rapidly are able to find a pretty good solution to, say, stick stuff in the back of the car, but if you give them an abstract equivalent problem to solve it's as hard as anything else to solve.