Меню Главная Случайная статья Настройки Расстояние городских кварталов Материал из https://ru.wikipedia.org Расстояние городских кварталов между точками A и B — сумма модулей разностей координат точек A и B, метрика, введённая Германом Минковским. Обозначается[1][2][3] как минимум следующими фразами — синонимами: расстояние городских кварталов; метрика городского квартала; метрика прямоугольного города; прямоугольная метрика; метрика прямого угла; метрика такси; метрика Манхэттена; манхэттенское расстояние; в пространстве Lp метрика L1, норма ${\displaystyle \ell _{1}}$; в ${\displaystyle \mathbb {Z} ^{2}}$ метрика гриды, 4-метрика. Название «манхэттенское расстояние» связано с уличной планировкой боро (района) Манхэттен города Нью-Йорк[4]. Содержание 1 Определение 2 Свойства 3 Примеры 3.1 Расстояния в шахматах 3.2 Пятнашки 3.3 Клеточные автоматы 4 См. также 5 Примечания 6 Литература 7 Ссылки Определение Пусть дано следующее: 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 Для ферзя и ладьи расстояние между полями шахматной доски равно расстоянию городских кварталов, изменяемому в полях шахматной доски. Для короля пользуется расстояние Чебышёва. Для слона используется расстояние городских кварталов на такой шахматной доске, которая повёрнута на 45°. Пятнашки При поиске оптимального решения игры (головоломки) «пятнашки» сумма расстояний городских кварталов между костяшками и теми позициями, в которых костяшки находятся в решённой игре, используется[5] в качестве эвристической функции. Клеточные автоматы Множество клеток на двумерном квадратном паркете, расстояние городских кварталов до которых от данной клетки не превышает r, называется[6] окрестностью фон Неймана диапазона (радиуса) r. См. также Нормированное векторное пространство Метрика Расстояние Хэмминга Расстояние Чебышёва Французская железнодорожная метрика Игра в 15 Случайное блуждание Матрица расстояний Примечания Елена Деза, Мишель Мари Деза. Глава 19. Расстояния на действительной и цифровой плоскостях. 19.1. Метрики на действительной плоскости // Энциклопедический словарь расстояний = Dictionary of Distances. — М.: Наука, 2008. — С. 276. — ISBN 978-5-02-036043-3. Кластерный анализ: Меры расстояния . Дата обращения: 24 июля 2013. Архивировано 7 апреля 2014 года. Manhattan distance . Дата обращения: 24 июля 2013. Архивировано 12 ноября 2006 года. City Block Distance. Архивная копия от 13 июня 2014 на Wayback Machine Spotfire Technology Network. История компьютера: Эвристические функции . Дата обращения: 24 июля 2013. Архивировано 17 мая 2014 года. Weisstein, Eric W. von Neumann Neighborhood (англ.) на сайте Wolfram MathWorld. Литература Ссылки 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