Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

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

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

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

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

d_1(\mathbf{p}, \mathbf{q}) = \|\mathbf{p} - \mathbf{q}\|_1 = \sum_{i=1}^n |p_i-q_i|,

где

\mathbf{p}=(p_1,p_2,\dots,p_n) и \mathbf{q}=(q_1,q_2,\dots,q_n)\,

векторы.

Например, на плоскости расстояние городских кварталов между (p_1,p_2) и (q_1,q_2) равно | p_1 - q_1 | + | p_2 - q_2 |.

Свойства Править

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

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

Примеры Править

Шаблон:Шахматная диаграмма

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

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

Пятнашки Править

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

Клеточные автоматы Править

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

См. также Править

Примечания Править

  1. Елена Деза, Мишель Мари Деза Глава 19. Расстояния на действительной и цифровой плоскостях. 19.1. Метрики на действительной плоскости // Энциклопедический словарь расстояний = Dictionary of Distances. — М: Наука, 2008. — С. 276. ISBN 978-5-02-036043-3
  2. Кластерный анализ: Меры расстояния
  3. Manhattan distance
  4. City Block Distance. Spotfire Technology Network.
  5. История компьютера: Эвристические функции
  6. Шаблон:Mathworld

Литература Править

Ссылки Править

Викия-сеть

Случайная вики