Featured image of post 曼哈顿距离

曼哈顿距离

曼哈顿距离和切比雪夫距离

转自 曼哈顿距离与切比雪夫距离及其相互转化 - 自为风月马前卒

本文只讨论二维空间中的曼哈顿距离与切比雪夫距离

曼哈顿距离

定义

设平面空间内存在两点,它们的坐标为$(x1,y1),(x2,y2)$

则$dis=|x1−x2|+|y1−y2|$

即两点横纵坐标差之和

煮个栗子

img

如图所示,图中$A,B$两点的曼哈顿距离为$AC+BC=4+3=7$

切比雪夫距离

定义

设平面空间内存在两点,它们的坐标为$(x1,y1),(x2,y2)$

则$dis=max(|x1−x2|,|y1−y2|)$

即两点横纵坐标差的最大值

再煮个栗子

img

$dis=max(AC,BC)=AC=4$

两者之间的关系

两者的定义看上去好像毛线关系都没有,但实际上,这两种距离可以相互转化

我们考虑最简单的情况,在一个二维坐标系中,设原点为$(0,0)$

如果用曼哈顿距离表示,则与原点距离为$1$的点会构成一个边长为$\sqrt{2}$的正方形

img

如果用切比雪夫距离表示,则与原点距离为$1$的点会构成一个边长为$2$的正方形

img

事实上,

将一个点

$$ (x,y) $$

的坐标变为

$$ (x+y,x−y) $$

后,原坐标系中的曼哈顿距离 $

$=$$ 新坐标系中的切比雪夫距离

将一个点

$$ (x,y) $$

的坐标变为

$$ (\frac{x+y}2,\frac{x-y}2) $$

后,原坐标系中的切比雪夫距离 $=$ 新坐标系中的曼哈顿距离

用处

切比雪夫距离在计算的时候需要取$max$,往往不是很好优化,对于一个点,计算其他点到该的距离的复杂度为$O(n)$

而曼哈顿距离只有求和以及取绝对值两种运算,我们把坐标排序后可以去掉绝对值的影响,进而用前缀和优化,可以把复杂度降为$O(1)$

例题

所念皆星河
Built with Hugo
主题 StackJimmy 设计

提供全站CDN服务