距離

歐氏距離

二維空間

定義

歐氏距離，一般也稱作歐幾里得距離。在平面直角座標系中，設點 \(A,B\) 的座標分別為 \(A(x_1,y_1),B(x_2,y_2)\)，則兩點間的歐氏距離為：

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

解釋

舉個例子，若在平面直角座標系中，有兩點 \(A(6,5),B(2,2)\)，通過公式，我們很容易得到 \(A,B\) 兩點間的歐氏距離：

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

除此之外，\(P(x,y)\) 到原點的歐氏距離可以用公式表示為：

\[ |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 提高組奶酪就運用了這一知識，可以作為歐氏距離的例題。

以此類推，我們就得到了 \(n\) 維空間中歐氏距離的距離公式：對於 \(\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）為它們橫座標之差的絕對值與縱座標之差的絕對值之和。設點 \(A(x_1,y_1),B(x_2,y_2)\)，則 \(A,B\) 之間的曼哈頓距離用公式可以表示為：

\[ d(A,B) = |x_1 - x_2| + |y_1 - y_2| \]

解釋

觀察下圖：

manhattan-dis-diff

在 \(A,B\) 間，黃線、橙線都表示曼哈頓距離，而紅線、藍線表示等價的曼哈頓距離，綠線表示歐氏距離。

同樣的例子，在下圖中 \(A,B\) 的座標分別為 \(A(25,20),B(10,10)\)。

manhattan-dis

通過公式，我們很容易得到 \(A,B\) 兩點間的曼哈頓距離：

\[ d(A,B) = |20 - 10| + |25 - 10| = 10 + 15 = 25 \]

經過推導，我們得到 \(n\) 維空間的曼哈頓距離公式為：

\[ \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\)
統一性

點到自身的曼哈頓距離為 \(0\)。

\(d(i,i) = 0\)
對稱性

\(A\) 到 \(B\) 與 \(B\) 到 \(A\) 的曼哈頓距離相等，且是對稱函數。

\(d(i,j) = d(j,i)\)
三角不等式

從點 \(i\) 到 \(j\) 的直接距離不會大於途經的任何其它點 \(k\) 的距離。

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

例題

P5098「USACO04OPEN」Cave Cows 3

根據題意，對於式子 \(|x_1-x_2|+|y_1-y_2|\)，我們可以假設 \(x_1 - x_2 \geq 0\)，根據 \(y_1 - y_2\) 的符號分成兩種情況：

\((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)\)

只要分別求出 \(x+y, x-y\) 的最大值和最小值即能得出答案。

參考代碼

C++Python

#include <bits/stdc++.h>
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）是向量空間中的一種度量，二個點之間的距離定義為其各座標數值差的最大值。¹

在二維空間內，兩個點之間的切比雪夫距離為它們橫座標之差的絕對值與縱座標之差的絕對值的最大值。設點 \(A(x_1,y_1),B(x_2,y_2)\)，則 \(A,B\) 之間的切比雪夫距離用公式可以表示為：

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

\(n\) 維空間中切比雪夫距離的距離公式可以表示為：

\[ \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} \]

解釋

仍然是這個例子，下圖中 \(A,B\) 的座標分別為 \(A(25,20),B(10,10)\)。

Chebyshev-dis

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

曼哈頓距離與切比雪夫距離的相互轉化

過程

首先，我們考慮畫出平面直角座標系上所有到原點的曼哈頓距離為 \(1\) 的點。

通過公式，我們很容易得到方程 \(|x| + |y| = 1\)。

將絕對值展開，得到 \(4\) 個一次函數，分別是：

\[ \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} \]

將這 \(4\) 個函數畫到平面直角座標系上，得到一個邊長為 \(\sqrt{2}\) 的正方形，如下圖所示：

dis-diff-square-1

正方形邊界上所有的點到原點的曼哈頓距離都是 \(1\)。

同理，我們再考慮畫出平面直角座標系上所有到原點的切比雪夫距離為 \(1\) 的點。

