切比雪夫距离 技术专题简介

简介

abcdefgh8877665544332211abcdefgh 国际象棋棋盘上二个位置间的切比雪夫距离是指王要从一个位子移至另一个位子需要走的步数。由于王可以往斜前或斜后方向移动一格,因此可以较有效率的到达目的的格子。上图是棋盘上所有位置距f6位置的切比雪夫距离。数学上,切比雪夫距离(Chebyshev distance)或是L∞度量是向量空间中的一种度量,二个点之间的距离定义为其各座标数值差的最大值。以(x1,y1)和(x2,y2)二点为例,其切比雪夫距离为max(|x2-x1|,|y2-y1|)。切比雪夫距离得名自俄罗斯数学家切比雪夫。若将国际象棋棋盘放在二维直角座标系中,格子的边长定义为1,座标的x轴及y轴和棋盘方格平行,原点恰落在某一格的中心点,则王从一个位置走到其他位置需要的步数恰为二个位置的切比雪夫距离,因此切比雪夫距离也称为棋盘距离。例如位置F6和位置E2的切比雪夫距离为4。任何一个不在棋盘边缘的位置,和周围八个位置的切比雪夫距离都是1。

定义

若二个向量或二个点p 、and q,其座标分别为 p i {displaystyle p_{i}} 及 q i {displaystyle q_{i}} ,则两者之间的切比雪夫距离定义如下:

D C h e b y s h e v ( p , q ) := max i ( | p i − q i | ) .   {displaystyle D_{rm {Chebyshev}}(p,q):=max _{i}(|p_{i}-q_{i}|). }

这也等于以下Lp度量的极值:

lim k → ( ∑ i = 1 n | p i − q i | k ) 1 / k , {displaystyle lim _{kto infty }{bigg (}sum _{i=1}^{n}left|p_{i}-q_{i}right|^{k}{bigg )}^{1/k},}

因此切比雪夫距离也称为L∞度量。

以数学的观点来看,切比雪夫距离是由一致范数(英语:uniform norm)(或称为上确界范数)所衍生的度量,也是超凸度量的一种。

在平面几何中,若二点pq的直角坐标系坐标为 ( x 1 , y 1 ) {displaystyle (x_{1},y_{1})} 及 ( x 2 , y 2 ) {displaystyle (x_{2},y_{2})} ,则切比雪夫距离为

D C h e s s = max ( | x 2 − x 1 | , | y 2 − y 1 | ) . {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的正方形。

性质

一维空间中,所有的Lp度量都是一样的-即为二座标差的绝对值。

二维空间下,和一点的曼哈顿距离L1为定值r的点也会形成一个正方形,但其边长为√2r,而且正方形的边和坐标轴会有π/4(45°)的夹角,因此平面的切比雪夫距离可以视为平面曼哈顿距离旋转再放大后的结果。

不过上述L1度量及L∞度量之间的关系在更高维度的空间不成立。和一点有相等切比雪夫距离的点会形成一个立方体,各面都和坐标轴垂直,而和一点有相等曼哈顿距离的点会形成一个正八面体。

切比雪夫距离也会用在仓储物流中。

对一个网格(例如棋盘),和一点的切比雪夫距离为1的点为此点的Moore型邻居(英语:Moore neighborhood)。

Published by

风君子

独自遨游何稽首 揭天掀地慰生平