切比雪夫距離

用手机看条目

出自 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

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