切比雪夫距离

1 基本概念

1.1 定义

切比雪夫距离是一种用于度量两点差异的距离度量。设有两点 \(x=(x_1,x_2,\dots,x_n)\) 与 \(y=(y_1,y_2,\dots,y_n)\)，其切比雪夫距离定义为各坐标差绝对值的最大值： \[

d_\infty(x,y)=\max_{1\le i\le n}	x_i-y_i	.

\] 在二维情形中，它刻画的是两点在水平或竖直方向上“差得最厉害”的那一项，从而反映整体差异的上界。

1.2 几何直观

1.2.1 二维平面中的等距图形

在二维平面中，给定某个半径 \(r\)，满足 \(d_\infty(x,y)=r\) 的点落在以某点为中心的正方形边界上；满足 \(d_\infty(x,y)\le r\) 的点构成正方形区域（边界到内部全部包含）。因此，切比雪夫距离的“等距线/等距曲线”呈现明显的折线几何特征，而不是圆或菱形那类更常见的连续曲线。

1.2.2 与网格移动的关系

若把平面看作规则网格，并考虑从点 \(x\) 到点 \(y\) 的移动，“距离”可以理解为需要的最大单方向步数。因为在每一维上要把坐标差至少“走满”到位，而整体移动所需的步数由最大的那一维差值决定。直观上，它对应“以最慢的那条轴为准”的同步更新思想：只要某一坐标差很大，就会成为最终距离的决定因素。

1.3 记号与别名

1.3.1 ∞范数

切比雪夫距离与向量的 \(\infty\) 范数密切相关。对向量 \(v\)，\(\infty\) 范数定义为 \[

\|v\|_\infty=\max_i	v_i	.

\]

于是切比雪夫距离也可写为 \(d_\infty(x,y)=\|x-y\|_\infty\)。

1.3.2 棋盘距离

“棋盘距离”强调在棋盘格上度量格点间差异的直观感受：在二维坐标中，其等距形状为正方形，使得“从一个格点到另一个格点需要多远”的概念更贴近网格语言。

1.3.3 最大范数

“最大范数”常用于强调其本质是对各分量取最大绝对值。该名称在工程或算法语境中较常见，便于提醒距离的计算规则与“取最大”直接对应。

2 数学性质

2.1 距离公理

2.1.1 非负性

对任意点 \(x,y\)，由于绝对值非负且最大值保持非负性， \[

d_\infty(x,y)=\max_i	x_i-y_i	\ge 0。

\]

2.1.2 对称性

交换 \(x\) 与 \(y\) 不改变坐标差的绝对值： \[

d_\infty(x,y)=\max_i	x_i-y_i	=\max_i	y_i-x_i	=d_\infty(y,x)。

\]

2.1.3 三角不等式

对任意 \(x,y,z\)，对每个分量都有 \[

x_i-z_i	\le	x_i-y_i	+	y_i-z_i	.

\] 取各分量的最大值可得 \[

d_\infty(x,z)=\max_i	x_i-z_i	\le \max_i\big(	x_i-y_i	+	y_i-z_i	\big)\le d_\infty(x,y)+d_\infty(y,z),

\] 从而满足三角不等式。因此它确实是一个度量。

2.2 与其他范数的关系

2.2.1 与欧氏距离的比较

欧氏距离对应 \(\ell_2\) 范数： \[ d_2(x,y)=\sqrt{\sum_i (x_i-y_i)^2}. \] 二者都刻画“幅度差”，但切比雪夫距离只看最大分量差，欧氏距离则把所有分量的贡献综合起来。直观上，若只有一个方向差很大而其他方向很小，两者会非常接近；若各方向差均匀，则欧氏距离往往更“平滑”，而切比雪夫距离表现得更“受限于最大轴”。

2.2.2 与曼哈顿距离的比较

曼哈顿距离对应 \(\ell_1\) 范数： \[

d_1(x,y)=\sum_i	x_i-y_i	.

\] \(\ell_1\) 会累加每一维的差异，因而对“多维同时偏离”的情况更敏感；而 \(\ell_\infty\) 则把注意力集中在最显著的那一维，是一种“保守上界”式的度量。

2.2.3 范数等价性

在有限维向量空间中，不同范数诱导的拓扑是等价的。具体到 \(\ell_p\) 与 \(\ell_\infty\)，存在常数 \(c,C>0\)（依赖维度）使得对所有向量 \(v\)： \[

c\|v\|_\infty \le \|v\|_p \le C\|v\|_\infty。

\] 因此在同一有限维空间里，收敛与连续性等性质不会因选用哪种范数而本质改变，但数值大小会有尺度差。

