曼哈顿相似性算法，也称为曼哈顿距离或L1距离，是一种衡量两个点在网格状空间中差异的度量方法。它模拟了在曼哈顿这样的城市中，只能沿着街道网格移动而无法直线穿越的路径长度2，因此得名。与欧几里得距离不同，曼哈顿距离不考虑对角线移动的可能性，而是将移动限制在垂直和水平方向上，这使得它在特定场景下具有独特优势。
一、什么是曼哈顿距离？
曼哈顿距离，也称作城市街区距离或L1距离，是两点在标准坐标系上的绝对轴距之和。
简单来说，想象你在一个规划整齐的棋盘式城市（比如曼哈顿）里，你不能斜着穿过建筑街区，只能沿着街道行走。那么，从一点到另一点的最短路径，就是沿着垂直的街道走，其行走的总距离就是曼哈顿距离。
![]()
三、一个简单的例子
假设我们在一个二维网格上有两个点：
- 点 A 的坐标是 (1, 1)
- 点 B 的坐标是 (4, 5)
那么，A 和 B 之间的曼哈顿距离计算如下：
d = |1 - 4| + |1 - 5| = | -3 | + | -4 | = 3 + 4 = 7
这意味着，如果你从A点出发，只能水平或垂直移动，到达B点最少需要走7个单位长度。
四、与欧几里得距离的对比
为了更好地理解曼哈顿距离，我们经常将它和我们最熟悉的欧几里得距离（即直线距离）进行比较。
特征 | 曼哈顿距离 | 欧几里得距离 |
定义 | 绝对轴距之和 | 两点间的直线距离 |
公式 | ||
几何意义 | 只能沿坐标轴方向移动的路径长度 | “最短路径”或“乌鸦飞行的距离” |
别称 | L1距离、城市街区距离 | L2距离 |
值的大小 | 在同一组点中，曼哈顿距离通常大于或等于欧氏距离 | 在同一组点中，欧氏距离通常小于或等于曼哈顿距离 |
继续上面的例子：
- A(1,1), B(4,5)
- 曼哈顿距离= 7
可以看到，曼哈顿距离（7）确实大于欧氏距离（5）。
五、应用场景
曼哈顿距离因其独特的性质，在许多领域有广泛应用：
- 城市规划与交通导航：
- 在棋盘式道路布局的城市中，计算两点间的实际驾驶或步行距离非常有用。计算机科学：
- 数据结构与算法：在棋盘类游戏（如八数码、国际象棋）中，常用曼哈顿距离作为启发式搜索（如A*算法）的评估函数。
- 图像处理：在数字图像中，像素点位于网格上，曼哈顿距离常用于计算两个像素之间的差异，或进行形态学操作。
- 数据挖掘与机器学习：
- 在聚类算法（如K-Means）和分类算法（如K-近邻算法K-NN）中，曼哈顿距离可以作为一种距离度量。当数据特征在高维空间中具有高度相关性时，使用曼哈顿距离有时能比欧氏距离获得更好的效果，因为它对异常值不那么敏感。
- 其他领域：
- 在电路设计（如VLSI布局布线）中，连接元件的导线通常只能水平和垂直走线，此时线长就是曼哈顿距离。
六、可视化：等距离线
一个有趣的方式来理解不同距离度量是观察它们的“等距离线”——即到中心点距离相等的所有点构成的图形。
- 曼哈顿距离的等距离线：是一个旋转了45度的正方形（菱形）。
- 欧几里得距离的等距离线：是一个标准的圆形。
总结
曼哈顿距离是一个直观且计算简便的距离度量方式，它描绘了一个在网格状约束下的世界。虽然它不是空间中最短的物理路径，但在许多现实世界和计算问题中，它比欧几里得距离更能准确地反映实际的“成本”或“距离”。
