曼哈顿距离（曼哈顿距离和欧几里得距离）

苦行僧

曼哈顿距离计算公式
曼哈顿距离计算公式：d(i，j)=|xi-xj|+|yi-yj|。
曼哈顿距离是由十九世纪的赫尔曼·闵可夫斯基所创词汇，是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。
曼哈顿距离不是距离不变量，当坐标轴变动时，点间的距离就会不同。曼哈顿距离示意图在早期的计算机图形学中，屏幕是由像素构成，是整数，点的坐标也一般是整数，原因是浮点运算很昂贵，很慢而且有误差。
如果直接使用AB的欧氏距离，则必须要进行浮点运算，如果使用AC和CB，则只要计算加减法即可，这就大大提高了运算速度，而且不管累计运算多少次，都不会有误差。
曼哈顿距离是两点在南北方向上的距离加上在东西方向上的距离，主要用来计算两个点在标准坐标系上的绝对轴距总和。计算公式是d(i,j)=|xi-xj|+|yi-yj|。曼哈顿距离具有非负性、同一性、对称性、三角不等式等数学性质。
要注意的是，曼哈顿距离依赖坐标系统的转度，而非系统在坐标轴上的平移或映射。

M-各种距离定义
一般而言，定义一个距离函数  , 需要满足下面几个准则：
   1).   ，即到自己的距离为0
   2).   ，距离非负
   3).   ，对称性: 如果 A 到 B 距离是  ，那么 B 到 A 的距离也应该是  
   4).   ， 三角形法则: (两边之和大于第三边)
在数学中， 欧几里得距离 或 欧几里得度量 是欧几里得空间中两点间“普通”（即直线）距离。使用这个距离，欧氏空间成为度量空间。相关联的范数称为欧几里得范数。
在欧几里得空间中，点  ，  之间的欧氏距离为：
欧式空间中的两个点可以看做空间中的两个以原点为起始点的向量，则向量  的自然长度即向量的模长，为该点到原点的距离：
它是一个纯数值。在欧几里得度量下，两点之间线段最短。
  曼哈顿距离 (Manhattan distance or Manhattan length)十九世纪的赫尔曼·闵可夫斯基所创辞汇，为欧几里得几何度量空间的几何学之用语，用以标明两个点上在标准坐标系上的绝对轴距之总和。
在直角坐标系的n维实向量空间中，两个向量  ,  的曼哈顿距离  为两个点连成的线段在各坐标轴上的投影之和，表示为：
例如在平面上，坐标  的点  与坐标  的点  的曼哈顿距离为：  
要注意的是，曼哈顿距离依赖座标系统的旋转，而非系统在座标轴上的平移或映射。
曼哈顿距离下的圆由与欧几里得几何中不同的度量来确定，圆的形状也发生变化。 一个圆是由从圆心向各个 固定曼哈顿距离 标示出来的点围成的区域，因此其形状为正方形，其侧面与坐标轴成45°角。
当使用欧几里得度量时，每边的长度为  ，其中  是圆的半径，但在曼哈顿距离下每条边长度为  。 因此，圆的周长为  。 因此，在此几何中，类似于  的几何模拟的值是4。而在直角坐标系中单位圆的公式为  ，在极坐标系中公式为  。
计程车几何学满足除了SAS全等定理之外的希尔伯特几何公理。
如果有一群圆，且任两圆皆相交，则整群圆必在某点相交；因此曼哈顿距离会形成一个超凸度量空间。对一个半径为  的 圆 来说，这个正方形的圆每边长  。此'"圆"的半径  对切比雪夫距离（  空间）的二维平面来说，也是一个对座标轴来说边长为  的正方形，因此二维切比雪夫距离可视为等同于旋转且放大过的二维曼哈顿距离。然而这种介于  与  的相等关系并不能延伸到更高的维度。
国际象棋棋子的移动
   压缩感测
   频率分布的差异
