El algoritmo de distancia de Manhattan se usó inicialmente para calcular la distancia de la manzana en Manhattan. Echa un vistazo a la imagen de abajo.
La línea verde es una distancia euclidiana, pero como está dentro de la cuadrícula, puede ver que no puede ir directamente del punto 1 al punto 2, por lo que la distancia euclidiana no funciona. Para llegar del punto 1 al punto 2, debe seguir la línea azul que representa la distancia de Manhattan.
- ¿Cómo saben las computadoras cuándo comienza y termina una cadena binaria?
- Si uso un algoritmo de cifrado no tan bueno que inventé dentro de uno real, ¿cuánto más seguros están juntos?
- ¿Cuáles son algunas formas diferentes de calcular la mediana de una matriz en Java?
- ¿Cómo puedo aprender los algoritmos de resolución de problemas solo?
- ¿Dónde puedo aprender conceptos de recursión?
La fórmula para calcular la distancia de Manhattan entre dos puntos es la siguiente:
[matemática] Distancia = abs (x1 – x2) + abs (y1 – y2) [/ matemática]
Según la wiki, se utiliza en la detección comprimida y las diferencias de distribución de frecuencia. Básicamente, se puede usar en cualquier lugar donde necesite calcular la distancia entre puntos en la cuadrícula.
Y el último pero no menos importante, eche un vistazo a la fórmula de la distancia euclidiana:
[matemáticas] Distancia = sqrt ((x1 – x2) ^ 2 + (y1 – y2) ^ 2) [/ matemáticas]
Requiere potencia de dos y operaciones de raíz cuadrada que son operaciones bastante caras, mientras que la distancia de Manhattan solo necesita restar y calcular el valor absoluto (para eliminar el signo). Si no necesita una distancia muy precisa pero necesita calcularla para un conjunto de datos muy grande, el algoritmo de distancia de Manhattan puede ayudar. Por cierto, tampoco estudié el algoritmo durante el curso de CS y lo encontré hace solo unos meses. Parece que no se considera esencial.
Puedes encontrar más aquí.
Editar:
Hubo un error de imprenta en la fórmula de la distancia euclidiana. Gracias a Vincent Tandya por corregirme.
