Python学习系列文章:👉 目录 👈
文章目录
*
– 一、概述
– 二、计算公式
–
+ ① 二维平面上的切比雪夫距离
+ ② n维空间上的切比雪夫距离
; 一、概述
国际象棋的棋盘上,一场大战正在进行,”车”横冲直撞,干掉敌人;”皇后”肆意横行,大开杀戒;而国王,只能在自己周围的 “横”、”竖”、”斜” 几个方块里移动。
切比雪夫距离 (Chebyshev Distance) 研究的就是关于 “国王” 移动的问题,国王从一个格子 (x1,y1) 走到 另一个格子 (x2,y2) 最少需要的步数就是 切比雪夫距离 。
二、计算公式
① 二维平面上的切比雪夫距离
二维平面上的切比雪夫距离就是国王移动问题,比如这里 “国王” 从 (f,3)
移动到 (c,5)
。
最短的距离肯定要 斜 着走的距离最大。因为,斜着走一格就相当于正常 ” 横“、” 竖” 走两格。一步抵两步,当然选斜着的了。
则 ” 斜” 的最大值为 m i n ( ∣ x 1 − x 2 ∣ , ∣ y 1 − y 2 ∣ ) min(|x_{1}-x_{2}|,|y_{1}-y_{2}|)m i n (∣x 1 −x 2 ∣,∣y 1 −y 2 ∣),而剩余的部分则只能用 ” 横” 或 ” 竖” 补齐。
所以,平面上两点A ( x 1 , y 1 ) A(x_{1},y_{1})A (x 1 ,y 1 ) 与 B ( x 2 , y 2 ) B({x_{2},y_{2}})B (x 2 ,y 2 )的 切比雪夫距离 为:d A B = m a x ( ∣ x 1 − x 2 ∣ , ∣ y 1 − y 2 ∣ ) d_{AB}=max(|x_{1}-x_{2}|,|y_{1}-y_{2}|)d A B =m a x (∣x 1 −x 2 ∣,∣y 1 −y 2 ∣)
则上面国王的切比雪夫距离为:d = m a x ( ∣ x 1 − x 2 ∣ , ∣ y 1 − y 2 ∣ ) = m a x ( ∣ 6 − 3 ∣ , ∣ 3 − 5 ∣ ) = 3 \begin{aligned} d &=max(|x_{1}-x_{2}|,|y_{1}-y_{2}|) \ &=max(|6-3|,|3-5|)\ &=3 \end{aligned}d =m a x (∣x 1 −x 2 ∣,∣y 1 −y 2 ∣)=m a x (∣6 −3 ∣,∣3 −5 ∣)=3
; ② n维空间上的切比雪夫距离
推广到 n 维空间则有两点:A ( x 11 , x 12 , . . . , x 1 n ) A(x_{11},x_{12},…,x_{1n})A (x 1 1 ,x 1 2 ,…,x 1 n ) 与 B ( x 21 , x 22 , . . . , x 2 n ) B(x_{21},x_{22},…,x_{2n})B (x 2 1 ,x 2 2 ,…,x 2 n )
则n维空间的切比雪夫距离公式为:
d A B = m a x ∣ x 1 i − x 2 i ∣ d_{AB}=max{|x_{1i}-x_{2i}|}d A B =m a x ∣x 1 i −x 2 i ∣
Original: https://blog.csdn.net/qq_21484461/article/details/125305913
Author: 繁依Fanyi
Title: 距离度量 —— 切比雪夫距离(Chebyshev Distance)
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/614008/
转载文章受原作者版权保护。转载请注明原作者出处!