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

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

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

Обозначается как минимум следующими фразами — синонимами:

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

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

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

Определение

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

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

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

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

Примеры.

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

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

Свойства

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

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

Примеры

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

abcdefgh8

877665544332211abcdefgh

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

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

Пятнашки

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

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

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

См. также

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

Литература

• Eugene F. Krause. Taxicab Geometry (неопр.). — Dover, 1987. — ISBN 0-486-25202-7.

Ссылки

• city-block metric Архивная копия от 1 июля 2007 на Wayback Machine on PlanetMath
• Weisstein, Eric W. Taxicab Metric (англ.) на сайте Wolfram MathWorld.
• Manhattan distance. Paul E. Black, Dictionary of Algorithms and Data Structures, NIST
• Taxi! — AMS column about Taxicab geometry
• TaxicabGeometry.net — a website dedicated to taxicab geometry research and information