切比雪夫距離

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

abcdefgh
8
a8 five
b8 four
c8 three
d8 two
e8 two
f8 two
g8 two
h8 two
a7 five
b7 four
c7 three
d7 two
e7 one
f7 one
g7 one
h7 two
a6 five
b6 four
c6 three
d6 two
e6 one
f6 white king
g6 one
h6 two
a5 five
b5 four
c5 three
d5 two
e5 one
f5 one
g5 one
h5 two
a4 five
b4 four
c4 three
d4 two
e4 two
f4 two
g4 two
h4 two
a3 five
b3 four
c3 three
d3 three
e3 three
f3 three
g3 three
h3 three
a2 five
b2 four
c2 four
d2 four
e2 four
f2 four
g2 four
h2 four
a1 five
b1 five
c1 five
d1 five
e1 five
f1 five
g1 five
h1 five
8
77
66
55
44
33
22
11
abcdefgh
國際象棋棋盤上二個位置間的切比雪夫距離是指要從一個位子移至另一個位子需要走的步數。由於王可以往斜前或斜後方向移動一格,因此可以較有效率的到達目的的格子。上圖是棋盤上所有位置距f6位置的切比雪夫距離。

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

定義

編輯

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

 

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

 

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

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

平面幾何中,若二點pq的直角坐標系坐標為   ,則切比雪夫距離為

 

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

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

性質

編輯

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

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

不過上述L1度量及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).