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

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

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

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

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

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

d 1 ( p , q ) = ‖ p − q ‖ 1 = ∑ i = 1 n | p i − q i | , {displaystyle d_{1}(mathbf {p} ,mathbf {q} )=|mathbf {p} -mathbf {q} |_{1}=sum _{i=1}^{n}|p_{i}-q_{i}|,}

где

p = ( p 1 , p 2 , … , p n ) {displaystyle mathbf {p} =(p_{1},p_{2},dots ,p_{n})} и q = ( q 1 , q 2 , … , q n ) {displaystyle mathbf {q} =(q_{1},q_{2},dots ,q_{n})}

— векторы.

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

Свойства

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

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

Примеры

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

Расстояние между полями шахматной доски для визиря (или ладьи, если расстояние считать в полях) равно манхэттенскому расстоянию; король пользуется расстоянием Чебышёва , а слон — манхэттенским расстоянием на доске, повёрнутой на 45°.

Пятнашки

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

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

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