距离

欧氏距离

二维空间

定义

欧氏距离，一般也称作欧几里得距离。在平面直角坐标系中，设点的坐标分别为，则两点间的欧氏距离为：

\left | AB \right | = \sqrt{\left ( x_2 - x_1 \right )^2 + \left ( y_2 - y_1 \right )^2}

解释

举个例子，若在平面直角坐标系中，有两点，通过公式，我们很容易得到两点间的欧氏距离：

\left | AB \right | = \sqrt{\left ( 2 - 6 \right )^2 + \left ( 2 - 5 \right )^2} = \sqrt{4^2+3^2} = 5

除此之外，到原点的欧氏距离可以用公式表示为：

|P| = \sqrt{x^2+y^2}

n 维空间

引入

那么，三维空间中两点的欧氏距离公式呢？我们来观察下图。

dis-3-dimensional

我们很容易发现，在 $\triangle ADC$ 中， $\angle ADC = 90^\circ$ ；在 $\triangle ACB$ 中， $\angle ACB = 90^\circ$ 。

\begin{aligned} \therefore ~ |AB| &= \sqrt{|AC|^2+|BC|^2} \\ &= \sqrt{|AD|^2+|CD|^2+|BC|^2} \end{aligned}

定义

由此可得，三维空间中欧氏距离的距离公式为：

\begin{gathered} \left | AB \right | = \sqrt{\left ( x_2 - x_1 \right )^2 + \left ( y_2 - y_1 \right )^2 + \left ( z_2 - z_1 \right )^2} \\ |P| = \sqrt{x^2+y^2+z^2} \end{gathered}

解释

NOIP2017 提高组奶酪就运用了这一知识，可以作为欧氏距离的例题。

以此类推，我们就得到了维空间中欧氏距离的距离公式：对于 $\vec A(x_{11}, x_{12}, \cdots,x_{1n}) ,~ \vec B(x_{21}, x_{22}, \cdots,x_{2n})$ ，有

\begin{aligned} \lVert\overrightarrow{AB}\rVert &= \sqrt{\left ( x_{11} - x_{21} \right )^2 + \left ( x_{12} - x_{22} \right )^2 + \cdot \cdot \cdot +\left ( x_{1n} - x_{2n} \right )^2}\\ &= \sqrt{\sum_{i = 1}^{n}(x_{1i} - x_{2i})^2} \end{aligned}

欧氏距离虽然很有用，但也有明显的缺点。两个整点计算其欧氏距离时，往往答案是浮点型，会存在一定误差。

曼哈顿距离

定义

在二维空间内，两个点之间的曼哈顿距离（Manhattan distance）为它们横坐标之差的绝对值与纵坐标之差的绝对值之和。设点，则之间的曼哈顿距离用公式可以表示为：

解释

观察下图：

manhattan-dis-diff

在间，黄线、橙线都表示曼哈顿距离，而红线、蓝线表示等价的曼哈顿距离，绿线表示欧氏距离。

同样的例子，在下图中的坐标分别为。

manhattan-dis

通过公式，我们很容易得到两点间的曼哈顿距离：

经过推导，我们得到维空间的曼哈顿距离公式为：

\begin{aligned} d(A,B) &= |x_1 - y_1| + |x_2 - y_2| + \cdot \cdot \cdot + |x_n - y_n|\\ &= \sum_{i = 1}^{n}|x_i - y_i| \end{aligned}

性质

除了公式之外，曼哈顿距离还具有以下数学性质：

非负性

曼哈顿距离是一个非负数。

$d(i,j)\geq 0$
统一性

点到自身的曼哈顿距离为。
对称性

到与到的曼哈顿距离相等，且是对称函数。
三角不等式

从点到的直接距离不会大于途经的任何其它点的距离。

$d(i,j)\leq d(i,k)+d(k,j)$

例题

P5098「USACO04OPEN」Cave Cows 3

根据题意，对于式子，我们可以假设 $x_1 - x_2 \geq 0$ ，根据的符号分成两种情况：

$(y_1 - y_2 \geq 0)\rightarrow |x_1-x_2|+|y_1-y_2|=x_1 + y_1 - (x_2 + y_2)$
$(y_1 - y_2 < 0)\rightarrow |x_1-x_2|+|y_1-y_2|=x_1 - y_1 - (x_2 - y_2)$

只要分别求出的最大值和最小值即能得出答案。

参考代码

C++Python

#include <algorithm>
#include <cstdio>
using namespace std;

int main() {
  int n, x, y, minx = 0x7fffffff, maxx = 0, miny = 0x7fffffff, maxy = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &x, &y);
    minx = min(minx, x + y), maxx = max(maxx, x + y);
    miny = min(miny, x - y), maxy = max(maxy, x - y);
  }
  printf("%d\n", max(maxx - minx, maxy - miny));
  return 0;
}

