Algorithme pour un minimum de distance manhattan
Je souhaite trouver le point avec le montant minimum de la distance manhattan/rectiligne distance à partir d'un ensemble de points (j'.e la somme des rectiligne de la distance entre ce point et chaque point de la série doit être au minimum ). Le point résultant peut être l'un des points de l'ensemble donné (pas nécessairement). Dans le cas où plus d'un des points d'exister avec la même distance minimale, je souhaite récupérer tous les d'entre eux.
EN D'AUTRES TERMES:
J'ai une grille avec certaines intersections marquées. Je voudrais trouver l'intersection la plus proche de toutes les intersections marquées. C'est, j'ai besoin de trouver un point tel que la somme des distances de tous les points est minimum.
- Est-ce devoirs? Si oui, il convient d'ajouter cette balise. Aussi, avez-vous une liste de points à choisir la réponse?
- signifie que vous avez une grille et un point sur la il a marqué et que vous voulez trouver un point dans la grille qui a moyenne distance Manhattan avec un point marqué?
- Quel est votre problème, alors? Ce n'est pas une vraie question, je pense.
- Demandez-vous: j'ai une grille avec certaines intersections marquées. J'aimerais trouver une intersection sur la grille la plus proche de toutes les intersections marquées. ??
- Pas de devoirs à faire, je suis tombé sur l'article springerlink.com/content/2yrp1u5gkdf05pgx , mais je ne pouvais pas comprendre un seul mot, la pensée que quelqu'un pourrait expliquer ici dans un anglais simple.
- oui, j'ai besoin de trouver un point tel que la somme des distances de tous les points est minimum.
- Quelle est la partie de papier ce faire?
- C'est un problème classique. Voir la petite amie problème dans de Martin Gardner livre "Aha! De perspicacité."
- Est la solution proposée similaire à ce que j'ai? Peut-être que si non, ça sera une bonne idée que vous ajoutez une autre réponse pour référence. Si vous le faites, veuillez @ moi pour que je puisse recevoir une notification 🙂
Vous devez vous connecter pour publier un commentaire.
La chose cool à propos de la Manhatan distance, c'est que la distance est lui-même constitué de deux éléments indépendants: la distance sur les coordonnées x et y. Ainsi, vous pouvez résoudre deux tâches simples et de fusionner les résultats pour obtenir les résultats souhaités.
La tâche dont je parle est: étant donné sont des points sur une ligne. Trouver le point de la droite qui minimise la somme des distances absolues pour tous les points. Si il y a beaucoup de trouver tous les (btw ils toujours se tourner vers un seul segment qui est facile à prouver). Le segment est déterminé par l' (éventuellement deux) points médianes de l'ensemble. Par median je veux dire le point qui a le même nombre de points à gauche et à droite de celui-ci. Dans le cas où le nombre de points est étrange qu'il n'y est aucun point et vous choisissez les points avec une différence de 1 dans les deux directions pour former le segment.
Ici, j'ai ajouter des exemples de solutions de cette tâche plus simple:
Dans le cas où les points sur la ligne sont comme ça:
La solution est simplement un point et c'est
2.Dans le cas où les points sur la ligne sont comme ça:
L'ensemble du segment [0, 2] est la solution du problème.
Vous résoudre cette tâche séparément pour les
xetyde coordonner et de fusionner les résultats pour obtenir le rectangle de minimum éloigné des points.EXEMPLE
Et vient maintenant un exemple de la solution de la tâche initiale.
Imaginez que vous voulez trouver les points qui sont avec un minimum de Manhatan distance à l'ensemble
(0, 6), (1, 3), (3, 5), (3, 3), (4, 7), (2, 4)Vous forment les deux tâches plus simples:
Pour x:
Et ici, la solution est le segment
[2, 3](notez qu'ici, nous avons dupliqué point3, je l'ai représenté en doute pas la manière la plus intuitive).Pour y:
Ici la solution est le segment
[4, 5].Enfin, nous obtenons que la solution de la tâche initiale est le rectangle avec la formule:
COMPLEXITÉ
Comme beaucoup de gens de montrer de l'intérêt dans ce post, j'ai décidé de l'améliorer un peu plus.
Parlons un peu de complexité.
La complexité de la tâche est en fait la même que la complexité de la résolution de la tâche plus simple (parce que, comme déjà discuté de la solution se compose en fait de la résolution de deux tâches plus simples). Beaucoup de gens aller et de le résoudre via le tri et de choisir les médianes. Cependant, ce sera la cause de
O(nlog n)complexité, oùnest le nombre de points dans le jeu d'entrée.Ce qui peut être amélioré si un meilleur algorithme pour trouver la kième élément est utilisé (Exemple de mise en œuvre dans le C++ STL). Cet algorithme suit globalement la même approche que qsort. Le temps d'exécution est
O(n). Même dans le cas de deux médiane des points en restera toujours linéaire (besoin de deux pistes d'un même algorithme), et donc de la complexité de l'algorithme devientO(n). Il est évident que la tâche ne peut pas être résolu plus vite, aussi longtemps que l'entrée est lui-même de la complexité.