数学上， 切比雪夫距离 （ Chebyshev distance ）或是   度量 是向量空间中的一种度量，二个点之间的距离定义为其各座标数值差的最大值。以  和  二点为例，其切比雪夫距离为  。切比雪夫距离得名自俄罗斯数学家切比雪夫。
若将国际象棋棋盘放在二维直角座标系中，格子的边长定义为1，座标的x轴及y轴和棋盘方格平行，原点恰落在某一格的中心点，则王从一个位置走到其他位置需要的步数恰为二个位置的切比雪夫距离，因此切比雪夫距离也称为 棋盘距离 。例如位置F6和位置E2的切比雪夫距离为4。任何一个不在棋盘边缘的位置，和周围八个位置的切比雪夫距离都是1。
若二个向量或二个点  、  ，其座标分别为  、  ，则两者之间的切比雪夫距离定义如下：  .
这也等于以下L p 度量的极值：  ，
因此切比雪夫距离也称为  度量。以数学的观点来看，切比雪夫距离是由一致范数（或称为上确界范数）所衍生的度量，也是超凸度量的一种。
在平面几何中，若二点 p 及 q 的直角坐标系坐标为  、  ，则切比雪夫距离为  .
依以上的度量，以任一点为准，和此点切比雪夫距离为r的点会形成一个正方形，其边长为  ，且各边都和坐标轴平行。
在棋盘上，使用的是离散的切比雪夫距离，以任一位置为准，和此点切比雪夫距离为r的所有位置也会形成一正方形，若以位置的中心量到其他位置的中心，此正方形的“边长”为  ，正方形的边会有  个方格，例如，和一位置切比雪夫距离为1的所有位置会形成一个3×3的正方形。
一维空间中，所有的  度量都是一样的－即为二座标差的绝对值。
二维空间下，和一点的曼哈顿距离  为定值  的点也会形成一个正方形，但其边长为  ，而且正方形的边和坐标轴会有  （45°）的夹角，因此平面的切比雪夫距离可以视为平面曼哈顿距离旋转再放大后的结果。
不过上述  度量及  度量之间的关系在更高维度的空间不成立。和一点有相等切比雪夫距离的点会形成一个立方体，各面都和坐标轴垂直，而和一点有相等曼哈顿距离的点会形成一个正八面体。
对一个网格（例如棋盘），和一点的切比雪夫距离为1的点为此点的Moore型邻居。
当  达到无穷大时，切比雪夫距离是Minkowski距离的极限情况。
切比雪夫距离有时用于仓库物流中，因为它可以有效地测量高架起重机移动物体所需的时间（因为起重机可以同时沿x和y轴移动）。
它还广泛用于电子CAM应用程序，尤其是针对这些应用程序的优化算法。 与高架起重机类似，许多工具，例如在平面上操作的绘图或钻孔机，光绘仪等，通常由两个电动机在x和y方向上控制。
闵可夫斯基距离，是欧氏空间中的一种测度，被看做是欧氏距离和曼哈顿距离的一种推广。严格意义上讲，闵可夫斯基距离不是一种距离，而是一组距离的定义。
两点        的  阶Minkowski 距离定义为：
Minkowski距离也可以看作是  和  之间的分量方差的幂均值的倍数。
   下图显示了具有各种  值的单位圆（所有距中心单位距离的点的集合）
当  时，闵可夫斯基距离不再符合三角形法则，举个例子：当  ,   到  的距离等于  , 而    到这两个点的距离都是  。
闵可夫斯基距离比较直观，但是它与数据的分布无关，具有一定的局限性，如果 x 方向的幅值远远大于 y 方向的值，这个距离公式就会过度放大 x 维度的作用。所以，在计算距离之前，我们可能还需要对数据进行 z-transform 处理，即减去均值，除以标准差：
     ，  :该维度上的均值，  :该维度上的标准差
可以看到，上述处理开始体现数据的统计特性了。这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关（例如：身高较高的信息很有可能会带来体重较重的信息，因为两者是有关联的），这时候就要用到马氏距离（Mahalanobis distance）了。
  马哈拉诺比斯距离 是由印度统计学家 P. C. Mahalanobis 在1936年提出的，表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法。与欧氏距离不同的是它考虑到各种特性之间的联系（例如：一条关于身高的信息会带来一条关于体重的信息，因为两者是有关联的）并且是尺度无关的（scale-invariant），即独立于测量尺度。
对于一个均值为  ，协方差矩阵为  的多变向量  ，其马氏距离为：
  马哈拉诺比斯距离 也可以定义为两个服从同一分布并且其协方差矩阵为  的随机变量  与  的差异程度：