minx = 0x7FFFFFFF
maxx = 0
miny = 0x7FFFFFFF
maxy = 0
n = int(input())
for i in range(1, n + 1):
    x, y = map(lambda x: int(x), input().split())
    minx = min(minx, x + y)
    maxx = max(maxx, x + y)
    miny = min(miny, x - y)
    maxy = max(maxy, x - y)
print(max(maxx - minx, maxy - miny))

其实还有第二种做法，那就是把曼哈顿距离转化为切比雪夫距离求解，最后部分会讲到。

切比雪夫距离

定义

切比雪夫距离（Chebyshev distance）是向量空间中的一种度量，二个点之间的距离定义为其各坐标数值差的最大值。¹

在二维空间内，两个点之间的切比雪夫距离为它们横坐标之差的绝对值与纵坐标之差的绝对值的最大值。设点，则之间的切比雪夫距离用公式可以表示为：

d(A,B) = \max(|x_1 - x_2|, |y_1 - y_2|)

维空间中切比雪夫距离的距离公式可以表示为：

\begin{aligned} d(x,y) &= \max\begin{Bmatrix} |x_1 - y_1|,|x_2 - y_2|,\cdot \cdot \cdot,|x_n - y_n|\end{Bmatrix} \\ &= \max\begin{Bmatrix} |x_i - y_i|\end{Bmatrix}(i \in [1, n])\end{aligned}

解释

仍然是这个例子，下图中的坐标分别为。

Chebyshev-dis

d(A,B) = \max(|20 - 10|, |25 - 10|) = \max(10, 15) = 15

曼哈顿距离与切比雪夫距离的相互转化

过程

首先，我们考虑画出平面直角坐标系上所有到原点的曼哈顿距离为的点。

通过公式，我们很容易得到方程。

将绝对值展开，得到个一次函数，分别是：

\begin{aligned} &y = -x + 1 &(x \geq 0, y \geq 0) \\ &y = x + 1 &(x \leq 0, y \geq 0) \\ &y = x - 1 &(x \geq 0, y \leq 0) \\ &y = -x - 1 &(x \leq 0, y \leq 0) \\ \end{aligned}

将这个函数画到平面直角坐标系上，得到一个边长为 $\sqrt{2}$ 的正方形，如下图所示：

dis-diff-square-1

正方形边界上所有的点到原点的曼哈顿距离都是。

同理，我们再考虑画出平面直角坐标系上所有到原点的切比雪夫距离为的点。

通过公式，我们知道 $\max(|x|,|y|)=1$ 。

我们将式子展开，也同样可以得到条线段，分别是：

\begin{aligned} &y = 1&(-1\leq x \leq 1) \\ &y = -1&(-1\leq x \leq 1) \\ &x = 1,&(-1\leq y \leq 1) \\ &x = -1,&(-1\leq y \leq 1) \\ \end{aligned}

画到平面直角坐标系上，可以得到一个边长为的正方形，如下图所示：

dis-diff-square-2

正方形边界上所有的点到原点的切比雪夫距离都是。

将这两幅图对比，我们会神奇地发现：

这个正方形是相似图形。

证明

所以，曼哈顿距离与切比雪夫距离之间会不会有联系呢？

接下来我们简略证明一下：

假设，

我们把曼哈顿距离中的绝对值拆开，能够得到四个值，这四个值中的最大值是两个非负数之和，即曼哈顿距离。则两点的曼哈顿距离为：

\begin{aligned} d(A,B)&=|x_1 - x_2| + |y_1 - y_2|\\ &=\max\begin{Bmatrix} x_1 - x_2 + y_1 - y_2, x_1 - x_2 + y_2 - y_1,x_2 - x_1 + y_1 - y_2, x_2 - x_1 + y_2 - y_1\end{Bmatrix}\\ &= \max(|(x_1 + y_1) - (x_2 + y_2)|, |(x_1 - y_1) - (x_2 - y_2)|) \end{aligned}

我们很容易发现，这就是两点之间的切比雪夫距离。

所以将每一个点转化为，新坐标系下的切比雪夫距离即为原坐标系下的曼哈顿距离。

同理，两点的切比雪夫距离为：

\begin{aligned} d(A,B)&=\max\begin{Bmatrix} |x_1 - x_2|,|y_1 - y_2|\end{Bmatrix}\\ &=\max\begin{Bmatrix} \left|\dfrac{x_1 + y_1}{2}-\dfrac{x_2 + y_2}{2}\right|+\left|\dfrac{x_1 - y_1}{2}-\dfrac{x_2 - y_2}{2}\right|\end{Bmatrix} \end{aligned}

