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

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

В метрике городских кварталов длины красной, жёлтой и синей линий равны между собой (12). В геометрии Евклида зелёная линия имеет длину 6√2 ≈ 8,49 и представляет собой единственный кратчайший путь.

У этой метрики много имён. Расстояние городских кварталов также известно как манхэттенское расстояние, метрика прямоугольного города, метрика 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. Кластерный анализ: Меры расстояния. Дата обращения: 24 июля 2013. Архивировано 7 апреля 2014 года.
  3. Manhattan distance. Дата обращения: 24 июля 2013. Архивировано 12 ноября 2006 года.
  4. City Block Distance. Архивная копия от 13 июня 2014 на Wayback Machine Spotfire Technology Network.
  5. История компьютера: Эвристические функции. Дата обращения: 24 июля 2013. Архивировано 17 мая 2014 года.
  6. Weisstein, Eric W. von Neumann Neighborhood (англ.) на сайте Wolfram MathWorld.

ЛитератураПравить

СсылкиПравить