Shortest path through nodes

13 次查看（过去 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:
travel
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: https://www.mathworks.com/help/optim/examples/travelling-salesman-problem.html

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品


版本

R2019b

Community Treasure Hunt

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

Start Hunting!

Translated by