Відстань Чебишова

Відстань Чебишова — метрика максимуму або ${\displaystyle l_{\infty }}$-метрика^[1] на векторному просторі, яка визначає відстань між двома векторами як найбільшу різницю їхніх координат.^[2] Названа на честь російського математика Пафнутія Чебишова.

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Відстань Чебишова між двома полями шахової дошки дорівнює мінімальній кількості ходів, яке необхідне королю, щоб перейти з одного поля в інше.

Визначення

Відстанню Чебишова між n-вимірними числовими векторами називається максимум модуля різниці компонент цих векторів. Відстань Чебишова задає метрику на ${\displaystyle \mathbb {R} ^{n}}$. Ця відстань часто позначається через ${\displaystyle l_{\infty }}$, оскільки є окремим випадком метрик ${\displaystyle l_{p}}$.

${\displaystyle l_{\infty }({\vec {x}},{\vec {y}})=\max _{i=1,\dots ,n}|x_{i}-y_{i}|}$

Назви

Відстань Чебишова називають також метрикою Чебишова, рівномірною метрикою, sup-метрикою і бокс-метрикою; на ${\displaystyle \mathbb {Z} ^{2}}$ вона називається метрикою решітки, метрикою шахової дошки, метрикою ходу короля і 8-метрикою^[3].

Властивості

Куля в цій метриці має форму куба, ребра якого паралельні вісям координат. Серед метрик ${\displaystyle l_{p}}$ метрика Чебишова має кулю найбільшого об'єму при фіксованому радіусі. Одинична куля має об'єм ${\displaystyle 2^{n}}$.

Практичне застосування

Відстань Чебишова використовується в задачах логістики складів^[4], оскільки вона ефективно вимірює час, котрий мостовий кран витрачає на переміщення об'єкта із точки в точку. Це можливо, оскільки кран може рухатися вздовж осей ${\displaystyle x}$ та ${\displaystyle y}$ одночасно, або порізно з однаковою швидкістю вздовж кожної з них.

Також широко використовується в електронних автоматизованих системах технологічної підготовки виробництва (англ. Computer-Aided Manufacturing), зокрема, в алгоритмах оптимізації необхідного часу роботи приладдя. Багато приладів, таких як графопобудовники, свердлильні верстати, фотографопобудовники та інші як правило керуються двома двигунами в напрямках ${\displaystyle x}$ та ${\displaystyle y}$, подібно до мостового крана, що дозволяє застосувати відстань Чебишова для оптимізації часу роботи.^[5]

У сфері машинного навчання ця метрика грає важливу роль у багатьох алгоритмах, де вимірювання відстані є необхідним для аналізу подібності між великими наборами даних чи визначення ступеня відмінності між користувачами в рекомендаційних системах (кластерний аналіз).

Див. також

• Мангеттенська метрика
• Евклідова відстань
• Евклідів простір
• Французька залізнична метрика