Відкрити головне меню

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

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

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

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

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

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

Формальне визначенняРедагувати

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

 

де

  і   — вектори.

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

ВластивостіРедагувати

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

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

ПрикладиРедагувати

abcdefgh
88
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. Кластерный анализ: Меры расстояния
  3. Manhattan distance
  4. City Block Distance. Spotfire[en] Technology Network.
  5. Історія комп'ютера: Еврістичні функції
  6. Weisstein, Eric W. von Neumann Neighborhood(англ.) на сайті Wolfram MathWorld.

ЛітератураРедагувати

ПосиланняРедагувати