Vzdálenost městského bloku

Vzdálenost městských bloků je metrika zavedená Hermannem Minkowskim . Podle této metriky je vzdálenost mezi dvěma body rovna součtu modulů jejich souřadnicových rozdílů.

Tato metrika má mnoho jmen. Vzdálenost městských bloků je také známá jako vzdálenost na Manhattanu , obdélníková metrika města , metrika L1 nebo norma $\ell _{1}$ (viz prostor Lp ) , metrika městských bloků , taxi metric , manhattanská metrika , obdélníková metrika , pravoúhlá metrika ; na něm se nazývá mřížková metrika a 4-metrika [1] [2] [3] . $\mathbb {Z} ^{2}$

Název „Manhattanská vzdálenost“ odkazuje na uliční uspořádání Manhattanu [4] .

Formální definice

Vzdálenost městských bloků mezi dvěma vektory v n - rozměrném reálném vektorovém prostoru s daným souřadnicovým systémem je součtem délek průmětů segmentů mezi body na souřadnicové ose. Formálněji, $d_{1}$ $\mathbf {p} ,\mathbf {q}$

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

kde

\mathbf {p} =(p_{1},p_{2},\tečky ,p_{n})

a jsou vektory .

{\mathbf {q}}=(q_{1},q_{2},\tečky ,q_{n})

Například v rovině je vzdálenost městských bloků mezi a rovna $(p_{1}, p_{2})$ $(q_{1},q_{2})$ $|p_{1}-q_{1}|+|p_{2}-q_{2}|.$

Vlastnosti

Manhattanská vzdálenost závisí na rotaci souřadnicového systému, ale nezávisí na odrazu kolem souřadnicové osy nebo translace . V geometrii založené na vzdálenosti Manhattan platí všechny Hilbertovy axiomy kromě axiomu o shodných trojúhelníkech.

Pro trojrozměrný prostor má koule v této metrice tvar osmistěnu , jehož vrcholy leží na souřadnicových osách.

Příklady

Vzdálenosti v šachu

Vzdálenost mezi čtverci šachovnice pro vezíra (nebo věž , pokud se vzdálenost počítá ve čtvercích) se rovná vzdálenosti na Manhattanu; král používá vzdálenost Čebyšev a biskup používá vzdálenost Manhattan na desce otočené o 45°.

Patnáct

Součet manhattanských vzdáleností mezi kostmi a pozicemi, ve kterých se nacházejí ve vyřešené hádance „ Patnáct “, se používá jako heuristická funkce k nalezení optimálního řešení [5] .

Buněčné automaty

Množina buněk na dvourozměrné čtvercové parketě , jejíž manhattanská vzdálenost od dané buňky nepřesahuje r , se nazývá von Neumannovo okolí rozsahu (poloměru) r [6] .

Viz také

Poznámky

↑ Elena Deza, Michelle Marie Deza. Kapitola 19 19.1. Metrics on the Real Plane // Encyklopedický slovník vzdáleností = Dictionary of Distancs. - M .: Nauka, 2008. - S. 276 . — ISBN 978-5-02-036043-3 .
↑ Shluková analýza: Míry vzdálenosti . Získáno 24. července 2013. Archivováno z originálu 7. dubna 2014. (neurčitý)
↑ Vzdálenost Manhattan . Získáno 24. července 2013. Archivováno z originálu 12. listopadu 2006. (neurčitý)
↑ Vzdálenost městského bloku. Archivováno 13. června 2014 na Wayback Machine Spotfire Technology Network.
↑ Historie počítače: Heuristické funkce . Získáno 24. července 2013. Archivováno z originálu 17. května 2014. (neurčitý)
↑ Weisstein, Eric W. von Neumann Neighborhood (anglicky) na webu Wolfram MathWorld .

Literatura

Evžen F. Krause. Geometrie taxi (neopr.) . - Dover, 1987. - ISBN 0-486-25202-7 .

Odkazy

metrika městských bloků Archivováno 1. července 2007 na Wayback Machine na PlanetMath
Weisstein, Eric W. Taxicab Metric (anglicky) na webových stránkách Wolfram MathWorld .
Vzdálenost Manhattan . Paul E. Black, Slovník algoritmů a datových struktur , NIST
Taxi! —AMS sloupek o geometrii Taxicabu
TaxicabGeometry.net — webová stránka věnovaná výzkumu geometrie taxi a informacím

Slovníky a encyklopedie	Britannica (online)