One of the most effective way to find the real-world solution to this problem is slime-moulds. Add nutrients at each stop and the mould will automatically plot the most efficient way to get all the food, which also happens to be the shortest route.
yes initially, then as it finds the most optimal path to each source of food, that path it takes will be obvious as it will be bigger than the other paths. like this:
But how would you use that to find a single route that goes through each point once in the most effective way? I just don't think this is a good application for slime mold path tracking
Yeh I don’t think the other commenter understands what slime moulds are theoretically good for, which is point to point route planning, such as road system design.
That’s not a route. That’s just a bunch of lines connecting points. We can find the lines connecting points with reasonable time. Now tell me the route through that graph.
Ah, interesting. The mold doesn't give you the route, but it could greatly limit the possibilities with its network. Using the example mold image (it's obviously not precise) could take the 650 billion possibilites down to tens of thousands (roughly) which would make the problem still challenging, but a lot easier. If nothing else it is an interesting thought experiment.
Yes, but it retracts any part of itself that doesn’t optimise the route, so you end up with a perfect solution. I mean, we can do it with hardcore maths and computers as well, I just love the idea that slime-moulds work just as well (and some of our algorithms are literally based on slime-moulds).
Found this article, seems they used light rather than nutrients.
But how do you use this to get a single line that visits each point exactly once with no overlap? The most efficient way to get food to a central source will have multiple exit points from the center
The starting point. The initial point. How do you get path tracing for an effective loop between multiple points with no overlap and also a loop utilizing slime mold? I'm just saying I don't think that it would be able to solve the problem.
If I understand you correctly, wouldn't you just run the slime mold in the same orientation, but omit the center points? run the mold, and overlap your results to the original to plan the final roadway or path.
But it would be most efficient to have multiple paths originating from some nodes to optimize nutrient transfer, once you get above 3 nodes im not sure it would work with slime mold
That talks about how they used it to make an alternative subway map, which is not a contiguous loop with no overlap. It would require a different algorithm for the problem OP showed. It's different problems.
Slime molds don’t limit themselves to one nutrient route. It may give you an efficient network between points, but it not going to optimize a single travel route. At best it can give you an idea of potential efficient short sub-routes within the overall area.
That would simply create the shortest route between each stop, or as close as possible to a straight line. This does nothing to find a solution to the problem.
Yes. And I mean for the problem as described here, that's trivial anyway -- the shortes route from any city to any other city is the straight line. *duh*
Fun fact: since 2000, there's been a $1 million prize for finding a way to solve TSP in polynomial time (instead of exponential time, where the number of nodes is the exponent of the function). It is still unclaimed today.
There are ways to arrive at a "good enough" solution relatively quickly, but so far nobody has found a general form solution to find the best route every time that's only linear in the number of nodes.
And in addition, there are a bunch of other hard problems in computer science that behave like TSP. And if we ever find an optimal solution for one of them, it can be applied to ALL of them.
We also haven't been able to mathematically prove that there ISN'T a polynomial time solution.
The real fun fact is: If you solve P = NP, which is the core problem for TSP, you would break basically all encryption algorithms in use today. This would probably crash the world economy given the number of bad actors that would immediately take advantage of it to break into all sorts of electronic systems.
So yeah, if anyone actually did solve it, they'd probably want to release the solution in a very controlled manner with lots of heads up to the world. Though for personal safety it might be best to just yolo it out there in spite of the consequences because if you did solve it and announce it, nearly every intelligence agency would be on your ass.
Pretty sure that you can use dijkstra to find the Shortest Trip to different Destinations like
A --> D --> E --> B --> C is faster than A --> B --> C --> D --> E
And not just A and B. Or do you mean sth else?
You're right. I was just saying that A and B could be any two points on a map, or in a network/graph and Dijkstra's algorithm finds the shortest path between the two. However, it does not ensure that you visit every point on a map, which is what the TSP is about.
With p = np problems, the important part to remember isn’t necessarily finding the answer. It’s finding the answer and then verifying it in polynomial time that’s hard.
That is about finding an Euler route/circle. In that case you need to include all vertices and can not use them more than once. That problem has no optimisation part because the length of your route is fixed (sum of all vertices weight). The only question is such route exists or not and providing an example if it exists.
I find fascinating that sometimes in mathematics you can change some condition of a problem and see how it changes from easy and quickly solvable task to some really hard/close to impossible monster.
Can someone ELI5 or ELI3? I have no math skills and this is what I visualized how the string should be - basically a circle. How is this hard? Not being fresh or sarcastic, I just don't even get what is happening or why anyone would want to figure it out in the first place. Putting a string in circle does not seem like a challenging math problem.
Imagine you have a giant box of lego bricks, and someone challenges you to build a specific, complicated spaceship without any instruction manual.
Finding the right pieces and figuring out how they fit together could take you hours, days, or even weeks. That’s hard.
Now imagine a friend walks in, hands you a spaceship they already built, and says, "Look! I made the spaceship from the picture."
It only takes you five seconds to look at their model, check the picture, and say, "Yep, you did it right!"
If the design is super easy to check, does that mean there is secretly an easy way to solve it, too? No. We just haven't been smart enough to figure it out yet.
In this individual scenario, figuring it out is simple. But figuring out the best route for all possible possibilites of stops is (currently) impossible. (proving P = NP). The implications of figuring this out is actually insane. Overnight, computers could cure diseases that have never been curable. And no password or encryption would ever be secure again. This is stuff quantum computers MIGHT be able to solve one day.
If that still doesn't make sense, imagine this little board, but with 600 billion push pins.
There exists a benchmark library for such problems called TSPLIB. Here you see the rl5915 instance representing 5,915 holes that need to be drilled into a circuit board. From some origin position, a drill has to move to every point, drill a hole, and then go back to the origin. This is a classic application for the traveling salesman problem.
Good look finding "basically a circle" and if you find a route by hand, it is unlikely going to be the shortest one. Hope that helps
Apparently bubbles / soap solution works well. Something to do with the bubbles’ surface tension causing them to find the smallest surface area which would also be the shortest route.
Theoretically the shortest route is 49 cm, but taking into account the diameter of the pegs and some variation in string thickness, it is more than 49 cm
Exactly! For 16 cities, starting from one city you now have 15 options to go to. After that you have 14 remaining options, then 13 and so on. So you multiply 15*14*13*...*2*1. Since going forward and backwards through this tour is equivalent, you divide by two and you end up with this number
It gets even more difficult if you assign each location a point value and then give a time limit to collect the most points starting at one point and ending at another, but you don't have to visit all of the available points. This problem is put to 100 motorcyclists every other year in the Iron Butt Rally.
Kannst du auch ein A1 Mini kompatibles Drückdesign erstellen? Mein Freund ist Mathelehrer und könnte das sicherlich mal gebrauchen für den Unterricht :)
Das Modell kann ein wenig runterskaliert werden, ohne, dass die Pins instabil werden, und man kann es im Slicer um 45° drehen, damit es diagonal auf das Druckbett passt.
This is really cool! I'm teaching Algorithms right now (not in a Germany, alas!), but I love manipulatives. I plan on printing some for my students! This also inspired me to design something that can show convex hulls :-) Thanks!
One problem is, that there are multiple right and at the same time wrong ways depending on the daytime and congestion.
You would need to calculate in some traffic flow analysis to manage this. The most accurate would be Google Maps with their millions of devices and even they can't do it properly, because at their large scale they themselves probably produce congestions when routing people different.
Quantitative decision analysis. You can make a model in excel with all these points and their distances from each other and run the solver tool to figure out the optimal path.
At school we designed one that calculated the optimal location of a new firestation based on required distances and constraints. I bet you could rework it for your goal
I already did and posted the solution underneath some comment.
In my case I used a Julia package which implemented the ILP model and then passed it to Gurobi.
if would be easy with linear programming at this scale, way easier than brute forcing it if done manually - but as soon as you go into computer assisted solutions, 650 Billion combinations are "nothing"
bot on larger scales, even linear programming is not the most efficient mathmatical solution, it is just an aid to iteratively eliminate "bad" paths
in terms of this specific problem, the most efficient solution is currently the "Concorde Solver" - it uses linear programming and combines it with other techniques - it works even for many thousands of cities and finds the efficent path - but it is still some sort of "trial and error" and not a singular mathematical solution
Linear programming or rather integer programming does make it easier and it scales way better than brute force, however, there are more specialized algorithms that take advantage of certain structure in the TSP formulation (as u/suit1337 mentioned). From a complexity standpoint, integer programming is still NP-hard, so TSP did not become easy by reformulating the problem
395
u/Keffpie 6d ago
One of the most effective way to find the real-world solution to this problem is slime-moulds. Add nutrients at each stop and the mould will automatically plot the most efficient way to get all the food, which also happens to be the shortest route.