im essayant de calculer la distance maximale de Manhattan d'une grande entrée 2D, les entrées sont constituées de (x, y) s et ce que je veux faire est de calculer la distance maximale entre les coordonnées inférieures à O (n ^ 2) Temps, je peux le faire dans O (n ^ 2) en traversant tous les éléments qc comme: mais cela ne fonctionnera pas efficacement Pour de très grandes entrées :(
* (Distance de Manhattan entre deux points (x1, Y1) et (x2, Y2) est: | x1-x2 | + | y1-y2 |)
Quelqu'un a une idée d'un meilleur algorithme?
5 Réponses :
La distance maximale sera comprise entre la plupart des autres points. Donc, vous venez de trouver un point avec un maximum de x et maximum y, puis de trouver du point avec un minimum de x et minimum y et de calculer la distance entre eux. Il peut y avoir beaucoup de points qui correspondront aux critères .. Mais au moins, vous aurez une quantité beaucoup moins de points à vérifier
Non, car la coordonnée avec maximum x, pourrait ne pas avoir le maximum Y! et est tellement avec le minimum aussi, considérez-les: (7, -2), (-1,5), (3, -9) et bien d'autres, ces 3 désapprouveront votre algorithme
La première grande amélioration serait la suivante: puisque la distance entre X et Y est identique à la distance entre Y et X. Cela couperait votre calcul de moitié ...
oui, c'est une amélioration, mais il faut toujours O (n ^ 2) heure :( qui ne fonctionnera pas pour de très grandes intrants
Oui, je sais que je venais de pointer la première amélioration évidente: réduire de moitié le nombre de comparaison est toujours une très grande amélioration. Je pense toujours à une manière plus rapide ...
Il n'y a que deux cas à considérer, si nous considérons uniquement les résultats tels que En la rompant dans ces cas, je me suis débarrassé de la fonction de valeur absolue, ce qui facilite beaucoup la raison des distances.
Donc, nous choisissons simplement des points avec minimum et maximum Ceci peut être fait dans xi <= xj .
yi <= yj , alors la distance est (xj + yj) - (xi + yi)
(xj-yj) - (xi-yi)
x + y et calculez la distance. Puis choisissez Points avec minimum et maximum x-y et calculez la distance. Une de ces deux distances est votre maximum.
O (n) , qui est asymptotiquement optimal.
Il est assez simple et peut être calculé dans let let Maintenant, changez x1 avec x2 et vous prenez les mêmes résultats. donc en général votre solution est O (n) x1> x2 et y1> y2 x1> x2 et y1
La meilleure chose à faire avec des questions telles que ceci est d'établir des petits résultats qui vous aideront avec le problème global.
Par exemple, il n'est pas trop difficile de déterminer que pour des trois points, A, B et C, qui ont la condition que B est entre (plus sur cela dans une seconde) A et C, B ne sera jamais plus éloigné d'un quatrième point D que l'un des A et C. Avec la métrique Euclidienne standard de distance, un point se situe entre deux autres points si cela se situe sur le segment les rejoignant. Pour les mesures de Manhattan, il n'est pas aussi simple - en partie parce que le concept d'un segment n'est pas aussi bien compris.
Une manière plus générale de décrire «entre» est-ce (en utilisant la notation que la distance entre A à B est | AB |):
Un point B est entre deux points A, C si | AB | + | Bc | = | AC |
Vous pouvez voir que dans une distance euclidienne, cela signifie que b est réside sur le segment de joindre A et C.
à distance de Manhattan, cela signifie que le point B est contenu dans le rectangle défini par A et C (bien sûr pourrait être un segment droit si l'AC est parallèle à l'un de l'axe).
Ce résultat signifie que, pour tout point, s'il se situe entre deux points existants, il ne peut plus être plus d'aucun nouveau point ajouté à l'ensemble que les deux qui l'entourent.
Maintenant, cette information ne résout pas le problème pour vous, mais cela vous permet de jeter de nombreux calculs futurs potentiels. Une fois que vous avez déterminé qu'un point se situe entre deux autres, il ne sert à rien de le suivre.
Donc, vous pouvez résoudre ce problème en suivant uniquement les points ultérieurs et en ignorant tout ce qui tombe à l'intérieur.
Prouvez que vous ne pouvez pas avoir plus de 4 points distincts de manière à ce que aucun des points ne soit entre deux des autres, au sens de Manhattan.
Avec ce deuxième résultat, il devient clair que vous n'aurez jamais besoin de suivre jusqu'à 4 points.
Certaines des autres méthodes déjà présentées sont probablement plus rapides, mais de cette façon est plus amusante!
Généralisez ces idées à n dimensions