通過公式，我們知道 \(\max(|x|,|y|)=1\)。

我們將式子展開，也同樣可以得到可以得到 \(4\) 條線段，分別是：

\[ \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} \]

畫到平面直角座標系上，可以得到一個邊長為 \(2\) 的正方形，如下圖所示：

dis-diff-square-2

正方形邊界上所有的點到原點的切比雪夫距離都是 \(1\)。

將這兩幅圖對比，我們會神奇地發現：

這 \(2\) 個正方形是相似圖形。

證明

所以，曼哈頓距離與切比雪夫距離之間會不會有聯繫呢？

接下來我們簡略證明一下：

假設 \(A(x_1,y_1),B(x_2,y_2)\)，

我們把曼哈頓距離中的絕對值拆開，能夠得到四個值，這四個值中的最大值是兩個非負數之和，即曼哈頓距離。則 \(A,B\) 兩點的曼哈頓距離為：

\[ \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} \]

我們很容易發現，這就是 \((x_1 + y_1,x_1 - y_1), (x_2 + y_2,x_2 - y_2)\) 兩點之間的切比雪夫距離。

所以將每一個點 \((x,y)\) 轉化為 \((x + y, x - y)\)，新座標系下的切比雪夫距離即為原座標系下的曼哈頓距離。

同理，\(A,B\) 兩點的切比雪夫距離為：

\[ \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})\) 兩點之間的曼哈頓距離。

所以將每一個點 \((x,y)\) 轉化為 \((\dfrac{x + y}{2},\dfrac{x - y}{2})\)，新座標系下的曼哈頓距離即為原座標系下的切比雪夫距離。

結論

曼哈頓座標系是通過切比雪夫座標系旋轉 \(45^\circ\) 後，再縮小到原來的一半得到的。
將一個點 \((x,y)\) 的座標變為 \((x + y, x - y)\) 後，原座標系中的曼哈頓距離等於新座標系中的切比雪夫距離。
將一個點 \((x,y)\) 的座標變為 \((\dfrac{x + y}{2},\dfrac{x - y}{2})\) 後，原座標系中的切比雪夫距離等於新座標系中的曼哈頓距離。

碰到求切比雪夫距離或曼哈頓距離的題目時，我們往往可以相互轉化來求解。兩種距離在不同的題目中有不同的優缺點，應該靈活運用。

例題

P4648「IOI2007」pairs 動物對數（曼哈頓距離轉切比雪夫距離）

P3964「TJOI2013」松鼠聚會（切比雪夫距離轉曼哈頓距離）

最後給出 P5098「USACO04OPEN」Cave Cows 3 的第二種解法：

我們考慮將題目所求的曼哈頓距離轉化為切比雪夫距離，即把每個點的座標 \((x,y)\) 變為 \((x + y, x - y)\)。

所求的答案就變為 \(\max\limits_{i,j\in n}\begin{Bmatrix} \max\begin{Bmatrix} |x_i - x_j|,|y_i - y_j|\end{Bmatrix}\end{Bmatrix}\)。

現要使得橫座標之差和縱座標之差最大，只需要預處理出 \(x,y\) 的最大值和最小值即可。

參考代碼

C++Python

#include <bits/stdc++.h>
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))

對比兩份代碼，我們又能夠發現，兩種不同的思路，寫出來的代碼卻是完全等價的，是不是很神奇呢？當然，更高深的東西需要大家另行研究。

閔可夫斯基距離

我們定義 \(n\) 維空間中兩點 \(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}}. \]

特別的：

當 \(p=1\) 時，\(D(X, Y) = \sum_{i=1}^n \left\vert x_i - y_i \right\vert\) 即為曼哈頓距離；
當 \(p=2\) 時，\(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 的授權。

切比雪夫距離 - 維基百科，自由的百科全書 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Chrogeek, frank-xjh, ChungZH, hsfzLZH1, Marcythm, Planet6174, partychicken, i-Yirannn
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用