Shortest path through nodes
2 次查看(过去 30 天)
显示 更早的评论
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 个评论
Bjorn Gustavsson
2020-9-10
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.
采纳的回答
Christine Tobler
2020-9-10
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 个评论
更多回答(0 个)
另请参阅
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!