大家好，欢迎来到IT知识分享网。
Python学习系列文章：👉 目录 👈
一、概述
国际象棋的棋盘上，一场大战正在进行，“车”横冲直撞，干掉敌人；“皇后”肆意横行，大开杀戒；而国王，只能在自己周围的 “横”、“竖”、“斜” 几个方块里移动。
切比雪夫距离 (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∣
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/10590.html
