数学严格证明

在一维情境中，假设我们有一组点 $a_1, a_2, \dots, a_n$，我们想找到一个点 $x$ 使得总距离 $\sum_{i=1}^n |a_i - x|$ 最小化。

思考过程

1. 代价函数: 设距离总和函数为 $f(x) = \sum_{i=1}^n |a_i - x|$。

2. 单调性: 当我们从左向右移动点 $x$，即增加 $x$ 的值时，离 $x$ 左侧的点 $a_i$ 的距离 $|a_i - x|$ 增加，离 $x$ 右侧的点 $a_i$ 的距离 $|a_i - x|$ 减少。

3. 关键点：考虑 $x$ 跨过某个点 $a_j$ 时的函数变化。特别在 $x=a_j$ 时，所有小于等于 $a_j$ 的点 $|a_i - x|$ 减小或不变，所有大于 $a_j$ 的点 $|a_i - x|$ 增加。若 $x$ 从 $a_j - \epsilon$ (一个小量 $\epsilon$) 移动到 $a_j + \epsilon$，如果左边点的数量多于右边点的数量，$f(x)$ 的值将增加；反之则减少。因此，将 $x$ 置于左右点数量相等的地方（或尽可能平衡的地方）是有利的。

断点

由于 $|a_i - x|$ 是 V 形，其最小值发生在 $a_i = x$ 时，因此寻找最小化 $f(x)$ 的点就是寻找中位数

严谨证明

要使 $\sum_{i=1}^n |a_i - x|$ 达到最小，关键在于 $x$ 的选择。考虑下面的两种情况：

• 当 $n$ 是奇数时，中位数存在且唯一，设为 $a_k$。在 $a_k$ 处，距其左侧的点数等于距其右侧的点数。
• 当 $n$ 是偶数时，有两个中位数 $a_{n/2}$ 和 $a_{n/2 + 1}$。在此范围内任何 $x \in [a_{n/2}, a_{n/2 + 1}]$ 使得损失函数不变，即所有这些点都可以作为最小化曼哈顿距离的解。

对于两种情况，选择中位数 (或中位数区间任意一个点) 显然最小化了从 $x$ 到所有点 $\{a_i\}$ 的曼哈顿距离。

引用：

• 如果将 $x$ 移动到既非左中位数也非右中位数的其他位置，则至少有一侧将有更多的点会导致距离之和增加，因为距离增加部分无法通过另一侧距离减少来完全抵消。

通过以上证明，中位数是曼哈顿距离问题中最优解的关键所在。对于二维问题（曼哈顿距离中），该结论可以分别在 $x$ 轴和 $y$ 轴独立应用。因此，对于 $(x_i, y_i)$，分别求 $x$ 和 $y$ 的中位数即为最优解。