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!