切比雪夫距離

數學上，切比雪夫距離（Chebyshev distance）或是L_∞度量^[1]是向量空間中的一種度量，二個點之間的距離定義為其各座標數值差的最大值^[2]。以(x₁,y₁)和(x₂,y₂)二點為例，其切比雪夫距離為max(|x₂-x₁|,|y₂-y₁|)。切比雪夫距離得名自俄羅斯數學家切比雪夫。

	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

國際象棋棋盤上二個位置間的切比雪夫距離是指王要從一個位子移至另一個位子需要走的步數。由於王可以往斜前或斜後方向移動一格，因此可以較有效率的到達目的的格子。上圖是棋盤上所有位置距f6位置的切比雪夫距離。

若將國際象棋棋盤放在二維直角座標系中，格子的邊長定義為1，座標的x軸及y軸和棋盤方格平行，原點恰落在某一格的中心點，則王從一個位置走到其他位置需要的步數恰為二個位置的切比雪夫距離，因此切比雪夫距離也稱為棋盤距離^[3]。例如位置F6和位置E2的切比雪夫距離為4。任何一個不在棋盤邊緣的位置，和周圍八個位置的切比雪夫距離都是1。

定義

若二個向量或二個點p 、and q，其坐標分別為${\displaystyle p_{i}}$及${\displaystyle q_{i}}$，則兩者之間的切比雪夫距離定義如下：

${\displaystyle D_{\rm {Chebyshev}}(p,q):=\max _{i}(|p_{i}-q_{i}|).\ }$

這也等於以下L_p度量的極值：

${\displaystyle \lim _{k\to \infty }{\bigg (}\sum _{i=1}^{n}\left|p_{i}-q_{i}\right|^{k}{\bigg )}^{1/k},}$

因此切比雪夫距離也稱為L_∞度量。

以數學的觀點來看，切比雪夫距離是由一致範數（英語：uniform norm）（或稱為上確界範數）所衍生的度量，也是超凸度量的一種。

在平面幾何中，若二點p及q的直角坐標系坐標為 ${\displaystyle (x_{1},y_{1})}$及${\displaystyle (x_{2},y_{2})}$，則切比雪夫距離為

${\displaystyle D_{\rm {Chess}}=\max \left(\left|x_{2}-x_{1}\right|,\left|y_{2}-y_{1}\right|\right).}$

依以上的度量，以任一點為準，和此點切比雪夫距離為r的點會形成一個正方形，其邊長為2r，且各邊都和坐標軸平行。

在棋盤上，使用的是離散的切比雪夫距離，以任一位置為準，和此點切比雪夫距離為r的所有位置也會形成一正方形，若以位置的中心量到其他位置的中心，此正方形的「邊長」為2r，正方形的邊會有2r+1個方格，例如，和一位置切比雪夫距離為1的所有位置會形成一個3×3的正方形。

性質

一維空間中，所有的L_p度量都是一樣的－即為二座標差的絕對值。

二維空間下，和一點的曼哈頓距離L₁為定值r的點也會形成一個正方形，但其邊長為${\displaystyle {\sqrt {2}}r}$，而且正方形的邊和坐標軸會有${\displaystyle {\frac {\pi }{4}}}$（45°）的夾角，因此平面的切比雪夫距離可以視為平面曼哈頓距離旋轉再放大後的結果。

不過上述L₁度量及L_∞度量之間的關係在更高維度的空間不成立。和一點有相等切比雪夫距離的點會形成一個立方體，各面都和坐標軸垂直，而和一點有相等曼哈頓距離的點會形成一個正八面體。

切比雪夫距離也會用在倉儲物流中^[4]。

對一個網格（例如棋盤），和一點的切比雪夫距離為1的點為此點的Moore型鄰居（英語：Moore neighborhood）。

切比雪夫距離等價於p趨於無窮大時的p階明可夫斯基距離。

參見

• 曼哈頓距離
• 賦範向量空間

參考資料

1. Cyrus. D. Cantrell. Modern Mathematical Methods for Physicists and Engineers. Cambridge University Press. 2000. ISBN 0521598273.
2. James M. Abello, Panos M. Pardalos, and Mauricio G. C. Resende (editors). Handbook of Massive Data Sets. Springer. 2002. ISBN 1402004893.
3. David M. J. Tax, Robert Duin, and Dick De Ridder. Classification, Parameter Estimation and State Estimation: An Engineering Approach Using MATLAB. John Wiley and Sons. 2004. ISBN 0470090138.
4. André Langevin and Diane Riopel. Logistics Systems. Springer. 2005 [2011-11-29]. ISBN 0387249710. （原始內容存檔於2014-01-05）.