Finding Shortest Path through whole points without revisiting
20 次查看(过去 30 天)
显示 更早的评论
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 个评论
采纳的回答
Bruno Luong
2020-8-18
编辑:Bruno Luong
2020-8-18
You can look at TMW tuto on Traveling Salesman Prroblem
or file exchanges of this author
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
"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."
更多回答(2 个)
Walter Roberson
2020-8-18
this problem is known as the Hamiltonian Path
https://www.mathworks.com/matlabcentral/fileexchange/51610-hamiltonian-graph-source-destination
另请参阅
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!