切比雪夫距离

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

切比雪夫距离(Chebyshev Distance)

目录

什么是切比雪夫距离

  数学上,切比雪夫距离或是L_\infty度量是向量空间中的一种度量,二个点之间的距离定义为其各座标数值差的最大值。以(x1,y1)(x2,y2)二点为例,其切比雪夫距离为max\left({\left|{x_2-x_1}\right|,\left|{y_2-y_1}\right|}\right)。切比雪夫距离得名自俄罗斯数学家切比雪夫。以数学的观点来看,切比雪夫距离是由一致范数(uniform norm)(或称为上确界范数)所衍生的度量,也是超凸度量(injective metric space)的一种。

  若将国际象棋棋盘放在二维直角座标系中,格子的边长定义为1,座标的x轴及y轴和棋盘方格平行,原点恰落在某一格的中心点,则王从一个位置走到其他位置需要的步数恰为二个位置的切比雪夫距离,因此切比雪夫距离也称为棋盘距离。例如位置F6和位置E2的切比雪夫距离为4。任何一个不在棋盘边缘的位置,和周围八个位置的切比雪夫距离都是1。

国际象棋棋盘上二个位置间的切比雪夫距离是指王要从一个位子移至另一个位子需要走的步数。由于王可以往斜前或斜后方向移动一格,因此可以较有效率的到达目的的格子。上图是棋盘上所有位置距f6位置的切比雪夫距离。
放大
国际象棋棋盘上二个位置间的切比雪夫距离是指王要从一个位子移至另一个位子需要走的步数。由于王可以往斜前或斜后方向移动一格,因此可以较有效率的到达目的的格子。上图是棋盘上所有位置距f6位置的切比雪夫距离。

切比雪夫距离的定义

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

  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_\infty度量。

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

  在平面几何中,若二点p及q的直角坐标系坐标为(x1,y1)(x2,y2),则切比雪夫距离为

  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的点也会形成一个正方形,但其边长为\sqrt{2}r,而且正方形的边和坐标轴会有π/4(45°)的夹角,因此平面的切比雪夫距离可以视为平面曼哈顿距离旋转再放大后的结果。

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

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

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

相关条目

本条目对我有帮助1
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您认为本条目还有待完善,需要补充新内容或修改错误内容,请编辑条目

本条目由以下用户参与贡献

otf125.

评论(共0条)

提示:评论内容为网友针对条目"切比雪夫距离"展开的讨论,与本站观点立场无关。

发表评论请文明上网,理性发言并遵守有关规定。

打开APP

以上内容根据网友推荐自动排序生成