切比雪夫距离

维基百科,自由的百科全书
跳转至: 导航搜索
Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
國際象棋棋盤上二個位置間的切比雪夫距离是指要從一個位子移至另一個位子需要走的步數。由於王可以往斜前或斜後方向移動一格,因此可以較有效率的到達目的的格子。上圖是棋盤上所有位置距f6位置的切比雪夫距离。

數學上,切比雪夫距离Chebyshev distance)或是L度量[1]向量空間中的一種度量,二個點之間的距離定義為其各座標數值差的最大值[2]。以(x1,y1)和(x2,y2)二點為例,其切比雪夫距离為max(|x2-x1|,|y2-y1|)。切比雪夫距离得名自俄羅斯數學家切比雪夫

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

定義[编辑]

若二個向量或二個點p 、and q,其座標分別為p_iq_i,則兩者之間的切比雪夫距离定義如下:

D_{\rm Chebyshev}(p,q) := \max_i(|p_i - q_i|).\

這也等於以下Lp度量的極值:

\lim_{k \to \infty} \bigg( \sum_{i=1}^n \left| p_i - q_i \right|^k \bigg)^{1/k},

因此切比雪夫距离也稱為L度量。

以數學的觀點來看,切比雪夫距离是由一致範數英语uniform norm(或稱為上確界範數)所衍生的度量,也是超凸度量英语injective metric space的一種。

平面幾何中,若二點pq的直角坐標系坐標為 (x_1,y_1)(x_2,y_2),則切比雪夫距离為

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的正方形。

性質[编辑]

一維空間中,所有的Lp度量都是一樣的-即為二座標差的絕對值。

二維空間下,和一點的曼哈頓距離L1為定值r的點也會形成一個正方形,但其邊長為√2r,而且正方形的邊和坐標軸會有π/4(45°)的夾角,因此平面的切比雪夫距離可以視為平面曼哈頓距離旋轉再放大後的結果。

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

切比雪夫距离也會用在倉儲物流[4]

對一個網格(例如棋盤),和一點的切比雪夫距離為1的點為此點的Moore型邻居英语Moore neighborhood

參考資料[编辑]

  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. ISBN 0387249710.