Расстояние Чебышева

Математическая метрика

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

В математике расстояние Чебышева (или расстояние Чебышева ), максимальная метрика или L _∞ метрика ^[1] — это метрика , определенная в реальном координатном пространстве , где расстояние между двумя точками является наибольшей из их разностей по любому координатному измерению. ^[2] Назван в честь Пафнутия Чебышева .

Оно также известно как расстояние шахматной доски , поскольку в игре в шахматы минимальное количество ходов, необходимое королю для перехода с одной клетки шахматной доски на другую, равно расстоянию Чебышева между центрами клеток, если клетки имеют длину стороны. один, представленный в двумерных пространственных координатах с осями, выровненными по краям доски. ^[3] Например, расстояние Чебышева между f6 и e2 равно 4.

Определение

Расстояние Чебышева между двумя векторами или точками x и y со стандартными координатами и соответственно равно ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$

${\displaystyle D_{\rm {Chebyshev}}(x,y):=\max _{i}(|x_{i}-y_{i}|).\ }$

Это соответствует пределу _{метрики} Lp :

${\displaystyle \lim _{p\to \infty }{\bigg (}\sum _{i=1}^{n}\left|x_{i}-y_{i}\right|^{p}{\bigg )}^{1/p},}$

следовательно, она также известна как метрика L _∞ .

Математически расстояние Чебышева — это метрика, индуцированная супремум-нормой или равномерной нормой . Это пример инъективной метрики .

В двух измерениях, т.е. в плоской геометрии , если точки p и q имеют декартовы координаты и , их расстояние Чебышева равно ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle (x_{2},y_{2})}$

${\displaystyle D_{\rm {Chebyshev}}=\max \left(\left|x_{2}-x_{1}\right|,\left|y_{2}-y_{1}\right|\right).}$

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

На шахматной доске, где используется дискретное расстояние Чебышева, а не непрерывное, круг радиуса r представляет собой квадрат с длиной стороны 2 r, отсчитываемый от центров квадратов, и, таким образом, каждая сторона содержит 2 r +1 квадрат. ; например, круг радиуса 1 на шахматной доске представляет собой квадрат 3×3.

Характеристики

Сравнение расстояний Чебышева, Евклида и Манхэттена для гипотенузы треугольника 3-4-5 на шахматной доске

В одном измерении все метрики Lp _равны – они представляют собой просто абсолютное значение разницы.

Двумерное манхэттенское расстояние имеет «круги», то есть наборы уровней в форме квадратов со сторонами длиной √ 2 r , ориентированными под углом π/4 (45 °) к осям координат, поэтому плоское расстояние Чебышева может быть рассматривается как эквивалент путем вращения и масштабирования (т.е. линейного преобразования ) плоского манхэттенского расстояния.

Однако эта геометрическая эквивалентность между метриками L ₁ и L _∞ не распространяется на более высокие измерения. Сфера , образованная с использованием в качестве метрики расстояния Чебышева, представляет собой куб , каждая грань которого перпендикулярна одной из осей координат, а сфера, образованная с использованием манхэттенского расстояния, — октаэдр : это двойственные многогранники , но среди кубов только квадрат (и 1 -мерный отрезок) являются самодвойственными многогранниками . Тем не менее, верно, что во всех конечномерных пространствах метрики L ₁ и L _∞ математически двойственны друг другу.

На сетке (например, на шахматной доске) точки на расстоянии Чебышева, равном 1 точке, являются окрестностью Мура этой точки.

Расстояние Чебышева является предельным случаем расстояния порядка-Минковского , когда достигает бесконечности . ${\displaystyle p}$ ${\displaystyle p}$

Приложения

Расстояние Чебышева иногда используется в складской логистике , ^[4] поскольку оно эффективно измеряет время, необходимое мостовому крану для перемещения объекта (поскольку кран может перемещаться по осям x и y одновременно, но с одинаковой скоростью вдоль каждой оси). ось).

Он также широко используется в электронных приложениях автоматизированного производства (CAM) , в частности, в алгоритмах их оптимизации. Многие инструменты, такие как плоттеры или сверлильные станки, фотоплоттеры и т. д., работающие в плоскости, обычно управляются двумя двигателями в направлениях x и y, подобно мостовым кранам. ^[5]

Обобщения

Для пространства последовательностей последовательностей действительных или комплексных чисел бесконечной длины расстояние Чебышева обобщается до -нормы ; эту норму иногда называют нормой Чебышева. Для пространства (действительных или комплекснозначных) функций расстояние Чебышева обобщается до равномерной нормы . ${\displaystyle \ell ^{\infty }}$

Смотрите также

• график Кинга
• Геометрия такси

Рекомендации

1. Сайрус. Д. Кантрелл (2000). Современные математические методы для физиков и инженеров . Издательство Кембриджского университета. ISBN 0-521-59827-3.
2. Абелло, Джеймс М.; Пардалос, Панос М.; Ресенде, Маурисио Г.К. , ред. (2002). Справочник по огромным наборам данных . Спрингер. ISBN 1-4020-0489-3.
3. Дэвид М.Дж. Такс; Роберт Дуин; Дик Де Риддер (2004). Классификация, оценка параметров и оценка состояния: инженерный подход с использованием MATLAB . Джон Уайли и сыновья. ISBN 0-470-09013-8.
4. Андре Ланжевен; Дайан Риопель (2005). Логистические системы. Спрингер. ISBN 0-387-24971-0.
5. Зейтц, Чарльз Л. (1989). Перспективные исследования в области СБИС: материалы десятилетней конференции Калифорнийского технологического института по СБИС, март 1989 г. ISBN 9780262192828.