距离

距离

欧氏距离：∣AB∣=(x2−x1)2+(y2−y1)2|AB|=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}

曼哈顿距离：d(A,B)=∣x1−x2∣+∣y1−y2∣d(A,B)=|x_{1}-x_{2}|+|y_{1}-y_{2}|

切比雪夫距离：d(A,B)=max(∣x1−x2∣,∣y1−y2∣)d(A,B)=max(|x_{1}-x_{2}|,|y_{1}-y_{2}|)

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

实际做题中常用到曼哈顿距离与切比雪夫距离的转化

曼哈顿距离→切比雪夫距离：(x,y)→(x+y,x−y)(x,y)→(x+y,x-y)

切比雪夫距离→曼哈顿距离：(x+y2,x−y2)→(x,y)(\frac{x+y}{2},\frac{x-y}{2})→(x,y)

Last updated