Distancia de bloque de ciudad

La distancia entre bloques de ciudad es una métrica introducida por Hermann Minkowski . Según esta métrica, la distancia entre dos puntos es igual a la suma de los módulos de sus diferencias de coordenadas.

Esta métrica tiene muchos nombres. La distancia de cuadra de la ciudad también se conoce como distancia de Manhattan , métrica de ciudad rectangular , métrica L1 o norma $\ell _{1}$ (ver espacio Lp ) , métrica de cuadra de ciudad, métrica de taxi , métrica de Manhattan , métrica rectangular, métrica de ángulo recto ; en él se llama la métrica de cuadrícula y la métrica de 4 [1] [2] [3] . $\mathbb {Z} ^{2}$

El nombre "distancia de Manhattan" se refiere al diseño de las calles de Manhattan [4] .

Formal definición

La distancia de las manzanas de la ciudad entre dos vectores en un espacio vectorial real de n dimensiones con un sistema de coordenadas dado es la suma de las longitudes de las proyecciones de segmento entre puntos en el eje de coordenadas. Más formalmente, $d_{1}$ $\mathbf{p},\mathbf{q}$

d_{1}(\mathbf {p} ,\mathbf {q} )=\|\mathbf {p} -\mathbf {q} \|_{1}=\sum _{i=1}^{n} |p_{i}-q_{i}|,

dónde

\mathbf {p} =(p_{1},p_{2},\puntos,p_{n})

y son vectores .

{\mathbf {q}}=(q_{1},q_{2},\puntos,q_{n})

Por ejemplo, en un avión , la distancia de las cuadras de la ciudad entre y es igual a $(p_{1},p_{2})$ $(q_{1},q_{2})$ $|p_{1}-q_{1}|+|p_{2}-q_{2}|.$

Propiedades

La distancia de Manhattan depende de la rotación del sistema de coordenadas, pero no depende de la reflexión sobre el eje de coordenadas o la traslación . En geometría basada en la distancia de Manhattan, todos los axiomas de Hilbert se cumplen excepto el axioma sobre triángulos congruentes .

Para un espacio tridimensional, la bola en esta métrica tiene la forma de un octaedro , cuyos vértices se encuentran en los ejes de coordenadas.

Ejemplos

Distancias en el ajedrez

La distancia entre las casillas de un tablero de ajedrez para un visir (o una torre , si la distancia se cuenta en casillas) es igual a la distancia de Manhattan; el rey usa la distancia de Chebyshev y el alfil usa la distancia de Manhattan en un tablero girado 45°.

Quince

La suma de las distancias de Manhattan entre los huesos y las posiciones en las que se encuentran en el rompecabezas " Fifteen " resuelto se utiliza como una función heurística para encontrar la solución óptima [5] .

Autómatas celulares

El conjunto de celdas en un parquet cuadrado bidimensional cuya distancia Manhattan desde una celda dada no excede r se denomina vecindad de von Neumann del rango (radio) r [6] .

Véase también

Notas

↑ Elena Deza, Michelle Marie Deza. capitulo 19 19.1. Métricas en el Plano Real // Diccionario Enciclopédico de Distancias = Diccionario de Distancias. - M. : Nauka, 2008. - S. 276 . — ISBN 978-5-02-036043-3 .
↑ Análisis de conglomerados: medidas de distancia . Consultado el 24 de julio de 2013. Archivado desde el original el 7 de abril de 2014. (indefinido)
↑ Distancia de Manhattan . Consultado el 24 de julio de 2013. Archivado desde el original el 12 de noviembre de 2006. (indefinido)
↑ Distancia de bloque de ciudad. Archivado el 13 de junio de 2014 en Wayback Machine Spotfire Technology Network.
↑ Historia de la computadora: funciones heurísticas . Consultado el 24 de julio de 2013. Archivado desde el original el 17 de mayo de 2014. (indefinido)
↑ Weisstein, Eric W. von Neumann Neighborhood (inglés) en el sitio web de Wolfram MathWorld .

Literatura

Eugene F. Krause. Taxitaxi Geometry (neopr.) . - Dover, 1987. - ISBN 0-486-25202-7 .

Enlaces

métrica de bloque de ciudad Archivado el 1 de julio de 2007 en Wayback Machine en PlanetMath
Weisstein, Eric W. Taxicab Metric (inglés) en el sitio web de Wolfram MathWorld .
distancia de manhattan Paul E. Black, Diccionario de algoritmos y estructuras de datos , NIST
¡Taxi! —Columna AMS sobre geometría de taxi
TaxicabGeometry.net : un sitio web dedicado a la investigación e información sobre la geometría de los taxis

diccionarios y enciclopedias	Britannica (en línea)