闵可夫斯基距离或闵可夫斯基度量是赋范向量空间中的度量,可以看作是欧几里得距离和曼哈顿距离的推广。它以波兰数学家赫尔曼·闵可夫斯基的名字命名。两点之间 p 阶闵可夫斯基距离(其中 p 为整数)
X=(x1,x2,…,xn)和Y=(y1,y2,…,yn)∈Rn
定义为:
D(X,Y)=(i=1∑n∣xi−yi∣p)p1(1)
对于 p≥1,闵可夫斯基距离是根据闵可夫斯基不等式得出的度量。当 p<1 时,(0,0) 和 (1,1) 之间的距离为 21/p>2,但点 (0,1) 与这两个点的距离均为 1。由于这违反了三角不等式,因此对于p<1,它不是度量。但是,只需删除 1 / p 的指数即可获得这些值的度量。得到的度量也是 F 范数。
通常使用闵可夫斯基距离,其中 p 为 1 或 2 ,分别对应于曼哈顿距离和欧几里得距离。 在 p 趋向无穷大的极限情况下,我们得到切比雪夫距离:
p→∞lim(i=1∑n∣xi−yi∣p)p1=i=1maxn∣xi−yi∣
类似地,对于 p 达到负无穷大,我们有:
p→−∞lim(i=1∑n∣xi−yi∣p)p1=i=1minn∣xi−yi∣
闵可夫斯基距离也可以看作是 P 和 Q 之间各分量差异的幂均值的倍数。
Python和C++/C#/Java计算闵可夫斯基距离
给定两个数组 A[] 和 B[] 作为 n 维空间中两个点的位置向量以及一个整数 p,任务是计算这两点之间的闵可夫斯基距离。根据上式(1),假设,输入A[] = {1,2,3,4}, B[] = {5,6,7,8}, P = 3 输出是 6.340,输入A = {1,2,3,4}, B[] = {5,6,7,8} P = 2 ,输出是8。
import math
def minkowski(A, B, P):
X = 0.0
for i in range(len(A)):
X += abs(A[i] - B[i]) ** P
Z = 1.0 / P
return X ** Z
if __name__ == "__main__":
A = [1, 2, 3, 4]
B = [5, 6, 7, 8]
P = 2.0
print(minkowski(A, B, P))
C++计算闵可夫斯基距离
#include<bits/stdc++.h>usingnamespace std; doubleminkowski(constvector<double>& A,constvector<double>& B,double P) { double X =0.0;for (size_t i =0; i <A.size(); ++i) { X +=pow(abs(A[i] -B[i]), P); }double Z =1.0/ P;returnpow(X, Z); } intmain() { vector<double> A = { 1,2,3,4 }; vector<double> B = { 5,6,7,8 };double P =2.0; cout <<minkowski(A, B, P) << endl;return0; }
C#计算闵可夫斯基距离
usingSystem;usingSystem.Collections.Generic; publicclassProgram {staticdoubleMinkowski(List<double> A,List<double> B,double P) {double X =0.0;for (int i =0; i <A.Count; ++i) { X +=Math.Pow(Math.Abs(A[i] -B[i]), P); }double Z =1.0/ P;returnMath.Pow(X, Z); } publicstaticvoidMain() {List<double> A =newList<double> { 1,2,3,4 };List<double> B =newList<double> { 5,6,7,8 };double P =2.0;Console.WriteLine(Minkowski(A, B, P)); } }
Java计算闵可夫斯基距离
importjava.util.ArrayList;importjava.util.List; publicclassMinkowskiDistance { privatestaticdoubleminkowski(List<Double> A,List<Double> B,double P) {double X =0.0;for (int i =0; i <A.size(); ++i) { X +=Math.pow(Math.abs(A.get(i) -B.get(i)), P); }double Z =1.0/ P;returnMath.pow(X, Z); } publicstaticvoidmain(String[] args) {List<Double> A =List.of(1.0,2.0,3.0,4.0);List<Double> B =List.of(5.0,6.0,7.0,8.0);double P =2.0;System.out.println(minkowski(A, B, P)); } }