Distanța de bloc

Distanța între blocuri este o măsurătoare introdusă de Hermann Minkowski . Conform acestei metrici, distanța dintre două puncte este egală cu suma modulelor diferențelor lor de coordonate.

Această măsurătoare are multe nume. Distanța de bloc este cunoscută și sub numele de distanță Manhattan , metrica de oraș dreptunghiulară , metrica L1 sau normă $\ell _{1}$ (vezi spațiul L p ), metrica de blocuri de oraș, metrica de taxi , metrica de Manhattan , metrica dreptunghiulară , metrica de unghi drept ; pe ea se numește metrica grilă și metrica 4 [1] [2] [3] . $\mathbb {Z} ^{2}$

Numele „Distanța Manhattan” se referă la aspectul străzilor din Manhattan [4] .

Definiție formală

Distanța blocurilor dintre doi vectori dintr-un spațiu vectorial real n - dimensional cu un sistem de coordonate dat este suma lungimilor proiecțiilor segmentelor dintre punctele de pe axa de coordonate. Mai formal, $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}|,

Unde

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

și sunt vectori .

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

De exemplu, pe un avion , distanța blocurilor dintre și este egală cu $(p_{1},p_{2})$ $(q_{1},q_{2})$ $|p_{1}-q_{1}|+|p_{2}-q_{2}|.$

Proprietăți

Distanța Manhattan depinde de rotația sistemului de coordonate, dar nu depinde de reflecția asupra axei de coordonate sau de translație . În geometria bazată pe distanța Manhattan, toate axiomele lui Hilbert sunt valabile, cu excepția axiomei despre triunghiuri congruente .

Pentru un spațiu tridimensional, bila din această metrică are forma unui octaedru , ale cărui vârfuri se află pe axele de coordonate.

Exemple

Distanțe în șah

Distanța dintre pătratele unei table de șah pentru un vizir (sau o turnă , dacă distanța este numărată în pătrate) este egală cu distanța Manhattan; regele folosește distanța Chebyshev și episcopul folosește distanța Manhattan pe o placă rotită cu 45°.

Cincisprezece

Suma distanțelor Manhattan dintre oase și pozițiile în care acestea sunt situate în puzzle-ul „ Fifteen ” rezolvat este folosită ca funcție euristică pentru a găsi soluția optimă [5] .

Automate celulare

Setul de celule de pe un parchet pătrat bidimensional a cărui distanță Manhattan față de o celulă dată nu depășește r se numește vecinătatea von Neumann a intervalului (raza) r [6] .

Vezi și

Note

↑ Elena Deza, Michelle Marie Deza. Capitolul 19 19.1. Metrics on the Real Plane // Dicționar enciclopedic al distanțelor = Dicționar al distanțelor. - M . : Nauka, 2008. - S. 276 . — ISBN 978-5-02-036043-3 .
↑ Cluster Analysis: Measures of Distance . Consultat la 24 iulie 2013. Arhivat din original la 7 aprilie 2014. (nedefinit)
↑ Distanța Manhattan . Consultat la 24 iulie 2013. Arhivat din original la 12 noiembrie 2006. (nedefinit)
↑ Distanța blocului oraș. Arhivat pe 13 iunie 2014 pe Wayback Machine Spotfire Technology Network.
↑ Istoria computerului: funcții euristice . Preluat la 24 iulie 2013. Arhivat din original la 17 mai 2014. (nedefinit)
^ Weisstein , Eric W. von Neumann Neighborhood (engleză) pe site-ul Wolfram MathWorld .

Literatură

Eugen F. Krause. Geometria taxiului (neopr.) . - Dover, 1987. - ISBN 0-486-25202-7 .

Link -uri

metric city-block Arhivat la 1 iulie 2007 la Wayback Machine pe PlanetMath
Weisstein, Eric W. Taxicab Metric (engleză) pe site-ul web Wolfram MathWorld .
distanta Manhattan . Paul E. Black, Dicționar de algoritmi și structuri de date , NIST
Taxi! — Coloana AMS despre geometria taxiului
TaxicabGeometry.net — un site web dedicat cercetării și informațiilor despre geometria taxiurilor

Dicționare și enciclopedii	Britannica (online)