各种距离

1. 欧几里得距离

给定空间中两个点 (x1,y1){(x_1,y_1)}(x2,y2){(x_2,y_2)};它们之间的欧几里得距离公式为:

(x1x2)2+(y1y2)2\begin{array}{c} \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} \end{array}

即两个点之间的直线距离。本质是向量的 2-范数

2. 曼哈顿距离

给定空间中两个点 (x1,y1){(x_1,y_1)}(x2,y2){(x_2,y_2)};它们之间的曼哈顿距离公式为:

x1x2+y1y2\begin{array}{c} |x_1-x_2|+|y_1-y_2| \end{array}

即两个点之间的水平距离绝对值加上垂直距离的绝对值。本质是向量的 1-范数
在平面上,从原点 OO 引出八条射线,相邻两射线角度均为 45{45^\circ},则将整个平面划分成 8 块区域,对于每一块区域内的点 B(x1,y1){B(x_1,y_1)}C(x2,y2){C(x_2,y_2)}满足:

  • OB<OC{|OB| \lt |OC|},则 BC<OC{|BC| \lt |OC|}(曼哈顿距离),即连接 OOBBCC 三点的最短曼哈顿树为 OBC{O \rightarrow B \rightarrow C}

3. 切比雪夫距离

给定空间中两个点 (x1,y1){(x_1,y_1)}(x2,y2){(x_2,y_2)};它们之间的切比雪夫距离公式为:

max(x1x2,y1y2)\begin{array}{c} max(|x_1-x_2|, |y_1-y_2|) \end{array}

即两点之间横纵坐标距离绝对值的最大值。本质是向量的 \infty-范数

###【曼哈顿距离与切比雪夫距离比较】
如下图所示,矩形 EFGH{EFGH} 是到原点曼哈顿距离为 2 的点的集合,矩形 ABCD{ABCD} 是到原点切比雪夫距离为 2 的点的集合。

4. 闵可夫斯基距离

给定空间中两个点 (x1,y1){(x_1,y_1)}(x2,y2){(x_2,y_2)};它们之间的闵可夫斯基距离公式为:

(x1x2)p+(y1y2)pp\begin{array}{c} \sqrt[p]{(x_1-x_2)^p+(y_1-y_2)^p} \end{array}

本质是向量的范数,pp 取不同的值时对应不同的 pp-范数


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!