距离度量的方法有欧式距离,切比雪夫距离、马氏距离、巴氏距离,曼哈顿距离等;
用欧氏距离(也称欧几里德度量),高中所学的两点距离公式就是欧氏距离在二维空间上的公式,也就是欧氏距离的n的值为2的情况.
二维坐标下:
(x1−x2)2+(x3−x4)2\sqrt{(x_1-x_2)^2} \quad + \quad \sqrt{(x_3-x_4)^2} (x1−x2)2+(x3−x4)2
曼哈顿距离:
c=∣x1−x2∣+∣x3−x4∣c=|x_1-x_2|+|x_3-x_4|c=∣x1−x2∣+∣x3−x4∣
从公式定义上看,曼哈顿距离一定是一个非负数,距离最小的情况就是两个点重合,距离为 0,这一点和欧氏距离一样。曼哈顿距离和欧氏距离的意义相近,也是为了描述两个点之间的距离,不同的是曼哈顿距离只需要做加减法,这使得计算机在大量的计算过程中代价更低,而且会消除在开平方过程中取近似值而带来的误差。不仅如此,曼哈顿距离在人脱离计算机做计算的时候也会很方便。
在国际象棋棋盘(图 2)上,有这种横平竖直的格子,描述格子和格子之间的距离可以直接用曼哈顿距离。如 A1 格子到 C4 格子的曼哈顿距离计算如下:
c=|3-1|+|4-1|=5 两个格子之间的曼哈顿距离为 5。
上面的公式只给了二维空间上的曼哈顿距离公式,三维、四维或者更多维度的计算原理是一样。
之所以曼哈顿距离又被称为出租车距离是因为在像纽约曼哈顿区这样的地区有很多由横平竖直的街道所切成的街区(Block),出租车司机计算从一个位置到另一个位置的距离,通常直接用街区的两个坐标分别相减,再相加,这个结果就是他即将开车通过的街区数量,而完全没有必要用欧氏距离来求解——算起来超级麻烦还没有意义,毕竟谁也没办法从欧氏距离的直线上飞过去。如图 3 所示,假设一辆出租车要从上面的圆圈位置走到下面的圆圈位置,无论是左边的线路,还是右边的线路,都要经过 11 个街区,而这个 11 就是曼哈顿距离。
从曼哈顿距离的定义就能看出,曼哈顿距离的创立,与其说有很大的学术意义不如说更多的是应用意义。这也是本书一直想说的一点,数学就在我们身边,它是我们的工具,能帮我们解决问题而不是带来麻烦。
切比雪夫距离
设平面空间内存在两点,它们的坐标为(x1,y1),(x2,y2)
则dis=max(|x1−x2|,|y1−y2|)
即两点横纵坐标差的最大值
如果想进一步了解曼哈顿距离与切比雪夫的互化,点击曼哈顿距离与切比雪夫的互化