Shortest path through nodes
2 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
Francesco Cattaneo
le 10 Sep 2020
Réponse apportée : Christine Tobler
le 10 Sep 2020
Hi everyone,
In a 2D plane I've got a starting point and a finish point.
Let's say they are:
p1_xy = [0 1];
p2_xy = [9 8];
Besides those two, I have another bunch of points:
P = [1 1 ; 2 1 ; 3 2 ; 3 3 ; 3 4 ; 5 6 ; 7 6 ; 8 8 ; 8 9];
Is there a simple strategy to find the shortest path from p1 to p2 passing through all P nodes just once?
I think it's some kind of mathematical process. I've found something, but something too complex for my purposes; maybe there's some useful simple function that I don't know about
Thanks to anyone who wants to help me!
1 commentaire
Bjorn Gustavsson
le 10 Sep 2020
Well, no.
This is a version of the traveling salesman problem, which is notoriously difficult, see: Traveling-salesman problem. If you have a small enough bunch of points to pass it is not too bad to solve. Matlab has a (old!) demo of the travling-salesman problem try it:
travel
Otherwise your best bet is the seemingly complex solutions you can find.
Réponse acceptée
Christine Tobler
le 10 Sep 2020
As Bjorn mentioned, this is the traveling salesman problem. The optimization toolbox has an example of how to use their intlinprog solver to solve such a problem: https://www.mathworks.com/help/optim/examples/travelling-salesman-problem.html
0 commentaires
Plus de réponses (0)
Voir également
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!