MATLAB Answers

Shortest path through nodes

1 view (last 30 days)
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 Comment

Bjorn Gustavsson
Bjorn Gustavsson on 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.

Sign in to comment.

Accepted Answer

Christine Tobler
Christine Tobler on 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 Comments

Sign in to comment.

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!