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

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

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

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

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

Определение

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

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

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

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

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

Математически расстояние Чебышева есть метрика вызванный верхняя норма или же единая норма. Это пример инъективная метрика.

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

{ Displaystyle D _ { rm {Чебышев}} = max left ( left | x_ {2} -x_ {1} right |, left | y_ {2} -y_ {1} right | right ).}

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

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

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

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

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

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

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

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

Приложения

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

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

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

внешняя ссылка

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

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

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

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

[5] [1]

[1]

[2]

[3]

[4]

[5]