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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
В метрике городских кварталов длины красной, жёлтой и синей линий равны между собой (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 six
b8 five
c8 four
d8 three
e8 two
f8 three
g8 four
h8 five
a7 five
b7 four
c7 three
d7 two
e7 one
f7 two
g7 three
h7 four
a6 four
b6 three
c6 two
d6 one
e6 white upside-down rook
f6 one
g6 two
h6 three
a5 five
b5 four
c5 three
d5 two
e5 one
f5 two
g5 three
h5 four
a4 six
b4 five
c4 four
d4 three
e4 two
f4 three
g4 four
h4 five
a3 seven
b3 six
c3 five
d3 four
e3 three
f3 four
g3 five
h3 six
a2 eight
b2 seven
c2 six
d2 five
e2 four
f2 five
g2 six
h2 seven
a1 nine
b1 eight
c1 seven
d1 six
e1 five
f1 six
g1 seven
h1 eight
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.

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

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