Чебышевская дистанция

	а	б	c	d	е	ж	грамм	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	грамм	час

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

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

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

Определение [ править ]

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

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

Это равняется пределу метрики L _p :

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

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

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

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

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

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

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

Свойства [ править ]

В одном измерении все метрики L _p равны - они представляют собой абсолютную величину разницы.

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

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

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

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

Приложения [ править ]

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

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

См. Также [ править ]

Граф короля
Единая норма
Геометрия такси

Ссылки [ править ]

↑ Сайрус. Д. Кантрелл (2000). Современные математические методы для физиков и инженеров . Издательство Кембриджского университета. ISBN 0-521-59827-3.
^ Джеймс М. Абелло, Панос М. Пардалос и Маурисио ГК Ресенде (редакторы) (2002). Справочник по массивным наборам данных . Springer. ISBN 1-4020-0489-3.CS1 maint: multiple names: authors list (link) CS1 maint: extra text: authors list (link)
^ Дэвид MJ Налог; Роберт Дуин; Дик Де Риддер (2004). Классификация, оценка параметров и оценка состояния: инженерный подход с использованием MATLAB . Джон Уайли и сыновья. ISBN 0-470-09013-8.
^ Андре Ланжевен; Дайан Риопель (2005). Логистические системы . Springer. ISBN 0-387-24971-0.
^ Зейтц, Чарльз Л. (1989). Advanced Research in VLSI: Proceedings of the Decennial Caltech Conference on VLSI, March 1989 . ISBN 9780262192828.

Внешние ссылки [ править ]

[1] Сайрус. Д. Кантрелл (2000). Современные математические методы для физиков и инженеров . Издательство Кембриджского университета. ISBN 0-521-59827-3.

[2] Джеймс М. Абелло, Панос М. Пардалос и Маурисио ГК Ресенде (редакторы) (2002). Справочник по массивным наборам данных . Springer. ISBN 1-4020-0489-3.CS1 maint: multiple names: authors list (link) CS1 maint: extra text: authors list (link)

[3] Дэвид MJ Налог; Роберт Дуин; Дик Де Риддер (2004). Классификация, оценка параметров и оценка состояния: инженерный подход с использованием MATLAB . Джон Уайли и сыновья. ISBN 0-470-09013-8.

[4] Андре Ланжевен; Дайан Риопель (2005). Логистические системы . Springer. ISBN 0-387-24971-0.

[5] Зейтц, Чарльз Л. (1989). Advanced Research in VLSI: Proceedings of the Decennial Caltech Conference on VLSI, March 1989 . ISBN 9780262192828.

[1]