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

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

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

У цієї метрики багато імен. Манхеттенська метрика також відома як манхеттенська відстань, відстань міських кварталів, метрика прямокутного міста, метрика L1, вулична метрика або норма \ell_1 (див. простір Lp), метрика міського кварталу, метрика таксі, прямокутна метрика, метрика прямого кута; на \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
Chessboard480.svg
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
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Манхеттенська відстань між двома полями шахової дошки дорівнює мінімальній кількості ходів, яке необхідне візиру, щоб з одного поля перейти в інше.

Відстань в шахах[ред.ред. код]

Відстань між полями шахової дошки для візиру (або тури, якщо відстань рахувати в клітинах) дорівнює манхеттенській відстані; король і ферзь користуються відстанню Чебишова, а слон — манхеттенською відстанню на дошці, повернутій на 45°.

П'ятнашки[ред.ред. код]

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

Клітинні автомати[ред.ред. код]

Множина клітин на двовимірному квадратному паркеті(en), манхеттенська відстань до яких від даної клітини не перевищує r, називається околом фон Неймана(en) діапазона (радіуса) r[6].

Див. також[ред.ред. код]

Примітки[ред.ред. код]

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

Література[ред.ред. код]

Посилання[ред.ред. код]