2.3 几何结构

2.3.1 球与单位球

“单位球”指满足 \(\|x\|_\infty\le 1\) 的集合。其在 \(\mathbb{R}^n\) 中对应超立方体（包含其面与内部），边界为由平面拼接而成的折面。由于没有圆弧，几何结构更偏向多面体。

2.3.2 等距集与超立方体

给定中心点 \(x\) 与半径 \(r\)，集合 \(\{y:\ d_\infty(x,y)\le r\}\) 正好是以 \(x\) 为中心、边长为 \(2r\) 的超立方体。等距集 \(d_\infty(x,y)=r\) 对应超立方体的边界面集合。因此在高维中，“等距”仍然由多面体结构刻画。

2.3.3 维度升高时的形状变化

当维度从二维扩展到三维与更高维，切比雪夫“球”（超立方体）所包含的面数量迅速增长，几何直觉上会更难以直观观察。然而其核心特征保持：半径由最大坐标差决定，形状总是由坐标轴方向的界限拼接形成。维度越高，边界复杂度越高，但计算规则依旧简单。

3 计算方法

3.1 坐标差法

3.1.1 逐维取差

计算两点之间距离时，先对每个坐标维度求差值并取绝对值： \[

\Delta_i=	x_i-y_i	。

\]

3.1.2 取最大值

再在所有 \(\Delta_i\) 中取最大者： \[ d_\infty(x,y)=\max_i \Delta_i。 \] 这一规则使得它常被视为“线性时间、常数开销较低”的距离度量：只需遍历一次各维并维护当前最大值。

3.2 矩阵与向量表示

3.2.1 向量范数形式

若把差向量写为 \(v=x-y\)，则 \[

d_\infty(x,y)=\|v\|_\infty.

\] 这种写法在理论推导与代码实现中都更紧凑：先求差，再调用“最大绝对值”的范数运算。

3.2.2 距离矩阵的构造

在批量计算中，常需要对集合 \(X=\{x^{(1)},\dots,x^{(m)}\}\) 与 \(Y=\{y^{(1)},\dots,y^{(k)}\}\) 构造距离矩阵 \(D\)，其中 \[ D_{ab}=d_\infty(x^{(a)},y^{(b)}). \] 直接做法是对每对样本计算坐标差并取最大值；若在实现上利用张量广播，可把“逐维取差与取最大”组织成向量化操作，提高效率。

3.3 算法实现

3.3.1 直接计算

单次计算的伪流程可概括为：初始化最大值为 0，逐维更新 \(\max \leftarrow \max(\max,	x_i-y_i	)\)，结束后输出最大值。由于只依赖最大运算，分支较少，适合在简单循环或向量化环境中实现。

3.3.2 批量计算

批量场景下通常采用广播或分块策略：把所有样本在维度上对齐，计算差的绝对值张量，再沿维度轴执行最大归约以得到距离矩阵。若数据规模较大，可通过分块减少内存峰值，同时保持算法逻辑一致。

3.3.3 数值稳定性

当坐标是浮点数时，切比雪夫距离涉及绝对值与最大值操作。它一般不会像涉及平方根或除法那样带来额外误差来源，但在极大/极小数值混合或存在 NaN/Inf 时仍需做输入检查。对 NaN 的传播规则应与具体数值库保持一致。

4 应用领域

4.1 计算几何

4.1.1 最近邻问题

在最近邻检索中，选择合适的距离度量会影响“最近”的含义。使用切比雪夫距离时，最近邻对应的是在某个坐标方向上差异最大的那类点，因此在处理网格化数据、坐标轴分辨率明确的场景时直观性较强。

4.1.2 矩形覆盖与包围盒

切比雪夫距离的等距集为正方形（高维为超立方体），与轴对齐的包围盒（AABB）天然相容。许多几何过滤步骤需要快速判断两个区域是否可能相交或是否满足尺度约束，\(\ell_\infty\) 与“最大坐标差”的判定方式常被用于构造保守的裁剪条件，从而加速筛选。

4.2 机器人与路径规划

4.2.1 网格环境建模

在栅格地图中，机器人从一个格点到另一个格点时，常需要把距离转化为代价或可行性判断。若用切比雪夫距离作为启发式或风险度量，它等价于“最大方向差”带来的限制，特别适用于坐标轴对齐的移动约束或对齐的估计策略。

4.2.2 运动代价估计

