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

Відстань Чебишова — метрика максимуму або $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-вимірними числовими векторами називається максимум модуля різниці компонент цих векторів. Відстань Чебишова задає метрику на $\mathbb {R} ^{n}$ . Ця відстань часто позначається через $l_{\infty }$ , оскільки є окремим випадком метрик $l_{p}$ .

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

Назви

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

Властивості

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

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

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

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

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

Див. також

Примітки

↑ Cyrus. D. Cantrell (2000). Modern Mathematical Methods for Physicists and Engineers. Cambridge University Press. ISBN 0-521-59827-3.
↑ James M. Abello, Panos M. Pardalos, and Mauricio G. C. Resende (editors) (2002). Handbook of Massive Data Sets. Springer. ISBN 1-4020-0489-3.
↑ Олена Деза, Мішель Марі Деза. Глава 19. Відстані на дійсній і цифровій площинах. 19.1. Метрики на дійсній площині // Енциклопедичний словник відстаней = Dictionary of Distances. — М : Наука, 2008. — С. 276. — ISBN 978-5-02-036043-3.
↑ André Langevin; Diane Riopel (2005). Logistics Systems. Springer. ISBN 0-387-24971-0.
↑ Seitz, Charles L. (1989). Advanced Research in VLSI: Proceedings of the Decennial Caltech Conference on VLSI, March 1989. ISBN 9780262192828.

Посилання

В. А. Скворцов, Приклади метричних просторів [Архівовано 10 серпня 2011 у Wayback Machine.], Библіотека «Математическое просвещение» [Архівовано 12 січня 2014 у Wayback Machine.], випуск 9, (2001).

[1] Cyrus. D. Cantrell (2000). Modern Mathematical Methods for Physicists and Engineers. Cambridge University Press. ISBN 0-521-59827-3.

[2] James M. Abello, Panos M. Pardalos, and Mauricio G. C. Resende (editors) (2002). Handbook of Massive Data Sets. Springer. ISBN 1-4020-0489-3.

[3] Олена Деза, Мішель Марі Деза. Глава 19. Відстані на дійсній і цифровій площинах. 19.1. Метрики на дійсній площині // Енциклопедичний словник відстаней = Dictionary of Distances. — М : Наука, 2008. — С. 276. — ISBN 978-5-02-036043-3.

[4] André Langevin; Diane Riopel (2005). Logistics Systems. Springer. ISBN 0-387-24971-0.

[5] Seitz, Charles L. (1989). Advanced Research in VLSI: Proceedings of the Decennial Caltech Conference on VLSI, March 1989. ISBN 9780262192828.

[1]

[2]

[3]

[4]

[5]