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

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

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

Обозначается^[1][2][3] как минимум следующими фразами — синонимами:

• расстояние городских кварталов;
• метрика городского квартала;
• метрика прямоугольного города;
• прямоугольная метрика;
• метрика прямого угла;
• метрика такси;
• метрика Манхэттена;
• манхэттенское расстояние;
• в пространстве L^p метрика L1, норма ${\displaystyle \ell _{1}}$;
• в ${\displaystyle \mathbb {Z} ^{2}}$ метрика гриды, 4-метрика.

Название «манхэттенское расстояние» связано с уличной планировкой боро (района) Манхэттен города Нью-Йорк^[4].

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

Определение

Пусть дано следующее:

• n-мерное вещественное векторное пространство;
• прямоугольная система координат;
• ${\displaystyle \mathbf {p} }$ — вектор с координатами ${\displaystyle p_{1}}$, ${\displaystyle p_{2}}$, ${\displaystyle \dots }$, ${\displaystyle p_{n}}$: ${\displaystyle \mathbf {p} =(p_{1},p_{2},\dots ,p_{n})}$;
• ${\displaystyle \mathbf {q} }$ — вектор с координатами ${\displaystyle q_{1}}$, ${\displaystyle q_{2}}$, ${\displaystyle \dots }$, ${\displaystyle q_{n}}$: ${\displaystyle \mathbf {q} =(q_{1},q_{2},\dots ,q_{n})}$;
• ${\displaystyle d_{1}}$ — расстояние городских кварталов между ${\displaystyle \mathbf {p} }$ и ${\displaystyle \mathbf {q} }$.

Тогда расстояние городских кварталов ${\displaystyle d_{1}}$ между двумя векторами ${\displaystyle \mathbf {p} }$, ${\displaystyle \mathbf {q} }$ в n-мерном вещественном векторном пространстве с заданной системой координат — сумма длин проекций такого отрезка, который соединяет точки ${\displaystyle (p_{1},p_{2},\dots ,p_{n})}$ и ${\displaystyle (q_{1},q_{2},\dots ,q_{n})}$, на оси координат. Более формально,

${\displaystyle d_{1}\left(\mathbf {p} ,\mathbf {q} \right)=\|\mathbf {p} -\mathbf {q} \|_{1}=\sum _{i=1}^{n}|p_{i}-q_{i}|.}$

Примеры.

При ${\displaystyle n}$, равном 2 (в двумерном пространстве, на плоскости), с системой координат, имеющей оси ${\displaystyle x}$ и ${\displaystyle y}$, ${\displaystyle d_{1}}$ между вектором ${\displaystyle \mathbf {p} }$, равным ${\displaystyle (p_{1},p_{2})=(p_{x},p_{y})}$, и вектором ${\displaystyle \mathbf {q} }$, равным ${\displaystyle (q_{1},q_{2})=(q_{x},q_{y})}$, равно ${\displaystyle d_{1}\left(\mathbf {p} ,\mathbf {q} \right)}$ = ${\displaystyle \left|p_{1}-q_{1}\right|+\left|p_{2}-q_{2}\right|}$ = ${\displaystyle \left|p_{x}-q_{x}\right|+\left|p_{y}-q_{y}\right|.}$

При ${\displaystyle n}$, равном 3 (в трёхмерном пространстве), с системой координат, имеющей оси ${\displaystyle x}$, ${\displaystyle y}$ и ${\displaystyle z}$, ${\displaystyle d_{1}}$ между вектором ${\displaystyle \mathbf {p} }$, равным ${\displaystyle (p_{1},p_{2},p_{3})=(p_{x},p_{y},p_{z})}$, и вектором ${\displaystyle \mathbf {q} }$, равным ${\displaystyle (q_{1},q_{2},q_{3})=(q_{x},q_{y},q_{z})}$, равно ${\displaystyle d_{1}\left(\mathbf {p} ,\mathbf {q} \right)}$ = ${\displaystyle \left|p_{1}-q_{1}\right|+\left|p_{2}-q_{2}\right|+\left|p_{3}-q_{3}\right|}$ = ${\displaystyle \left|p_{x}-q_{x}\right|+\left|p_{y}-q_{y}\right|+\left|p_{z}-q_{z}\right|.}$

Свойства

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

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

Примеры

Расстояния в шахматах

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Расстояние городских кварталов, измеряемое в полях (клетках) шахматной доски, между полями A и B равно минимальному количеству полей, на которое необходимо переместить ладью, чтобы переместить ладью из поля A в поле B

Для ферзя и ладьи расстояние между полями шахматной доски равно расстоянию городских кварталов, изменяемому в полях шахматной доски. Для короля пользуется расстояние Чебышёва. Для слона используется расстояние городских кварталов на такой шахматной доске, которая повёрнута на 45°.

Пятнашки

При поиске оптимального решения игры (головоломки) «пятнашки» сумма расстояний городских кварталов между костяшками и теми позициями, в которых костяшки находятся в решённой игре, используется^[5] в качестве эвристической функции.

Клеточные автоматы

Множество клеток на двумерном квадратном паркете, расстояние городских кварталов до которых от данной клетки не превышает r, называется^[6] окрестностью фон Неймана диапазона (радиуса) r.

См. также

• Нормированное векторное пространство
• Метрика
• Расстояние Хэмминга
• Расстояние Чебышёва
• Французская железнодорожная метрика
• Игра в 15
• Случайное блуждание
• Матрица расстояний