Расстояние городских кварталов

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

Расстояние городских кварталовметрика, введённая Германом Минковским. Согласно этой метрике, расстояние между двумя точками равно сумме модулей разностей их координат.

У этой метрики много имён. Расстояние городских кварталов также известно как манхэттенское расстояние, метрика прямоугольного города, метрика L1 или норма (см. пространство Lp), метрика городского квартала, метрика такси, метрика Манхэттена, прямоугольная метрика, метрика прямого угла; на её называют метрикой гриды и 4-метрикой[1][2][3].

Название «манхэттенское расстояние» связано с уличной планировкой Манхэттена[4].

Окружности в дискретной и непрерывной геометрии городских кварталов

Формальное определение[править | править вики-текст]

Расстояние городских кварталов между двумя векторами в n-мерном вещественном векторном пространстве с заданной системой координат — сумма длин проекций отрезка между точками на оси координат. Более формально,

где

и

векторы.

Например, на плоскости расстояние городских кварталов между и равно

Свойства[править | править вики-текст]

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

Шар в этой метрике имеет форму октаэдра, вершины которого лежат на осях координат.

Примеры[править | править вики-текст]

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].

Клеточные автоматы[править | править вики-текст]

Множество клеток на двумерном квадратном паркете, манхэттенское расстояние до которых от данной клетки не превышает 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 Technology Network.
  5. История компьютера: Эвристические функции
  6. Weisstein, Eric W. von Neumann Neighborhood (англ.) на сайте Wolfram MathWorld.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]