Чебышёвское расстояние¶

Чебышёвское расстояние (также расстояние Чебышёва, метрика Чебышёва, метрика L∞, метрика шахматной доски) — это метрика в метрическом пространстве, определяемая как максимум модулей разности координат двух точек. В двумерном пространстве оно соответствует минимальному числу ходов, которое требуется королю в шахматах для перемещения между двумя клетками. Названо в честь русского математика Пафнутия Львовича Чебышёва.

¶Определение

Пусть заданы две точки \( p \) и \( q \) в \( n \)-мерном вещественном пространстве \( \mathbb{R}^n \) с координатами \( p = (p_1, p_2, \dots, p_n) \) и \( q = (q_1, q_2, \dots, q_n) \). Тогда чебышёвское расстояние \( d_\infty(p, q) \) определяется как:

\[ d_\infty(p, q) = \max_{i=1,2,\dots,n} |p_i - q_i|. \]

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

¶Свойства

Чебышёвское расстояние удовлетворяет всем аксиомам метрики:

1. Неотрицательность: \( d_\infty(p, q) \ge 0 \), причём равенство нулю достигается только при \( p = q \).
2. Симметричность: \( d_\infty(p, q) = d_\infty(q, p) \).
3. Неравенство треугольника: \( d_\infty(p, r) \le d_\infty(p, q) + d_\infty(q, r) \) для любых точек \( p, q, r \).

Кроме того, метрика является однородной: \( d_\infty(\lambda p, \lambda q) = |\lambda| d_\infty(p, q) \) для любого вещественного \( \lambda \). Она инвариантна относительно параллельного переноса и отражений.

¶Связь с другими метриками

Чебышёвское расстояние — частный случай метрики Lp (метрики Минковского) при \( p \to \infty \). Для конечного \( p \) метрика Lp определяется как:

\[ d_p(p, q) = \left( \sum_{i=1}^n |p_i - q_i|^p \right)^{1/p}. \]

При \( p = 1 \) получается манхэттенское расстояние, при \( p = 2 \) — евклидово. В пределе при \( p \to \infty \) метрика стремится к чебышёвскому расстоянию. Это можно показать: для любого набора неотрицательных чисел \( a_i \) выполняется

\[ \lim_{p \to \infty} \left( \sum_{i=1}^n a_i^p \right)^{1/p} = \max_i a_i. \]

Таким образом, чебышёвское расстояние является метрикой L∞.

¶Геометрическая интерпретация

В двумерном пространстве единичный шар (множество точек, удалённых от центра не более чем на 1) в метрике Чебышёва представляет собой квадрат со сторонами, параллельными осям координат, с центром в начале координат и длиной стороны 2. В трёхмерном пространстве — куб, в \( n \)-мерном — гиперкуб.

В отличие от евклидова шара (круга) и манхэттенского шара (ромба), граница чебышёвского шара состоит из точек, у которых хотя бы одна координата отличается от центра на 1, а остальные — не более чем на 1.

¶Применение

¶Шахматы и настольные игры

Наиболее известная иллюстрация чебышёвского расстояния — ходы шахматного короля. Король за один ход может переместиться на одну клетку в любом направлении (по горизонтали, вертикали или диагонали). Минимальное количество ходов, необходимое королю для перехода с клетки с координатами \( (x_1, y_1) \) на клетку \( (x_2, y_2) \), равно \( \max(|x_1 - x_2|, |y_1 - y_2|) \), то есть чебышёвскому расстоянию между центрами клеток. Это свойство используется в алгоритмах поиска пути в играх.

¶Компьютерные науки и обработка изображений

В задачах компьютерного зрения и обработки изображений чебышёвское расстояние применяется для сравнения цветовых гистограмм, поиска ближайших соседей и кластеризации. В некоторых алгоритмах, таких как k-ближайших соседей (k-NN) или метод k-средних, выбор метрики влияет на форму кластеров. Метрика Чебышёва порождает кластеры кубической формы, что может быть полезно при работе с данными, где важна максимальная разница по одному признаку.

¶Теория управления и робототехника

В планировании движения мобильных роботов, особенно тех, которые могут двигаться в восьми направлениях (аналогично шахматному королю), чебышёвское расстояние используется для оценки длины пути. Например, в складских роботах, перемещающихся по прямоугольной сетке, метрика позволяет быстро вычислять минимальное количество шагов.

¶Математическая экономика и теория игр

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

¶Кодирование и теория информации

В теории кодирования расстояние Чебышёва используется в некоторых метриках для кодов, исправляющих ошибки, особенно в каналах с помехами, где ошибки могут затрагивать несколько бит одновременно.

¶История

Метрика названа в честь Пафнутия Львовича Чебышёва (1821—1894) — выдающегося русского математика и механика, основателя петербургской математической школы. Чебышёв внёс значительный вклад в теорию чисел, теорию вероятностей, математический анализ и теорию приближений. В частности, он изучал многочлены, наименее уклоняющиеся от нуля (многочлены Чебышёва), которые минимизируют максимальное отклонение от нуля на отрезке — эта задача связана с метрикой L∞. Однако сам термин «чебышёвское расстояние» вошёл в обиход позже, в XX веке, в связи с развитием функционального анализа и теории метрических пространств. В англоязычной литературе метрику часто называют «Chebyshev distance» или «Chessboard distance».

¶Интересные факты

• В метрике Чебышёва окружность (множество точек, равноудалённых от центра) — это квадрат, повёрнутый на 45 градусов относительно осей координат. В манхэттенской метрике, наоборот, окружность — квадрат, повёрнутый на 45 градусов.
• Чебышёвское расстояние является частным случаем метрики Хаусдорфа, используемой в теории множеств.
• В задачах машинного обучения при нормализации данных метрика Чебышёва менее чувствительна к выбросам, чем евклидова, поскольку учитывает только максимальное отклонение, а не сумму квадратов.
• В некоторых алгоритмах сжатия изображений, например, в векторном квантовании, метрика Чебышёва может использоваться для ускорения поиска ближайшего кодового слова.