距离度量 —— 切比雪夫距离（Chebyshev Distance）-繁依Fanyi

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}|)

min(∣x1​−x2​∣,∣y1​−y2​∣)，而剩余的部分则只能用 “横” 或 “竖” 补齐。

所以，平面上两点

A

(

x

1

,

y

1

)

A(x_{1},y_{1})

A(x1​,y1​) 与

B

(

x

2

,

y

2

)

B({x_{2},y_{2}})

B(x2​,y2​)的 切比雪夫距离 为：

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}|)

dAB​=max(∣x1​−x2​∣,∣y1​−y2​∣)

则上面国王的切比雪夫距离为：

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​=max(∣x1​−x2​∣,∣y1​−y2​∣)=max(∣6−3∣,∣3−5∣)=3​

② n维空间上的切比雪夫距离

推广到 n 维空间则有两点：

A

(

x

11

,

x

12

,

.

.

.

,

x

1

n

)

A(x_{11},x_{12},…,x_{1n})

A(x11​,x12​,...,x1n​) 与

B

(

x

21

,

x

22

,

.

.

.

,

x

2

n

)

B(x_{21},x_{22},…,x_{2n})

B(x21​,x22​,...,x2n​)

则n维空间的切比雪夫距离公式为：

d

A

B

=

m

a

x

∣

x

1

i

−

x

2

i

∣

d_{AB}=max{|x_{1i}-x_{2i}|}

dAB​=max∣x1i​−x2i​∣