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

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

Название «манхэттенское расстояние» связано с уличной планировкой Манхэттена .

Формальное определение

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

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

где

${\displaystyle \mathbf {p} =(p_{1},p_{2},\dots ,p_{n})}$ и ${\displaystyle \mathbf {q} =(q_{1},q_{2},\dots ,q_{n})}$ — векторы .

Например, на плоскости расстояние городских кварталов между ${\displaystyle (p_{1},p_{2})}$ и ${\displaystyle (q_{1},q_{2})}$ равно ${\displaystyle |p_{1}-q_{1}|+|p_{2}-q_{2}|.}$

Свойства

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

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

Примеры

	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°.

Пятнашки

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

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

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

См. также

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

Примечания

Литература

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

Ссылки

• от 1 июля 2007 на Wayback Machine on PlanetMath
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• . Paul E. Black, , NIST
• — AMS column about Taxicab geometry
• — a website dedicated to taxicab geometry research and information