Расстояние городских кварталов

Расстояние городских кварталов — метрика, введённая Германом Минковским. Согласно этой метрике, расстояние между двумя точками равно сумме модулей разностей их координат.

В метрике городских кварталов длины красной, жёлтой и синей линий равны между собой (12). В геометрии Евклида зелёная линия имеет длину 6√2 ≈ 8,49 и представляет собой единственный кратчайший путь.

У этой метрики много имён. Расстояние городских кварталов также известно как манхэттенское расстояние, метрика прямоугольного города, метрика L1 или норма $\text{[math]}$ $\text{[math]}$ $\ell _{1}$ $\ell _{1}$ (см. пространство L^p), метрика городского квартала, метрика такси, метрика Манхэттена, прямоугольная метрика, метрика прямого угла; на $\text{[math]}$ $\text{[math]}$ $\mathbb {Z} ^{2}$ $\mathbb {Z} ^{2}$ её называют метрикой гриды и 4-метрикой^[1]^[2]^[3].

Название «манхэттенское расстояние» связано с уличной планировкой Манхэттена^[4].

Окружности в дискретной и непрерывной геометрии городских кварталов

Формальное определениеПравить

Расстояние городских кварталов $\text{[math]}$ $\text{[math]}$ $d_{1}$ между двумя векторами $\text{[math]}$ $\text{[math]}$ $\mathbf {p} ,\mathbf {q}$ в n-мерном вещественном векторном пространстве с заданной системой координат — сумма длин проекций отрезка между точками на оси координат. Более формально,

\text{[math]}

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

где

\text{[math]}

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

и

\text{[math]}

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

— векторы.

Например, на плоскости расстояние городских кварталов между $\text{[math]}$ $\text{[math]}$ $(p_{1},p_{2})$ и $\text{[math]}$ $\text{[math]}$ $(q_{1},q_{2})$ равно $\text{[math]}$ $\text{[math]}$ $|p_{1}-q_{1}|+|p_{2}-q_{2}|.$

СвойстваПравить

Манхэттенское расстояние зависит от вращения системы координат, но не зависит от отражения относительно оси координат или переноса. В геометрии, основанной на манхэттенском расстоянии, выполняются все аксиомы Гильберта, кроме аксиомы о конгруэнтных треугольниках.

Для трёхмерного пространства, шар в этой метрике имеет форму октаэдра, вершины которого лежат на осях координат.

ПримерыПравить


	a	b	c	d	e	f	g	h
8		8
7	7
6	6
5	5
4	4
3	3
2	2
1	1
	a	b	c	d	e	f	g	h

Манхэттенское расстояние между двумя полями шахматной доски равно минимальному количеству ходов, которое необходимо визирю, чтобы перейти из одного поля в другое.

Расстояния в шахматахПравить

Расстояние между полями шахматной доски для визиря (или ладьи, если расстояние считать в полях) равно манхэттенскому расстоянию; король пользуется расстоянием Чебышёва, а слон — манхэттенским расстоянием на доске, повёрнутой на 45°.

ПятнашкиПравить

Сумма манхэттенских расстояний между костяшками и позициями, в которых они находятся в решённой головоломке «Пятнашки», используется в качестве эвристической функции для поиска оптимального решения^[5].

Клеточные автоматыПравить

Множество клеток на двумерном квадратном паркете, манхэттенское расстояние до которых от данной клетки не превышает r, называется окрестностью фон Неймана диапазона (радиуса) r^[6].

См. такжеПравить

ПримечанияПравить

↑ Елена Деза, Мишель Мари Деза. Глава 19. Расстояния на действительной и цифровой плоскостях. 19.1. Метрики на действительной плоскости // Энциклопедический словарь расстояний = Dictionary of Distances. — М.: Наука, 2008. — С. 276. — ISBN 978-5-02-036043-3.
↑ Кластерный анализ: Меры расстояния (неопр.). Дата обращения: 24 июля 2013. Архивировано 7 апреля 2014 года.
↑ Manhattan distance (неопр.). Дата обращения: 24 июля 2013. Архивировано 12 ноября 2006 года.
↑ City Block Distance. Архивная копия от 13 июня 2014 на Wayback Machine Spotfire Technology Network.
↑ История компьютера: Эвристические функции (неопр.). Дата обращения: 24 июля 2013. Архивировано 17 мая 2014 года.
↑ Weisstein, Eric W. von Neumann Neighborhood (англ.) на сайте Wolfram MathWorld.

ЛитератураПравить

Eugene F. Krause. Taxicab Geometry (неопр.). — Dover, 1987. — ISBN 0-486-25202-7.

СсылкиПравить

city-block metric Архивная копия от 1 июля 2007 на Wayback Machine on PlanetMath
Weisstein, Eric W. Taxicab Metric (англ.) на сайте Wolfram MathWorld.
Manhattan distance. Paul E. Black, Dictionary of Algorithms and Data Structures, NIST
Taxi! — AMS column about Taxicab geometry
TaxicabGeometry.net — a website dedicated to taxicab geometry research and information

[1] Елена Деза, Мишель Мари Деза. Глава 19. Расстояния на действительной и цифровой плоскостях. 19.1. Метрики на действительной плоскости // Энциклопедический словарь расстояний = Dictionary of Distances. — М.: Наука, 2008. — С. 276. — ISBN 978-5-02-036043-3.

[2] Кластерный анализ: Меры расстояния (неопр.). Дата обращения: 24 июля 2013. Архивировано 7 апреля 2014 года.

[3] Manhattan distance (неопр.). Дата обращения: 24 июля 2013. Архивировано 12 ноября 2006 года.

[4] City Block Distance. Архивная копия от 13 июня 2014 на Wayback Machine Spotfire Technology Network.

[5] История компьютера: Эвристические функции (неопр.). Дата обращения: 24 июля 2013. Архивировано 17 мая 2014 года.

[6] Weisstein, Eric W. von Neumann Neighborhood (англ.) на сайте Wolfram MathWorld.

[1]

[2]

[3]

[4]

[5]

[6]