如果协方差矩阵为单位矩阵，马哈拉诺比斯距离就简化为欧氏距离；如果协方差矩阵为对角阵，其也可称为 标准化欧氏距离 。
其中  是  的标准差。
Mahalanobis距离在数据跨空间的满秩线性变换下得以保留。 这意味着，如果数据具有非平凡的零空间，则可以在将数据（非退化地）向下投影到数据的适当维数的任何空间之后，计算马氏距离。
对于任何维数的正态分布，观测的概率密度唯一地由马氏距离  确定。 具体而言，  是卡方分布的。 例如，维数为2时，特定计算的  小于某个阈值  的概率为  ，要确定达到特定概率  的阈值，  。 对于除2以外的维数，参询卡方分布。
在正态分布中，马氏距离小于1的区域（即椭圆体内距离1的区域）恰好是概率分布为凹形的区域。
对于正态分布，马氏距离与负对数似然的平方根成正比（在添加常数后，最小值为零）。
马氏距离的定义源于1927年基于测量确定头骨相似性的问题。
马氏距离已广泛用于聚类分析和分类技术。 它与用于多变量统计检验的霍特林T平方分布(Hotelling's T-square distribution)和用于监督分类的Fisher线性判别分析(Fisher's Linear Discriminant Analysis)密切相关。
为了使用马氏距离将测试点分类为属于N个类别之一，通常首先基于已知属于每个类别的样本来估计每个类别的协方差矩阵。 然后，给定一个测试样本，计算每个类别的马氏距离，并将测试点分类为马氏距离最小的那个类别。
马氏距离和杠杆通常用于检测离群值，尤其是在线性回归模型的开发中。 与其他样本点群具有更大的Mahalanobis距离的点被认为具有更高的杠杆作用，因为它对回归方程的斜率或系数影响更大。 马氏距离还用于确定多元离群值。 回归技术可用于通过两个或多个可变得分的组合来确定样本总体中的特定情况是否是异常值。 即使对于正态分布，点也可以是多变量离群值，即使它不是任何变量的单变量离群值（如沿线  集中的概率密度），使得马氏距离比单独检查尺寸更为灵敏。
在信息论中，两个等长字符串之间的 汉明距离 （Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它测量将一个字符串转换为另一个字符串所需的最小替换数，或可能将一个字符串转换为另一个字符串的最小错误数。 在一般的上下文中，汉明距离是用于测量两个序列之间的编辑距离的几个字符串指标之一。
  汉明重量 是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是1的个数，所以11101的汉明重量是4。
下列字符串的汉明距离为：
对于固定的长度 n ，汉明距离是该长度字符向量空间上的度量，很显然它满足非负、唯一及对称性，并且可以很容易地通过完全归纳法证明它满足三角不等式。
两个字 a 与 b 之间的汉明距离也可以看作是特定运算?的 a ? b 的汉明重量。
对于二进制字符串 a 与 b 来说，它等于 a  异或 b 以后所得二进制字符串中“1”的个数。另外二进制字符串的汉明距离也等于 n 维超正方体两个顶点之间的曼哈顿距离，其中 n 是两个字串的长度。
在统计中，巴氏距离衡量两个概率分布的相似性。 它与Bhattacharyya系数密切相关，后者是两个统计样本或总体之间重叠量的度量。
该系数可用于确定所考虑的两个样本的相对接近度。 它用于度量分类的类的可分离性，并且被认为比马哈拉诺比斯距离更可靠，因为当两个类的标准偏差相同时，马哈拉诺比斯距离是巴氏距离的特例。 因此，当两个类别的均值相似但标准差不同时，马氏距离将趋于零，而巴氏距离则根据标准差之间的差异而增长。
对于同一域  上的概率分布  和  ，巴氏距离定义为:
当  、  为离散概率分布时，Bhattacharyya系数为  。
当  、  为连续概率分布时，Bhattacharyya系数为  
在两种情况中，  并且  。   不服从三角形不等式，但是由  给出的Hellinger距离服从三角形不等式。
用最简单的公式表示，可以通过提取两个单独的分布或类的均值和方差来计算正态分布下两个类之间的Bhattacharyya距离：
其中：   是  和  分布之间的Bhattacharyya距离，   是分布  的方差，  是分布  的均值，  是两个不同的分布。
Fisher线性判别分析中使用的Mahalanobis距离是Bhattacharyya距离的特例。
  Metric geometry
    Distance
知识点：曼哈顿距离相关
传送门:
两点间的曼哈顿距离为:  
那它的结果可能有四种。取最大值即是它的结果:
稍微整理:将相同的点放在一个括号中得到：
推广到N个点之间的最大曼哈顿距离也是一样。
  问题2:如果要求某一个点到其他点的曼哈顿距离：四种情况：
把它当作  
然后再在集合中找对应的最值和它做运算即可
对于1,2,3维的观察归纳不难想到:
对于D维空间,坐标之间有D - 1 个符号，所以我们需要对  种组合方式做集合。然后从每个集合中取出最大最小做差，得到  种结果后再取最大值.
1.  力扣:翻转子数组得到最大的数组值  （最大曼哈顿距离）
2. hdu 6435 CSGO（最大曼哈顿距离）
曼哈顿距离vs欧氏距离
欧式距离，即欧几里得距离，是最常见的两点之间的距离表示法，它定义在 欧几里 得空间中，例如x = (x1,x2,...,xn)和y = (y1,y2,...,yn)的欧式距离可表示为：
  曼哈顿距离 ，是欧几里得空间中两点之间的线段在坐标轴上的投影的距离的和，例如x = (x1,x2) y = (y1,y2)则两点的曼哈顿距离可表示为：