PROFILPELAJAR.COM

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

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

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

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

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

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

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

де

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

і

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

— вектори.

Наприклад, на площині відстань міських кварталів між точками $(p_{1},p_{2})$ і $(q_{1},q_{2})$ дорівнює $|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.
↑ Кластерный анализ: Меры расстояния. Архів оригіналу за 7 квітня 2014. Процитовано 1 червня 2014.
↑ Manhattan distance. Архів оригіналу за 12 листопада 2006. Процитовано 1 червня 2014.
↑ City Block Distance. [Архівовано 13 червня 2014 у Wayback Machine.] Spotfire^[en] Technology Network.
↑ Історія комп'ютера: Еврістичні функції. Архів оригіналу за 17 травня 2014. Процитовано 1 червня 2014.
↑ Weisstein, Eric W. von Neumann Neighborhood(англ.) на сайті Wolfram MathWorld.