Byblok afstand

Byblokafstand er en metrik introduceret af Hermann Minkowski . Ifølge denne metrik er afstanden mellem to punkter lig med summen af modulerne af deres koordinatforskelle.

Denne metrik har mange navne. Byblokafstand er også kendt som Manhattan-afstand , rektangulær by -metrisk , L1-metrisk eller norm ( $\ell _{1}$ se Lp -mellemrum ), byblok- metrisk , taxa -metrisk , Manhattan-metrisk , rektangulær metrisk , retvinklet metrisk ; på den kaldes gittermetrikken og 4-metrikken [1] [2] [3] . $\mathbb {Z} ^{2}$

Navnet "Manhattan distance" henviser til Manhattans gadelayout [ 4] .

Formel definition

Afstanden af byblokke mellem to vektorer i et n - dimensionelt reelt vektorrum med et givet koordinatsystem er summen af længderne af segmentprojektionerne mellem punkter på koordinataksen. Mere formelt, $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}|,

hvor

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

og er vektorer .

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

For eksempel på et fly er afstanden mellem byblokke mellem og lig med $(p_{1},p_{2})$ $(q_{1},q_{2})$ $|p_{1}-q_{1}|+|p_{2}-q_{2}|.$

Egenskaber

Manhattan-afstanden afhænger af koordinatsystemets rotation , men afhænger ikke af refleksion om koordinataksen eller translation . I geometri baseret på Manhattan-afstanden gælder alle Hilberts aksiomer undtagen aksiomet om kongruente trekanter.

For et tredimensionelt rum har kuglen i denne metrik form som et oktaeder , hvis toppunkter ligger på koordinatakserne.

Eksempler

Afstande i skak

Afstanden mellem kvadraterne på et skakbræt for en vesir (eller et tårn , hvis afstanden tælles i kvadrater) er lig med Manhattan-afstanden; kongen bruger Chebyshev-afstanden, og biskoppen bruger Manhattan-afstanden på et bræt roteret 45°.

Femten

Summen af Manhattan-afstandene mellem knoglerne og de positioner, de er placeret i i det løste " Femten "-puslespil, bruges som en heuristisk funktion til at finde den optimale løsning [5] .

Mobilautomater

Sættet af celler på en todimensionel firkantet parket , hvis Manhattan-afstand fra en given celle ikke overstiger r , kaldes von Neumann-kvarteret i området (radius) r [6] .

Se også

Noter

↑ Elena Deza, Michelle Marie Deza. Kapitel 19 19.1. Metrics on the Real Plane // Encyclopedic Dictionary of Distances = Dictionary of Distances. - M . : Nauka, 2008. - S. 276 . — ISBN 978-5-02-036043-3 .
↑ Klyngeanalyse: Afstandsmål . Hentet 24. juli 2013. Arkiveret fra originalen 7. april 2014. (ubestemt)
↑ Manhattan afstand . Hentet 24. juli 2013. Arkiveret fra originalen 12. november 2006. (ubestemt)
↑ Byblok afstand. Arkiveret 13. juni 2014 på Wayback Machine Spotfire Technology Network.
↑ Computerens historie: Heuristiske funktioner . Hentet 24. juli 2013. Arkiveret fra originalen 17. maj 2014. (ubestemt)
↑ Weisstein, Eric W. von Neumann Neighborhood (engelsk) på Wolfram MathWorld- webstedet .

Litteratur

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

Links

byblok metrisk Arkiveret 1. juli 2007 på Wayback Machine på PlanetMath
Weisstein, Eric W. Taxicab Metric (engelsk) på Wolfram MathWorld- webstedet .
Manhattan afstand . Paul E. Black, Dictionary of Algorithms and Data Structures , NIST
Taxa! —AMS-spalte om Taxa-geometri
TaxicabGeometry.net — et websted dedikeret til forskning og information om taxigeometri

Ordbøger og encyklopædier	Britannica (online)