距離

在幾何學(xué)里面距離并不單指直線距離，有很多其他的距離沒有那么常用，但考場上可能會出現(xiàn)，為了防止題目不給出定義等，我們有必要認(rèn)識一下各種距離。

后面的角標(biāo)為了清楚直接打到字母后面了

歐幾里得距離

也被稱作歐式距離，在平面直角坐標(biāo)系中，設(shè)有兩點 \(A(x_{1},y_{1}),B(x_{2},y_{2})\)，他們的歐幾里得距離其實就是兩點所連成的線段的長度，初中也講過計算公式：

這個公式怎么來的呢？看一下這張圖：

我們可以看到我們的 \(A,B\) 兩點，我們選了一個中轉(zhuǎn)點 \(C\) 來幫助我們計算 \(|AB|\)，而選擇的 \(C\) 點與 \(A,B\) 構(gòu)成了一個三角形，而我們要求的就是 \(h\)，但是很明顯是可以通過勾股定理來計算的，也就是 \(h=\sqrt{f^{2}+g^{2}}\)，而 \(f\) 的值就是 \(|x_{2}-x_{1}|\)，\(g\) 的值為 \(|y_{2}-y_{1}|\)，平方后絕對值可以不加，所以得到了上面的公式。

當(dāng)然我們不一定只在平面上解決這個問題，有可能會遇到三維空間的問題，也就是立體空間里面求解歐幾里得距離。

技術(shù)有限

我們可以看到我們要求的是 \(A(x1,y1,z1),G(x2,y2,z2)\) 兩點的距離 \(|AG|\)，我們考慮這樣來求解：

如果想要求 \(|AG|\)，我們從圖中可以看出 \(AG\) 是 \(A,G,C\) 所在平面的一個直角三角形的斜邊，而 \(GC\) 的長度我們是可以求出來的，就是 \(|z2-z1|\)，所以問題轉(zhuǎn)化為求 \(AC\) 的長度；\(AC\) 所在的平面為 \(ABCD\) ，我們可以直接用上面的公式來計算出 \(AC^{2}=(y2-y1)^{2}+(x2-y1)^{2}\)，然后跟 \(GC\) 勾股定理一下就可以得出以下公式：

由此我們也可以推廣到多維，但大多數(shù)情況用不到，而且我也不會證

雖然歐幾里得距離很有用，但也有缺點，比如最后得出的答案往往都是帶根號的，會存在一定的誤差，在信息學(xué)里這是一個難以解決的問題。

曼哈頓距離

在二維的空間內(nèi)，兩個點之間的曼哈頓距離為他們橫坐標(biāo)之差的絕對值與縱坐標(biāo)之差的絕對值的和。設(shè) \(A(x1,y1),B(x2,y2)\)，則兩點之間的曼哈頓距離可以表示為

例如上圖中的藍(lán)線為歐幾里得距離，黑線為曼哈頓距離。

當(dāng)然曼哈頓距離也可以通過類似歐幾里得距離的推理出 N 維空間的公式。

設(shè) \(A(x1,x2,\dots,xn),B(y1,y2,\dots,yn)\)，則有：

性質(zhì)

曼哈頓距離有以下數(shù)學(xué)性質(zhì)：

• 非負(fù)性，這一點很明顯就能看出來
• 統(tǒng)一性，點到自身的曼哈頓距離為 \(0\)。
• 對稱性，\(A\) 到 \(B\) 與 \(B\) 到 \(A\) 的曼哈頓距離相等。
• 三角不等式，從 \(i\) 到 \(j\) 的直接距離不會大于途經(jīng)的任何其他點 \(k\) 的距離。\(d(i,j)\le d(i,k)+d(k,j)\)

切比雪夫距離

切比雪夫距離是向量空間中的一種度量，兩個點之間的距離定義為其各坐標(biāo)數(shù)值差的最大值。

在二維空間內(nèi)，兩個點之間的切比雪夫距離為他們橫坐標(biāo)之差的絕對值和縱坐標(biāo)之差的絕對值的最大值。設(shè) \(A(x1,y1),B(x2,y2)\)，則 \(A,B\) 之間的切比雪夫距離可以用公式表示為：

\(n\) 維空間中 \(A(x1,x2,\dots,xn),B(y1,y2,\dots,yn)\) 的切比雪夫距離的公式可以表示為：

曼哈頓距離與切比雪夫距離的相互轉(zhuǎn)化

首先我們考慮曼哈頓距離為 \(1\) 的所有點組成的圖像：

然后再來看看所有切比雪夫距離為 \(1\) 的圖像：

對比一下，你會發(fā)現(xiàn)，這兩個正方形是相似的。

所以我們可以找到曼哈頓距離與切比雪夫距離之間的關(guān)系！

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

欸，這不是 \((x1+y1,x1-y1)\) 與 \((x2+y2,x2-y2)\) 兩點的切比雪夫距離嗎？

所以，將點 \((x,y)\) 轉(zhuǎn)化為 \((x+y,x-y)\)，新坐標(biāo)系下的切比雪夫距離即為原坐標(biāo)系下的曼哈頓距離。

那我們是不是也可以用切比雪夫距離轉(zhuǎn)化成曼哈頓距離呢？

設(shè) \(A(x1,y1),B(x2,y2)\) 的切比雪夫距離為：

為什么呢？

還記得上面的兩張圖嗎？把切比雪夫的轉(zhuǎn) \(45^{\circ}\) 后再縮小至 \(\frac{1}{2}\) 不就是曼哈頓距離的了嗎？所以都帶有 \(\frac{1}{2}\) 這個系數(shù)。

也就是說，將每一個點 \((x,y)\) 轉(zhuǎn)化為 \((\frac{x+y}{2},\frac{x-y}{2})\)，新坐標(biāo)系下的曼哈頓距離即為原坐標(biāo)系下的切比雪夫距離。

結(jié)論

• 曼哈頓坐標(biāo)系是通過切比雪夫坐標(biāo)系旋轉(zhuǎn) \(45^{\circ}\) 后，再縮小到原來的一半得到的。

• 將一個點 \((x,y)\) 的坐標(biāo)轉(zhuǎn)化為 \((x+y,x-y)\) 后，原坐標(biāo)系中的曼哈頓距離等于新坐標(biāo)系中的切比雪夫距離。

• 將一個點 \((x,y)\) 的坐標(biāo)轉(zhuǎn)化為 \((\frac{x+y}{2},\frac{x-y}{2})\) 后，原坐標(biāo)系中的切比雪夫距離等于新坐標(biāo)系中的曼哈頓距離。

碰到求切比雪夫距離或者曼哈頓距離的題目的時候，我們往往可以相互轉(zhuǎn)化來求解。

\(L_{m}\) 距離

一般的，我們定義平面上兩點 \(A(x1,y1),B(x2,y2)\) 之間的 \(L_{m}\) 距離為

容易發(fā)現(xiàn) \(L_{2}\) 就是歐幾里得距離，\(L_{1}\) 就是曼哈頓距離。

漢明距離

漢明距離是兩個字符串之間的距離，它表示兩個長度相同的字符串對應(yīng)位字符不同的數(shù)量

通常用于比較兩個串的差異。

部分參考自https://www.luogu.com.cn/blog/xuxing/Distance-Algorithm文章來源地址http://www.zghlxwxcb.cn/news/detail-460024.html

到了這里，關(guān)于題目中常見的幾種距離的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！