Расстояние Чебышева
а | б | с | д | и | ж | г | час | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
а | б | с | д | и | ж | г | час |
В математике ( расстояние Чебышева или расстояние Чебышева ), максимальная метрика или L ∞ метрика. [1] — это метрика, определенная в реальном координатном пространстве , где расстояние между двумя точками является наибольшей из их разностей по любому координатному измерению. [2] Назван в честь Пафнутия Чебышева .
Оно также известно как шахматное расстояние , так как в игре в шахматы минимальное количество ходов, необходимое королю для перехода с одной клетки шахматной доски на другую, равно расстоянию Чебышева между центрами клеток, если клетки имеют длину стороны. один, представленный в двумерных пространственных координатах с осями, выровненными по краям доски. [3] Например, расстояние Чебышева между f6 и e2 равно 4.
Определение
[ редактировать ]Расстояние Чебышева между двумя векторами или точками x и y со стандартными координатами и , соответственно,
соответствует пределу Lp метрики Это :
следовательно, она также известна как метрика L ∞ .
Математически расстояние Чебышева — это метрика, индуцированная супремум-нормой или равномерной нормой . Это пример инъективной метрики .
В двух измерениях, т. е. в плоской геометрии , если точки p и q имеют декартовы координаты. и , их расстояние Чебышева равно
В этой метрике круг радиуса от центральной точки, представляет собой r , представляющий собой множество точек на чебышевском расстоянии r квадрат, стороны которого имеют длину 2 r и параллельны осям координат.
На шахматной доске, где используется дискретное расстояние Чебышева, а не непрерывное, круг радиуса r представляет собой квадрат с длиной стороны 2 r, отсчитываемый от центров квадратов, и, таким образом, каждая сторона содержит 2 r +1 квадрат. ; например, круг радиуса 1 на шахматной доске представляет собой квадрат 3×3.
Характеристики
[ редактировать ]В одном измерении все метрики Lp равны – они представляют собой просто абсолютное значение разницы.
Двумерное манхэттенское расстояние имеет «круги», то есть наборы уровней в форме квадратов со сторонами длиной √ 2 r , ориентированными под углом π/4 (45 °) к осям координат, поэтому плоское расстояние Чебышева может быть рассматривается как эквивалент путем вращения и масштабирования (т.е. линейного преобразования ) плоского манхэттенского расстояния.
Однако эта геометрическая эквивалентность между метриками L 1 и L ∞ не распространяется на более высокие измерения. Сфера , образованная с использованием в качестве метрики расстояния Чебышева, представляет собой куб , каждая грань которого перпендикулярна одной из осей координат, а сфера, образованная с использованием манхэттенского расстояния, — октаэдр : это двойственные многогранники , но среди кубов только квадрат (и 1 -мерный отрезок) являются самодвойственными многогранниками . Тем не менее, верно, что во всех конечномерных пространствах метрики L 1 и L ∞ математически двойственны друг другу.
На сетке (например, на шахматной доске) точки на расстоянии Чебышева, равном 1 точке, являются окрестностью Мура этой точки.
Расстояние Чебышева является предельным случаем порядка Расстояние Минковского , когда достигает бесконечности .
Приложения
[ редактировать ]Расстояние Чебышева иногда используется в складской логистике , [4] поскольку он эффективно измеряет время, необходимое мостовому крану для перемещения объекта (поскольку кран может перемещаться по осям x и y одновременно, но с одинаковой скоростью вдоль каждой оси).
Он также широко используется в электронных приложениях автоматизированного производства (CAM) , в частности, в алгоритмах их оптимизации. Многие инструменты, такие как плоттеры или сверлильные станки, фотоплоттеры и т. д., работающие в плоскости, обычно управляются двумя двигателями в направлениях x и y, подобно мостовым кранам. [5]
Обобщения
[ редактировать ]Для пространства последовательностей последовательностей действительных или комплексных чисел бесконечной длины расстояние Чебышева обобщается до -норма ; эту норму иногда называют нормой Чебышева. Для пространства (действительных или комплекснозначных) функций расстояние Чебышева обобщается до равномерной нормы .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Сайрус. Д. Кантрелл (2000). Современные математические методы для физиков и инженеров . Издательство Кембриджского университета. ISBN 0-521-59827-3 .
- ^ Абелло, Джеймс М.; Пардалос, Панос М.; Ресенде, Маурисио Г.К. , ред. (2002). Справочник по огромным наборам данных . Спрингер. ISBN 1-4020-0489-3 .
- ^ Дэвид М.Дж. Такс; Роберт Дуин; Дик Де Риддер (2004). Классификация, оценка параметров и оценка состояния: инженерный подход с использованием MATLAB . Джон Уайли и сыновья. ISBN 0-470-09013-8 .
- ^ Андре Ланжевен; Дайан Риопель (2005). Логистические системы . Спрингер. ISBN 0-387-24971-0 .
- ^ Зейтц, Чарльз Л. (1989). Перспективные исследования в области СБИС: материалы десятилетней конференции Калифорнийского технологического института по СБИС, март 1989 г. ISBN 9780262192828 .