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

Расстояние Чебышёва — это метрика, задаваемая в многомерном векторном пространстве, при которой расстояние между двумя точками определяется как максимальная абсолютная разность их координат по любому измерению. Является частным случаем метрики \( L_p \) при \( p \to \infty \) и относится к классу функций расстояния, используемых в математическом анализе, теории приближений, вычислительной геометрии и машинном обучении.

Определение и формальное описание

Пусть даны два вектора \( \mathbf{x} = (x_1, x_2, \dots, x_n) \) и \( \mathbf{y} = (y_1, y_2, \dots, y_n) \) в \( n \)-мерном действительном пространстве \( \mathbb{R}^n \). Расстояние Чебышёва \( d_\infty(\mathbf{x}, \mathbf{y}) \) определяется как предел нормы \( L_p \):

\[ d_\infty(\mathbf{x}, \mathbf{y}) = \lim_{p \to \infty} \left( \sum_{i=1}^n |x_i - y_i|^p \right)^{1/p} = \max_{i=1,\dots,n} |x_i - y_i|. \]

Иными словами, это наибольшее значение разности по модулю среди всех компонент векторов.

Свойства метрики

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

• Неотрицательность: \( d_\infty(\mathbf{x}, \mathbf{y}) \ge 0 \), причём равенство нулю только при \( \mathbf{x} = \mathbf{y} \).
• Симметричность: \( d_\infty(\mathbf{x}, \mathbf{y}) = d_\infty(\mathbf{y}, \mathbf{x}) \).
• Неравенство треугольника: \( d_\infty(\mathbf{x}, \mathbf{z}) \le d_\infty(\mathbf{x}, \mathbf{y}) + d_\infty(\mathbf{y}, \mathbf{z}) \).

От других распространённых метрик, таких как евклидова (L₂) или манхэттенская (L₁), расстояние Чебышёва отличается тем, что учитывает только одно «самое удалённое» измерение, игнорируя остальные.

История

Метрика получила название в честь русского математика Пафнутия Львовича Чебышёва (1821—1894). Сам Чебышёв не вводил эту метрику явно, однако его работы по теории приближений функций, особенно по равномерному (чебышёвскому) приближению, заложили её математическую основу. В задаче наилучшего равномерного приближения функции на отрезке расстояние между функцией и приближающим многочленом измеряется именно как максимальное отклонение — то есть как расстояние Чебышёва в пространстве непрерывных функций. В современной математической литературе эта метрика также известна как равномерная метрика (uniform metric) или \( l_\infty \)-метрика.

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

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

Эта геометрия отличает метрику от евклидовой (круг) и манхэттенской (ромб, повёрнутый на 45°). В контексте комбинаторной геометрии расстояние Чебышёва также называют метрикой шахматной доски или метрикой короля (Chebyshev distance, king move metric), поскольку наименьшее число ходов, за которое король в шахматах может переместиться между двумя полями, равно расстоянию Чебышёва между их (целочисленными) координатами.

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

Расстояние Чебышёва является предельным случаем для семейства метрик \( L_p \). При возрастании параметра \( p \) вклад наибольшего по модулю отклонения становится всё более доминирующим, и при \( p \to \infty \) метрика \( L_p \) совпадает с \( L_\infty \). Важным следствием является неравенство:

\[ \max_i |x_i - y_i| \le \left( \sum_{i=1}^n |x_i - y_i|^p \right)^{1/p} \le n^{1/p} \max_i |x_i - y_i|, \]

которое при \( p \to \infty \) даёт сходимость \( L_p \)-метрик к расстоянию Чебышёва.

Применение

1. Теория приближений и численный анализ

В задаче равномерного приближения непрерывных функций многочленами (аппроксимация Чебышёва) минимизируется максимальное уклонение — то есть расстояние Чебышёва между функцией и многочленом. Это лежит в основе построения многочленов Чебышёва, которые имеют минимальное максимальное отклонение от нуля на отрезке \([-1, 1]\) среди всех полиномов с заданным старшим коэффициентом. Данный подход применяется при интерполяции, численном интегрировании и фильтрации сигналов.

2. Машинное обучение и анализ данных

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

3. Обработка изображений и компьютерное зрение

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

4. Логистика и транспортные задачи

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

5. Шахматы и игровые алгоритмы

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

6. Целочисленные решётки и комбинаторная геометрия

В задачах теории кодирования и целочисленной оптимизации расстояние Чебышёва на решётке \( \mathbb{Z}^n \) называется \( L_\infty \)-расстоянием. Оно используется при анализе кодов, исправляющих ошибки в равномерной метрике, и в задачах построения упаковок гиперкубов.

Сравнение с другими метриками (таблица)

Примеры вычислений

Пример 1. Даны точки \( A(3, 7) \) и \( B(5, 4) \). Разности по координатам: \( |3-5| = 2 \), \( |7-4| = 3 \). Максимум — 3. Расстояние Чебышёва: \( d_\infty(A, B) = 3 \).

Пример 2. В трёхмерном пространстве точки \( C(1, 0, -2) \) и \( D(1, 4, 6) \). Разности: \( |1-1| = 0 \), \( |0-4| = 4 \), \( |-2-6| = 8 \). \( d_\infty(C, D) = 8 \).

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

• В честь Пафнутия Чебышёва названы также многочлены Чебышёва, неравенство Чебышёва в теории вероятностей, фильтры Чебышёва в электротехнике и ряд других математических объектов.
• Метрика Чебышёва является ультраметрикой только в тривиальном случае одномерного пространства (если \( n = 1 \), то она совпадает с обычным расстоянием как модулем разности и удовлетворяет усиленному неравенству треугольника). В размерностях \( n \geq 2 \) она ультраметрикой не является.
• В контексте машинного обучения при работе с категориальными признаками расстояние Чебышёва может быть менее чувствительным к выбору нормализации, чем евклидово.

Источники

• Чебышёв П. Л. Избранные труды. — М.: Издательство АН СССР, 1955.
• Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — М.: Наука, 1989.
• Рокафеллар Р. Выпуклый анализ. — М.: Мир, 1973.
• Deza E., Deza M. Encyclopedia of Distances. — Springer, 2009.