MATLAB Answers

Shortest path through nodes

조회 수: 2(최근 30일)
Francesco Cattaneo
Francesco Cattaneo 2020년 9월 10일
답변: Christine Tobler 2020년 9월 10일
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
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:
Otherwise your best bet is the seemingly complex solutions you can find.

댓글을 달려면 로그인하십시오.

채택된 답변

Christine Tobler
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:

추가 답변(0개)




Community Treasure Hunt

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

Start Hunting!

Translated by