Finding Shortest Path through whole points without revisiting

Question

Ömer Yaman 2020-8-18

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/581010-finding-shortest-path-through-whole-points-without-revisiting

回答： Ömer Yaman 2020-8-18

Hi all,

I have a problem and I need urgent help. I have more than 30 points (2D cartesian coordinate) with known x and y coordinates. All points can be distributed randomly or on a regular basis such as star shape or cross shape. I would like to asing a one way path which connects all points without circling or revisiting them. How can I implement this question? I would like to visit each point only once and complete the whole journey as quick as possible.

Thanks in advance.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Bruno Luong 2020-8-18

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/581010-finding-shortest-path-through-whole-points-without-revisiting#answer_481527

编辑：Bruno Luong 2020-8-18

You can look at TMW tuto on Traveling Salesman Prroblem

https://uk.mathworks.com/help/optim/ug/travelling-salesman-problem.html

or file exchanges of this author

https://uk.mathworks.com/matlabcentral/fileexchange/?q=profileid:397959

2 个评论
显示无隐藏无

Walter Roberson 2020-8-18

Note that the request is for a Hamiltonian Path not Travelling Salesman. Travelling Salesman can revisit a point.

Bruno Luong 2020-8-18

They are equivalent https://en.wikipedia.org/wiki/Travelling_salesman_problem Related problems

"An equivalent formulation in terms of graph theory is: Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a Hamiltonian cycle with the least weight."

请先登录，再进行评论。

Answer 2

Walter Roberson 2020-8-18

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/581010-finding-shortest-path-through-whole-points-without-revisiting#answer_481503

this problem is known as the Hamiltonian Path

https://www.mathworks.com/matlabcentral/fileexchange/51610-hamiltonian-graph-source-destination

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Ömer Yaman 2020-8-18

Thank you but I am new at that kind of structures. I could not understand well.

Let's say my points as (x,y)

(1,-1), (0,3), (-1,2), (0,2), (1,1), (1,0), (1,3), (1,5), (2,1), (3,1), (-2,1), (0,0), (-1,0), (3,4), (2,3), (4,1), (2,-1)

I need to find the shortest path covers all those points. It should not visit same point twice (like circles or backlines). It may start from any of them (which is optimum)

I have found something known as Minimal Nearest-Neighbor Closed Contour but in this contour it creates loops on some points. I hope I explained my question clearly.

请先登录，再进行评论。