而这就是 $(\dfrac{x_1 + y_1}{2},\dfrac{x_1 - y_1}{2}), (\dfrac{x_2 + y_2}{2},\dfrac{x_2 - y_2}{2})$ 两点之间的曼哈顿距离。

所以将每一个点转化为 $(\dfrac{x + y}{2},\dfrac{x - y}{2})$ ，新坐标系下的曼哈顿距离即为原坐标系下的切比雪夫距离。

结论

曼哈顿坐标系是通过切比雪夫坐标系旋转 $45^\circ$ 后，再缩小到原来的一半得到的。
将一个点的坐标变为后，原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离。
将一个点的坐标变为 $(\dfrac{x + y}{2},\dfrac{x - y}{2})$ 后，原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。

碰到求切比雪夫距离或曼哈顿距离的题目时，我们往往可以相互转化来求解。两种距离在不同的题目中有不同的优缺点，应该灵活运用。

例题

P4648「IOI2007」pairs 动物对数（曼哈顿距离转切比雪夫距离）

P3964「TJOI2013」松鼠聚会（切比雪夫距离转曼哈顿距离）

最后给出 P5098「USACO04OPEN」Cave Cows 3 的第二种解法：

我们考虑将题目所求的曼哈顿距离转化为切比雪夫距离，即把每个点的坐标变为。

所求的答案就变为 $\max\limits_{i,j\in n}\begin{Bmatrix} \max\begin{Bmatrix} |x_i - x_j|,|y_i - y_j|\end{Bmatrix}\end{Bmatrix}$ 。

现要使得横坐标之差和纵坐标之差最大，只需要预处理出的最大值和最小值即可。

参考代码

C++Python

#include <algorithm>
#include <cstdio>
using namespace std;

int main() {
  int n, x, y, a, b, minx = 0x7fffffff, maxx = 0, miny = 0x7fffffff, maxy = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &a, &b);
    x = a + b, y = a - b;
    minx = min(minx, x), maxx = max(maxx, x);
    miny = min(miny, y), maxy = max(maxy, y);
  }
  printf("%d\n", max(maxx - minx, maxy - miny));
  return 0;
}

minx = 0x7FFFFFFF
maxx = 0
miny = 0x7FFFFFFF
maxy = 0
n = int(input())
for i in range(1, n + 1):
    a, b = map(lambda x: int(x), input().split())
    x = a + b
    y = a - b
    minx = min(minx, x)
    maxx = max(maxx, x)
    miny = min(miny, y)
    maxy = max(maxy, y)
print(max(maxx - minx, maxy - miny))

对比两份代码，我们又能够发现，两种不同的思路，写出来的代码却是完全等价的，是不是很神奇呢？当然，更高深的东西需要大家另行研究。

闵可夫斯基距离

我们定义维空间中两点 $X(x_1, x_2, \dots, x_n)$ ， $Y(y_1, y_2, \dots, y_n)$ 之间的闵可夫斯基距离为：

D(X, Y) = \left(\sum_{i=1}^n \left\vert x_i - y_i \right\vert ^p\right)^{\frac{1}{p}}.

特别的：

当时， $D(X, Y) = \sum_{i=1}^n \left\vert x_i - y_i \right\vert$ 即为曼哈顿距离；
当时， $D(X, Y) = \left(\sum_{i=1}^n (x_i - y_i)^2\right)^{1/2}$ 即为欧几里得距离；
当 $p \to \infty$ 时， $D(X, Y) = \lim_{p \to \infty}\left(\sum_{i=1}^n \left\vert x_i - y_i \right\vert ^p\right) ^{1/p} = \max\limits_{i=1}^n \left\vert x_i - y_i \right\vert$ 即为切比雪夫距离。

注意：当 $p \ge 1$ 时，闵可夫斯基距离才是度量，具体证明参见 Minkowski distance - Wikipedia。

汉明距离

汉明距离是两个字符串之间的距离，它表示两个长度相同的字符串对应位字符不同的数量

我们可以简单的认为对两个串进行异或运算，结果为 1 的数量就是两个串的汉明距离。

参考资料与链接

浅谈三种常见的距离算法，感谢作者 xuxing 的授权。

切比雪夫距离 - 维基百科，自由的百科全书 ↩

本页面最近更新：2024/10/14 16:00:33，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Chrogeek, ChungZH, frank-xjh, Henry-ZHR, hsfzLZH1, partychicken, Planet6174, abc1763613206, countercurrent-time, Enter-tainer, ezoixx130, Haohu Shen, i-Yirannn, i-yyi, iamtwz, Ir1d, ksyx, Marcythm, Menci, mgt, ouuan, scp020, shawlleyw, StudyingFather, swsoyee, Tiger3018, Tiphereth-A, TrisolarisHD, turing0, Xeonacid, xmb3857
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用