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
3
A
Répondre
4
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.
Questions connexes
- 1. Trier les points verticalement puis horizontalement
- 2. Bouton radio exclusif horizontalement et verticalement
- 3. Centrer Texte Horizontalement et Verticalement dans LATEX
- 4. CSS/jQuery Verticalement et horizontalement Centre DIV
- 5. Comment centrer un formulaire horizontalement et verticalement?
- 6. Comment centrer (verticalement et horizontalement) les boutons d'une balise div?
- 7. Comment mettre en page les enregistrements horizontalement et verticalement
- 8. Que signifie filtrer une collection «verticalement» et «horizontalement»?
- 9. CSS: div fixé verticalement, mais horizontalement mobile
- 10. wxpython - Développer le contrôle de liste verticalement et non horizontalement
- 11. Remplir tout l'espace disponible horizontalement et verticalement, avec divs
- 12. images fluides de dimension variable, verticalement et horizontalement centrés
- 13. remplacer des éléments horizontalement et verticalement dans un tableau 2D
- 14. Centrer horizontalement et verticalement Centre Dival Div IE Édition
- 15. Comment aligner les boutons radio horizontalement plutôt que verticalement?
- 16. XAML Treeview, comment les noeuds affichés horizontalement plutôt que verticalement
- 17. Comment régler l'élément centré horizontalement et verticalement dans Android?
- 18. Comment centrer une citation, verticalement et horizontalement dans du latex?
- 19. Centrer le texte horizontalement et verticalement dans Silverlight
- 20. VS IDE: Diviser les onglets horizontalement ou verticalement
- 21. Comment faire pour que les éléments WPF ListView se répètent horizontalement et verticalement?
- 22. Solution pratique pour centrer verticalement et horizontalement en HTML qui fonctionne dans FF, IE6 et IE7
- 23. Algorithme pour trouver des points proches?
- 24. Éléments de niveau de bloc central verticalement/horizontalement
- 25. Comment faire pour que ma mise en page défile horizontalement et verticalement?
- 26. Aligner les éléments img horizontalement et verticalement au milieu d'un div flottant
- 27. Comment puis-je mosaïquer plusieurs fenêtres wpf horizontalement ou verticalement?
- 28. ASP.NET + CSS - Comment centrer les éléments au milieu de la page Web verticalement et horizontalement?
- 29. Pourquoi WrapPanel enveloppe-t-il horizontalement TextBlocks mais UserControls verticalement?
- 30. Scrollview pour faire défiler le tableau horizontalement et verticalement dans android
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