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

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

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

У цієї метрики багато назв. Мангеттенська метрика відома як мангеттенська відстань, відстань міських кварталів, метрика прямокутного міста, метрика L1, вулична метрика або норма (див. простір Lp), метрика міського кварталу, метрика таксі, прямокутна метрика, метрика прямого кута; на її називають метрикою гріди та 4-метрикою[1][2][3].

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

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

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

[ред. | ред. код]

Мангеттенська метрика між двома векторами в n-вимірному дійсному просторі з заданою прямокутною системою координат — сума довжин проєкцій відрізка між точками на осі координат. Більш формально

де

і  — вектори.

Наприклад, на площині відстань міських кварталів між точками і дорівнює

Властивості

[ред. | ред. код]

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

Куля в цій метриці має форму октаедру, вершини якого лежать на осях координат.

Приклади

[ред. | ред. код]
abcdefgh
8
a8 шістка
b8 п'ятірка
c8 четвірка
d8 трійка
e8 двійка
f8 трійка
g8 четвірка
h8 п'ятірка
a7 п'ятірка
b7 четвірка
c7 трійка
d7 двійка
e7 одиниця
f7 двійка
g7 трійка
h7 четвірка
a6 четвірка
b6 трійка
c6 двійка
d6 одиниця
e6 біла перевернута тура
f6 одиниця
g6 двійка
h6 трійка
a5 п'ятірка
b5 четвірка
c5 трійка
d5 двійка
e5 одиниця
f5 двійка
g5 трійка
h5 четвірка
a4 шістка
b4 п'ятірка
c4 четвірка
d4 трійка
e4 двійка
f4 трійка
g4 четвірка
h4 п'ятірка
a3 сімка
b3 шістка
c3 п'ятірка
d3 четвірка
e3 трійка
f3 четвірка
g3 п'ятірка
h3 шістка
a2 вісімка
b2 сімка
c2 шістка
d2 п'ятірка
e2 четвірка
f2 п'ятірка
g2 шістка
h2 сімка
a1 дев'ятка
b1 вісімка
c1 сімка
d1 шістка
e1 п'ятірка
f1 шістка
g1 сімка
h1 вісімка
8
77
66
55
44
33
22
11
abcdefgh
Мангеттенська відстань між двома полями шахової дошки дорівнює мінімальній кількості ходів, яке необхідне візиру, щоб з одного поля перейти в інше.

Відстань в шахах

[ред. | ред. код]

Відстань між полями шахової дошки для візиру (або тури, якщо відстань рахувати в клітинах) дорівнює мангеттенській відстані; король і ферзь користуються відстанню Чебишова, а слон — мангеттенською відстанню на дошці, повернутій на 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.

Література

[ред. | ред. код]

Посилання

[ред. | ред. код]