Мангеттенська метрика

У Мангеттенській метриці довжини червоної, жовтої і синьої ліній рівні між собою (12). У геометрії Евкліда зелена лінія має довжину 12/√2 ≈ 8.48 і являє собою єдиний найкоротший шлях.

Мангеттенська метрика (метрика прямокутного міста, метрика L₁) — метрика, запроваджена Германом Мінковським. За цією метрикою, відстань між двома точками дорівнює сумі модулів різниць їх координат.

У цієї метрики багато назв. Мангеттенська метрика відома як мангеттенська відстань, відстань міських кварталів, метрика прямокутного міста, метрика L1, вулична метрика або норма ${\displaystyle \ell _{1}}$ (див. простір L^p), метрика міського кварталу, метрика таксі, прямокутна метрика, метрика прямого кута; на ${\displaystyle \mathbb {Z} ^{2}}$ її називають метрикою гріди та 4-метрикою[1][2][3].

Назва «мангеттенська відстань» пов'язана з вуличним плануванням Мангеттена[4], де вулиці перетинаються під прямими кутами.

Кола в дискретній і неперервній геометрії міських кварталів.

Формальне визначення

Мангеттенська метрика ${\displaystyle d_{1}}$ між двома векторами ${\displaystyle \mathbf {p} ,\mathbf {q} }$ в n-вимірному дійсному просторі з заданою прямокутною системою координат — сума довжин проєкцій відрізка між точками на осі координат. Більш формально

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

де

${\displaystyle \mathbf {p} =(p_{1},p_{2},\dots ,p_{n})}$ і ${\displaystyle \mathbf {q} =(q_{1},q_{2},\dots ,q_{n})\,}$ — вектори.

Наприклад, на площині відстань міських кварталів між точками ${\displaystyle (p_{1},p_{2})}$ і ${\displaystyle (q_{1},q_{2})}$ дорівнює ${\displaystyle |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].

Див. також

• Нормований простір
• Метрика
• Відстань Геммінга
• Відстань Чебишова
• Французька залізнична метрика
• П'ятнашки
• Випадкове блукання

Примітки

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

Література

• Eugene F. Krause (1987). Taxicab Geometry. Dover. ISBN 0-486-25202-7.

Посилання

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