Jump to content

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

(Перенаправлено из метрики Чебышева )
а б с д и ж г час
8
а8 пять
b8 четыре
с8 три
d8 два
е8 два
f8 два
g8 два
h8 два
а7 пять
b7 четыре
с7 три
d7 два
е7 один
f7 один
g7 one
h7 два
а6 пять
b6 четыре
с6 три
d6 два
е6 один
f6 белый король
g6 один
h6 два
а5 пять
b5 четыре
с5 три
d5 два
е5 один
f5 один
g5 один
h5 два
а4 пять
b4 четыре
с4 три
d4 два
е4 два
f4 два
g4 два
h4 два
а3 пять
б3 четыре
с3 три
d3 три
е3 три
f3 три
g3 три
h3 три
а2 пять
б2 четыре
с2 четыре
d2 четыре
е2 четыре
f2 четыре
g2 четыре
ч2 четыре
а1 пять
б1 пять
с1 пять
d1 пять
е1 пять
f1 пять
g1 пять
ч1 пять
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
а б с д и ж г час
Дискретное расстояние Чебышева между двумя клетками на шахматной доске дает минимальное количество ходов, необходимое королю для перемещения между ними. Это связано с тем, что король может двигаться по диагонали, так что прыжки на меньшее расстояние, параллельное ряду или столбцу, эффективно поглощаются прыжками, охватывающими большее расстояние. Выше указаны чебышевские расстояния каждого квадрата от квадрата f6.

В математике ( расстояние Чебышева или расстояние Чебышева ), максимальная метрика или 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.

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

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

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

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

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

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

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

Приложения

[ редактировать ]

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

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

Обобщения

[ редактировать ]

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

См. также

[ редактировать ]
  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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 099792d1a294ec97924806969014c760__1718227980
URL1:https://arc.ask3.ru/arc/aa/09/60/099792d1a294ec97924806969014c760.html
Заголовок, (Title) документа по адресу, URL1:
Chebyshev distance - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)