Il y a n points dans le plan 2D. Un robot veut les visiter tous mais ne peut que se déplacer horizontalement ou verticalement. Comment devrait-il les visiter tous afin que la distance totale qu'il couvre est minime?algorithme pour parcourir les points horizontalement et verticalement
Ceci est le Travelling Salesman Problem où la distance entre chaque paire de points est | y2-y1 | + | x2-x1 | (appelé distance rectiligne ou Manhattan distance). C'est NP-hard qui signifie fondamentalement qu'il n'y a aucune solution efficace connue.
Methods to solve it sur Wikipedia.
L'algorithme le plus simple est une recherche de force brute naïve, où vous calculez la distance pour chaque permutation possible des points et trouvez le minimum. Cela a un temps de fonctionnement de O (n!). Cela fonctionnera jusqu'à environ 10 points, mais il deviendra très rapidement trop lent pour un plus grand nombre de points.
Etes-vous sûr que la distance entre les paires de points est | y2-y1 | + | x2-x1 |? Je suis tout à fait sûr de son ': sqrt ((y2-y1)^2 + (x2-x1)^2) –
Cela dit, si vous voulez une très bonne solution, mais pas nécessairement la optimale optimale, cette page wikipedia a également quelques bonnes suggestions. – UncleO
@ Sbm007 Apparemment, le robot ne peut pas se déplacer en diagonale, donc Mark est correct. – UncleO