在规划算法中，距离度量常被用作启发式函数或代价下界。切比雪夫距离因为不依赖于所有维度的综合累积，而是由最大偏差决定，因而在某些“同步更新受最慢约束”模型里更符合直觉：只要某方向差仍较大，代价就不会降低太快。

4.3 计算机图形学

4.3.1 像素距离度量

在图像处理中，像素点通常落在规则网格上。使用 \(\ell_\infty\) 衡量像素间差异时，等距区域呈现方形扩散，因此在需要“方形邻域”“最大像素偏差”意义的操作中较为常用。例如，某些形态学或邻域统计会通过设定阈值实现类似效果。

4.3.2 图像形态分析

当结构元素采用轴对齐的几何形状时，切比雪夫距离对应的阈值膨胀或腐蚀效果与正方形/立方体结构元素一致。这样一来，算法可以用更简单的坐标约束表达，从而提升实现的可控性。

4.4 机器学习与数据分析

4.4.1 聚类中的距离选择

聚类算法的表现取决于距离度量。采用切比雪夫距离时，簇的形状倾向于围绕最大偏差形成的几何边界，直观上与超立方体边界相关。这种选择在特征尺度具有明确“上界约束”意义、或希望避免某些维度被过度平均时可能更合适。

4.4.2 特征尺度敏感性

由于距离取决于最大坐标差，特征未标准化时，量纲较大或变化幅度更大的特征会主导结果。为避免这种不平衡，实践中常进行特征缩放或归一化，使各维对“最大偏差”的贡献更均衡。

4.5 运筹优化

4.5.1 约束建模

在优化中，\(\ell_\infty\) 常用于表达“最大偏差不超过阈值”的约束。例如，一个向量变量 \(z\) 满足 \(\|z\|_\infty \le \tau\) 等价于对每个分量同时施加 \(-\tau \le z_i \le \tau\)。这种分量式的展开使得约束结构较清晰。

4.5.2 最大偏差最小化

将目标函数设置为最小化 \(\|x-y\|_\infty\) 或最小化 \(\|z\|_\infty\) 时，优化问题会倾向于均衡各维的最大误差，从而形成“消除最坏情况”的最优解。该思路与“鲁棒性”语言相近：关注最不利偏差而非平均误差。

5 相关拓展

5.1 广义距离度量

5.1.1 Minkowski距离族

切比雪夫距离属于 Minkowski 距离族的特殊情形。Minkowski 距离的一般形式为 \[

d_p(x,y)=\left(\sum_i	x_i-y_i	^p\right)^{1/p}.

\]

当 \(p\to\infty\) 时，距离趋向于 \(\max_i	x_i-y_i	\)，得到切比雪夫距离。

5.1.2 加权切比雪夫距离

为反映不同维度的重要性，可引入权重 \(w_i\ge 0\)。一种常见形式为 \[

d(x,y)=\max_i w_i	x_i-y_i	.

\] 较大的权重意味着该维度的偏差更容易主导距离值，适合在先验知识表明某些特征更关键时使用。

5.2 高维情形

5.2.1 高维数据中的解释

在高维空间里，距离仍由最大坐标差决定。由于维度增多，“出现较大差值的概率”会上升，导致很多样本对的切比雪夫距离可能变得相近。理解这一点有助于正确评估用 \(\ell_\infty\) 进行检索或聚类时的分辨率。

5.2.2 维数灾难与距离分布

当维度非常高时，不同距离度量的“区分度”可能下降，样本之间的距离分布会逐渐变窄。虽然切比雪夫距离只看最大分量，但高维下最大值更容易接近某个典型尺度，因此距离统计常出现集中现象。这也是高维数据分析中常讨论的距离劣化问题之一。

5.3 典型例题

5.3.1 二维坐标求距

若 \(x=(1,5)\)，\(y=(4,2)\)，则坐标差的绝对值分别为 \(	1-4	=3\)、\(	5-2	=3\)，最大值为 3，因此切比雪夫距离为 3。

5.3.2 三维及更高维求距

若 \(x=(0,2,-1)\)，\(y=(3,1,2)\)，则差的绝对值为 \(	0-3	=3\)、\(	2-1	=1\)、\(	-1-2	=3\)，最大值为 3，因此 \(d_\infty(x,y)=3\)。

5.3.3 最短路径与网格问题

在网格图中，若把边权与坐标差的最大变化量联系起来，切比雪夫距离可作为启发式下界或估计尺度。例如在需要评估“最坏方向偏差”是否能在步数预算内消除时，可用它快速判断是否可能达到目标，从而减少不必要的扩展。