Algorithme pour la distance minimale de manhattan
je souhaite trouver le point avec la somme minimale de distance manhattan/distance rectiligne à partir d'un ensemble de points (I. e la somme de la distance rectiligne entre ce point et chaque point de l'ensemble doit être minimale ). Le point résultant peut être l'un des points de l'ensemble donné (pas nécessairement). S'il y a plus d'un point avec la même distance minimale, je souhaite les récupérer tous.
EN D'AUTRES TERMES:
j'ai une grille avec certains carrefours marqué. 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.
1 réponses
ce qui est cool à propos de la distance de Manhatan, c'est que la distance elle-même comprend deux composantes indépendantes: la distance sur la coordonnée 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: donné sont des points sur une ligne. Trouvez le point sur la ligne qui minimise la somme des distances absolues à tous les points. S'il y a beaucoup de trouver tous (btw ils se transforment toujours pour être un seul segment qui est facile à prouver). Le segment est déterminé par les médianes (potentiellement deux) 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 impair il n'y a pas de tel point et vous choisissez les points avec la différence 1 dans les deux directions pour former le segment.
ici j'ajoute des exemples de solutions de cette tâche plus simple:
Dans le cas où les points sur la ligne sont comme que:
-4 | | | 0 | 2 3 4
^
La solution est simplement un point et c'est 2.
Dans le cas où les points sur la ligne sont comme ça:
-4 | | | 0 | 2 3
^---^
le segment entier [0, 2] est la solution du problème.
vous résolvez cette tâche séparément pour le x et y coordonner puis fusionner les résultats pour obtenir le rectangle des points de distance minimum.
exemple
et voici un exemple de la solution pour la tâche initiale.
Imaginez que vous voulez trouver les points qui sont à distance Manhatan minimum du set (0, 6), (1, 3), (3, 5), (3, 3), (4, 7), (2, 4)
vous formez les deux tâches les plus simples:
Pour x:
0 1 2 3 3 4
^-^
et ici la solution est le segment [2, 3] (notez qu'ici, nous avons dupliqué point 3, que je n'ai probablement pas représenté de la manière la plus intuitive).
Pour y:
3 3 4 5 6 7
^-^
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:
2 <= x <= 3; 4 <= y <= 5
complexité
comme beaucoup de gens manifestent de l'intérêt pour ce billet, j'ai décidé de l'améliorer un peu plus.
parlons 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é la solution en fait consiste à résoudre deux tâches plus simples). Beaucoup de gens vont y aller et le résoudront en triant et en choisissant les médians. Toutefois, cela entraînera O(nlog n) complexité, où n est le nombre de points dans le jeu d'entrée.
ceci peut être amélioré si un meilleur algorithme pour trouver l'élément kth est utilisé (Exemple d'implémentation dans le C++ STL). Cet algorithme suit essentiellement la même approche que qsort. Le temps d'exécution est O(n). Même dans le cas de deux points médians cela restera toujours linéaire (nécessitant deux passages du même algorithme), et donc la complexité totale de l'algorithme devient O(n). Il est évident que la tâche ne peut pas être résolue plus rapidement, tant que l'entrée elle-même est de la complexité mentionnée.