切比雪夫距离

数学上,切比雪夫距离Chebyshev distance)或是L度量[1]向量空间中的一种度量,二个点之间的距离定义为其各座标数值差的最大值[2]。以(x1,y1)和(x2,y2)二点为例,其切比雪夫距离为max(|x2-x1|,|y2-y1|)。切比雪夫距离得名自俄罗斯数学家切比雪夫

abcdefgh
8
Chessboard480.svg
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的点也会形成一个正方形,但其边长为√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 [2011-11-29]. ISBN 0387249710. (原始内容存档于2014-01-05).