Finding Shortest Path through whole points without revisiting
20 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
Ömer Yaman
le 18 Août 2020
Réponse apportée : Ömer Yaman
le 18 Août 2020
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 commentaires
Réponse acceptée
Bruno Luong
le 18 Août 2020
Modifié(e) : Bruno Luong
le 18 Août 2020
You can look at TMW tuto on Traveling Salesman Prroblem
or file exchanges of this author
2 commentaires
Walter Roberson
le 18 Août 2020
Note that the request is for a Hamiltonian Path not Travelling Salesman. Travelling Salesman can revisit a point.
Bruno Luong
le 18 Août 2020
"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."
Plus de réponses (2)
Walter Roberson
le 18 Août 2020
this problem is known as the Hamiltonian Path
https://www.mathworks.com/matlabcentral/fileexchange/51610-hamiltonian-graph-source-destination
Voir également
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!