Чебышевская дистанция - Chebyshev distance
| а | б | c | d | е | ж | грамм | час | ||
| 8 |        |
8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| а | б | c | d | е | ж | грамм | час | ||
В математике , Чебышева расстояние (или Tchebychev расстояние ), максимальная метрика , или L ∞ метрики является метрикой , определенной на векторном пространстве , где расстояние между двумя векторами является наибольшим из их различий вдоль любой координатной размерности. Он назван в честь Пафнутия Чебышева .
Его также называют расстоянием на шахматной доске , поскольку в игре в шахматы минимальное количество ходов, необходимых королю, чтобы перейти от одного квадрата на шахматной доске к другому, равно расстоянию Чебышева между центрами квадратов, если квадраты имеют длину стороны. один, представленный в двухмерных пространственных координатах с осями, выровненными по краям платы. Например, расстояние Чебышева между f6 и e2 равно 4.
Определение
Расстояние Чебышева между двумя векторами или точками x и y со стандартными координатами и , соответственно, равно
Это равняется пределу метрики L p :
следовательно, она также известна как метрика L ∞ .
Математически расстояние Чебышева - это метрика, индуцированная супремум-нормой или равномерной нормой . Это пример инъективной метрики .
В двух измерениях, то есть в плоской геометрии , если точки p и q имеют декартовы координаты и их расстояние Чебышева равно
В соответствии с этим метрика, А круг из радиуса г , что множество точек с Чебышева расстояния г от центральной точки, представляет собой квадрат, стороны которого имеют длину 2 г и параллельны осям координат.
На шахматной доске, где используется дискретное расстояние Чебышева, а не непрерывное, круг радиуса r представляет собой квадрат со стороной 2 r, отсчитываемой от центров квадратов, и, таким образом, каждая сторона содержит 2 r +1 квадраты; например, круг радиуса 1 на шахматной доске представляет собой квадрат 3 × 3.
Характеристики
В одном измерении все метрики L p равны - они представляют собой абсолютную величину разницы.
Двумерное манхэттенское расстояние имеет «круги», то есть наборы уровней в форме квадратов со сторонами длиной √ 2 r , ориентированные под углом π / 4 (45 °) к осям координат, поэтому плоское расстояние Чебышева может быть рассматривается как эквивалентное вращение и масштабирование (то есть линейное преобразование ) плоского манхэттенского расстояния.
Однако эта геометрическая эквивалентность между метриками L 1 и L ∞ не распространяется на более высокие измерения. Сфера формируется с использованием Чебышевым расстояния как метрика является кубой с каждой гранью , перпендикулярной к одной из осей координат, а сфера формируется с использованием Manhattan расстояния является октаэдром : это двойные многогранники , но среди кубов, только квадрата (и 1 -мерный отрезок) являются самодвойственными многогранниками . Тем не менее верно, что во всех конечномерных пространствах метрики L 1 и L ∞ математически двойственны друг другу.
На сетке (например, на шахматной доске) точки на расстоянии Чебышева, равном 1 точке, являются окрестностью Мура этой точки.
Расстояние Чебышева является предельным случаем расстояния Минковского порядка , когда оно достигает бесконечности .
Приложения
Расстояние Чебышева иногда используется в складской логистике , поскольку оно эффективно измеряет время, необходимое мостовому крану для перемещения объекта (поскольку кран может перемещаться по осям x и y одновременно, но с одинаковой скоростью по каждой оси).
Он также широко используется в электронных CAM- приложениях, в частности, в алгоритмах их оптимизации. Многие инструменты, такие как плоттерные или сверлильные станки, фотоплоттеры и т. Д., Работающие в плоскости, обычно управляются двумя двигателями в направлениях x и y, как и у мостовых кранов.