Расстояние городских кварталов
Расстояние городских кварталов — метрика, введённая Германом Минковским. Согласно этой метрике, расстояние между двумя точками равно сумме модулей разностей их координат.
У этой метрики много имён. Расстояние городских кварталов также известно как манхэттенское расстояние, метрика прямоугольного города, метрика L1 или норма [math]\displaystyle{ \ell_1 }[/math] (см. пространство Lp), метрика городского квартала, метрика такси, метрика Манхэттена, прямоугольная метрика, метрика прямого угла; на [math]\displaystyle{ \mathbb{Z}^2 }[/math] её называют метрикой гриды и 4-метрикой[1][2][3].
Название «манхэттенское расстояние» связано с уличной планировкой Манхэттена[4].
Формальное определение
Расстояние городских кварталов [math]\displaystyle{ d_1 }[/math] между двумя векторами [math]\displaystyle{ \mathbf{p}, \mathbf{q} }[/math] в n-мерном вещественном векторном пространстве с заданной системой координат — сумма длин проекций отрезка между точками на оси координат. Более формально,
- [math]\displaystyle{ d_1(\mathbf{p}, \mathbf{q}) = \|\mathbf{p} - \mathbf{q}\|_1 = \sum_{i=1}^n |p_i-q_i|, }[/math]
где
- [math]\displaystyle{ \mathbf{p}=(p_1,p_2,\dots,p_n) }[/math] и [math]\displaystyle{ \mathbf{q}=(q_1,q_2,\dots,q_n) }[/math] — векторы.
Например, на плоскости расстояние городских кварталов между [math]\displaystyle{ (p_1,p_2) }[/math] и [math]\displaystyle{ (q_1,q_2) }[/math] равно [math]\displaystyle{ | p_1 - q_1 | + | p_2 - q_2 |. }[/math]
Свойства
Манхэттенское расстояние зависит от вращения системы координат, но не зависит от отражения относительно оси координат или переноса. В геометрии, основанной на манхэттенском расстоянии, выполняются все аксиомы Гильберта, кроме аксиомы о конгруэнтных треугольниках.
Для трёхмерного пространства, шар в этой метрике имеет форму октаэдра, вершины которого лежат на осях координат.
Примеры
| 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, называется окрестностью фон Неймана диапазона (радиуса) r[6].
См. также
- Нормированное векторное пространство
- Метрика
- Расстояние Хэмминга
- Расстояние Чебышёва
- Французская железнодорожная метрика
- Игра в 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.
Литература
- 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