给定平面上的点,直接求最近点对可以比较每一对点。分治法可以减少工作:分别求解两半,再只在靠近分割线的窄条带中检查跨越分界的点对。条带可能包含很多点,所以仅凭宽度还不能解释效率;真正限制每个点需要检查的邻居数量的是几何上的间距论证。
算法还要满足一个顺序要求。点最初按横坐标排序,但检查条带时需要按纵坐标排列。让递归调用返回按纵坐标排序的列表,就能在线性时间内合并它们。我们将证明几何和排序两方面的结论,并处理横坐标相同、点重合以及距离并列的情况。
规定点、距离和返回的点对
定义 9.1.1
(由两个不同输入位置组成的点对)
设输入为有限整数坐标点序列 。不同下标的点可以坐标相同。对于 ,欧几里得距离(Euclidean distance)的平方为
函数返回最小距离平方,以及达到该值的一对原始下标。如果点不足两个,返回 (None, None)。两个输入位置上的点重合时,零距离是合法的最优值,而不是缺少点对的标记。
返回任意一对达到最小值的点即可。实现不会枚举所有并列点对,也不保证下标对的字典序最小。
比较距离平方已足够,因为平方根在非负数上单调递增。整数减法、平方和加法能保持比较精确。实际距离可能是无理数;返回平方值可以避免仅为选择点对而引入舍入误差。
先将记录 (x, y, original_id) 排序一次。坐标完全相同的记录相邻,因此预先检查相邻记录就能立即返回零距离点对。排除此情况后,每个递归子问题的最近距离都为正。按排序列表中间下标分成两半,即使许多点的横坐标相同,两边大小也保持平衡。
每个递归结果都携带纵坐标有序的点
对至少两个点组成的横坐标有序列表,递归调用返回三项:最小距离平方、达到该值的一对下标,以及按 (y, x, id) 排序的全部记录。两个或三个点直接比较所有点对。更大的调用分成左右列表,分别求解,再合并返回的两个纵坐标有序列表。
设两侧最小距离分别为 ,并记 。当前距离平方的上界为 。令 为右侧列表第一个点的横坐标;所有左侧点的横坐标不大于 ,所有右侧点的横坐标不小于 。
引理 9.1.2
(条带包含所有改进的跨侧点对)
设 为两个子问题最小距离中的较小者, 为右列表的第一个 x 坐标。若左侧一点与右侧一点的距离小于 ,则两点都落在条带 内。
证明
(水平间距不超过距离)
设左点与右点的距离小于 。它们的水平间距不大于全距离,所以小于 。分割坐标 介于两点的 x 坐标之间,因此每个端点与该直线的距离都小于 ,两点都属于条带 。所以条带外的点对不可能严格改进较好的子问题距离。距离相等的跨侧点对不必找到,因为在“任一最小者”的约定下,已返回的子问题点对就是该值的见证。
代码使用子问题给出的初始上界,通过 (x-c)**2 < best 构造条带,同时保留合并后的纵坐标顺序。它不计算浮点宽度。
为什么只需检查后续七项
在任一递归子问题内部,任意两点距离都至少为 。不同子问题的点则未必如此:合并步骤的目的正是寻找这样的更近点对。
引理 9.1.3
(后续七个邻项已足够)
把条带按 排序。对条带内的点 ,在此顺序中排在 之后、且纵向间距 的条带内的点至多有七个。
证明
(每个子问题四个小格)
固定条带内的点 。只有 y 顺序在它之后且 的点,才可能与它构成改进点对。考虑这个纵向带与条带的交集。对每个递归子问题分别来看,其点落在宽 、高 的区域内:左子问题用切割线的左侧,右子问题用右侧。
把每个子问题的区域分成两列两行的小格。小格的边长至多为 ,对角线为 。同一子问题内的两点相距至少 ,所以每个小格至多含该子问题的一个点。每个子问题四个小格,故此纵向带内连同 至多有八个点。因此纵向间距小于 的后续条带项至多七个。切割线上的点归入它们实际所属的子问题,所以 x 坐标相等不会使这个计数含糊,小格边界也可以一致地归入某一个小格。y 坐标相同而排在 之前的项只占用这八个位置中的一些,不会增加 之后的项数。
证明透视
为什么上限是八而不是无界
这个证明有一个几何成分和一个顺序成分。几何成分是小格边长 :对角线小于 ,而子问题内部的分离性禁止这种情况,所以一个小格至多容纳该子问题的一个点。顺序成分是只考虑间距小于 的后续项,这把候选点限制在高度为 的纵向带内,因此只需两行小格。没有这个限制,条带可以容纳任意多个点:把它们全放在切割线上,纵向相隔 即可。
恰好在切割线上的点以及在小格边界上的点,只需要约定,不需要新的论证:每个点归入它实际所属的子问题,每条边界归入某一个小格,所以八个的计数不会因坐标相等而削弱。
因此,每个条带点只需与其后至多七项比较。如果后续某项的纵坐标间距平方已经不小于当前最优距离平方,那么再后面的点间距至少同样大,也都可以跳过。
扫描过程中最优值可能下降。条带及七邻居证明仍使用子问题原来的上界 :任何后续改进也必定落在原条带和原纵向带内。用更小的当前纵向界进行检查只会舍弃无法改进新点对的候选,不必每次改进都重建条带。
例题 9.1.4
(跨侧点对改进两个子问题的答案)
使用以下已经按横坐标排序的输入记录:
| 原始编号 | 点 | 递归所属侧 |
|---|---|---|
| 左 | ||
| 左 | ||
| 右 | ||
| 右 |
左侧点对的距离平方为十,右侧为二十。因此初始距离平方上界为十,分割坐标 。只有编号 1 和 2 位于严格条带内:它们到分割线的水平距离平方为四和零,而编号 0 和 3 分别为 25 和 16。
按纵坐标排序,条带中编号 2 在编号 1 之前。二者的纵向间距平方为一,完整距离平方为 。结果为距离平方五,点对下标是 1 和 2;实际距离为 。
例题 9.1.5
(x 坐标相等与平衡的分割)
取四个点 ,它们的 全为 。按下标分割,把编号 0、1 放在左侧,编号 2、3 放在右侧,切割坐标 ;若按 x 坐标分割,就无法把它们分开。两个子问题的距离平方分别为 和 ,所以界为 ,条带条件 保留全部四个点,并且它们已按 y 排序。对编号 0,下一项的纵向间距平方为 ,所以扫描中断。对编号 1,下一项(编号 2)的间距平方为 ,距离平方为 ,于是最好值变为 ,见证为 ,这是一个跨越分割的点对。再下一项(编号 3)的间距平方为 ,扫描停止;之后的点找不到更小的值。结果是距离平方 ,与最小的纵向间距 吻合。条带含有所有点,但每个点至多只检查后面两项。
例题 9.1.6
(重合的点在递归之前处理)
对 ,排序后的记录为 。前两条相邻而坐标相同,所以函数在任何递归之前就返回距离平方 和见证 。这种情形必须先排除:若 ,条带条件 不会选中任何点,而装填论证(使用边长 的小格,以及相距至少 的子问题点)也就失去意义。
反例模式
仅取较好的子问题答案会漏掉跨侧点对
对于例题中的四个点,如果返回较小的子问题答案,就会返回十。真正的答案是跨越分割线的五。递归只覆盖同一侧内部的点对,不能取代条带论证。
也不能将横坐标相等的所有点都送入同一个子问题:纯粹按坐标分割可能严重失衡。按排序记录的下标分割能保持平衡递推,而几何证明仍允许点位于分割线上。
常见错误
(把零距离当作缺少点对)
像 if best: 这样的判断,会把合法的最优值 当成点数少于二时返回的 None。应改为判断 best is None。
常见错误
(对每个条带内的点扫描整个条带)
条带可以含有所有的点,例如所有点都在同一条竖直线上、纵向间距至少为 。若把每个条带内的点与其后所有条带内的点比较,就需要 时间。只需检查接下来的七项,并在纵向间距过大时提前中断。
精确计算距离平方的实现
输入点为整数对,这是类型和形状的前提;函数不验证这些条件。它创建新记录,不会改变调用者输入的顺序。内部过程只处理至少两个点的列表:较大调用在大小至少为四时才分割,而顶层少于两个点时已提前返回。
def closest_pair_squared(points):
records = sorted((x, y, index) for index, (x, y) in enumerate(points))
if len(records) < 2:
return None, None
for index in range(1, len(records)):
if records[index][:2] == records[index - 1][:2]:
return 0, (records[index - 1][2], records[index][2])
def squared(p, q):
return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2
def by_y(p):
return p[1], p[0], p[2]
def solve(xs):
length = len(xs)
if length <= 3:
best = squared(xs[0], xs[1])
pair = (xs[0][2], xs[1][2])
for first in range(length):
for second in range(first + 1, length):
candidate = squared(xs[first], xs[second])
if candidate < best:
best = candidate
pair = (xs[first][2], xs[second][2])
return best, pair, sorted(xs, key=by_y)
middle = length // 2
cut_x = xs[middle][0]
left_best, left_pair, left_y = solve(xs[:middle])
right_best, right_pair, right_y = solve(xs[middle:])
if left_best <= right_best:
best, pair = left_best, left_pair
else:
best, pair = right_best, right_pair
y_order = []
left = right = 0
while left < len(left_y) and right < len(right_y):
if by_y(left_y[left]) <= by_y(right_y[right]):
y_order.append(left_y[left])
left += 1
else:
y_order.append(right_y[right])
right += 1
y_order.extend(left_y[left:])
y_order.extend(right_y[right:])
strip = [p for p in y_order if (p[0] - cut_x) ** 2 < best]
for first, p in enumerate(strip):
for second in range(first + 1, min(first + 8, len(strip))):
q = strip[second]
if (q[1] - p[1]) ** 2 >= best:
break
candidate = squared(p, q)
if candidate < best:
best = candidate
pair = (p[2], q[2])
return best, pair, y_order
best, pair, _ = solve(records)
return best, pair
对于 [(-4,0),(-1,1),(1,0),(5,2)],返回 (5, (2,1));点对顺序相反不影响结论。对于 [(2,3),(9,0),(2,3)],返回距离平方零以及下标 0 和 2。竖直排列的点无需斜率或除法;距离并列按照所述的任意最优点对约定处理。
证明递归结果的完整正确性
命题 9.1.7
(递归合并的正确性)
在初步检查之后,对 条坐标两两不同的记录,递归例程返回最小距离平方、达到该值的两个原始下标,以及按 排序的全部记录。
证明
(对递归作归纳)
两个或三个点时,所有点对都被明确检查,返回的 y 顺序也已排好。设两个子结果对较大的调用都正确。它们较好的答案在父问题中是可行的,所以提供了一个带有真实见证的上界。
父问题的任何点对,不是在一个子问题之内,就是跨越分割。子问题内部的点对不可能优于该子问题的最优值。若跨侧点对严格改进初始的界,则由条带引理,它在条带内;由七邻项引理,它较后的端点在较前端点之后的七项之内。若它被当前的 y 间距界剪掉,则当前见证已经不比它差;否则它被明确比较。因此没有任何点对优于最后返回的值,而这个值总有两个输入下标作见证。合并两个子问题的 y 列表,恰好得到父问题按 y 排序的记录。
证明透视
归纳步骤用到哪些事实
归纳步骤依靠四项事实:子问题的答案(归纳假设)、条带引理、七邻项引理,以及合并。两种剪枝的理由不同。严格的条带测试丢弃不可能严格改进子问题界的点对;对 y 间距的中断成立,是因为列表已排序,所以其后每一项的间距至少同样大。合并恰好返回父问题的 y 列表,是因为合并两个按全序 排好的列表,得到的就是排好序的并集。
两个引理都假设 ,所以初步的重复点检查是证明的一部分,而不只是加速手段。没有它,子问题距离为零会使条带为空,论证便不再涵盖跨侧点对。
保持线性合并并计算内存
对于长度为 的一次调用,合并纵坐标列表、建立条带,以及对每个条带项进行至多七次比较,都需要 工作量。因此,当 时,平衡递归连同最初的横坐标排序,共需要 次比较和算术操作。
反例模式
每次重新排序条带会增加一个对数因子
如果每一层递归都独立按纵坐标排序条带,而不是向上返回已排序列表,合并步骤可能需要 。递推式变为 ,一般得到 的上界。
距离答案仍可能正确,改变的是能够证明的运行时间。维护纵坐标顺序是快速算法的一部分,而非无关紧要的实现细节。
这个教学实现使用切片、合并列表和条带列表,因此额外空间不是常数。峰值存储为 个点记录引用,加上 个递归栈帧:调用顺序执行,活动递归路径上保留的各级大小构成几何级数,每一级只有常数个与该调用规模成正比的列表。所有调用累计分配的空间不同于同时存活内存的峰值。
这些界统计机器字级操作与引用。若坐标绝对值至多为 ,距离平方至多为 ;固定宽度实现必须容纳中间的差、平方和总和。Python 整数保持精确,但任意长度整数的算术和比较有其位运算成本。几何证明仅在推理中使用实数 ;程序始终比较整数平方。
练习与详解
快速检查
(还原例题中的跨侧改进)
对于例题的四个点,给出两侧距离平方、分割坐标、按原始编号表示的条带顺序,以及最终距离平方。为什么返回五而不是它的平方根?
解答 · 答案
两侧值分别为十和二十;分割坐标 。条带按纵坐标的顺序为编号 2、1,它们的距离平方为五。接口返回距离平方,以保持整数比较精确;欧几里得距离为 。
快速检查
(利用各侧内部间距证明七邻居界)
每个子问题的半条带纵向带分为多少个小格?为什么每格最多包含该子问题的一个点?这如何限制当前点之后的数量?
解答 · 答案
每侧有四个格子,分成两列两行,对角线长度均为 。同一格内若有两个同侧点,会与子问题的最小间距矛盾。包括当前点在内总共至多八个点,因此纵向间距小于 的后续项至多七个。
快速检查
(在保持平衡的同时处理坐标相等)
许多点横坐标相同时,为什么按排序列表下标分割?对于 [(2,3),(9,0),(2,3)],预检查返回什么?为什么下标 0 和 2 仍构成有效点对?
解答 · 答案
按下标分割可以保持两侧大小平衡,即使按坐标分割会把几乎所有点送到一侧。重复点检查返回距离平方零及下标 0、2。尽管位置相同,它们是不同的输入位置,因此构成有效的最优点对。
快速检查
(在点对返回约定下解释严格剪枝)
为什么条带可以排除距分割线的水平距离恰好为 的点?为什么纵向间距平方等于当前最优值时也能剪枝?代码是否声称枚举所有等距最优点对?
解答 · 答案
这样的水平间距不可能属于严格改进子问题上界的跨侧点对。同样,纵向间距已经等于当前距离时,也不可能严格改进。已有点对已达到该值,足以满足返回任意一个最优点对的要求。代码不声称枚举全部最优解或返回字典序最小点对。
快速检查
(答案改进后仍使用原来的点数界)
如果一次条带比较降低了最优距离平方,为什么原条带和后续七项仍然足够?依据当前纵向间距界退出循环为什么安全?
解答 · 答案
任何后续改进也小于原子问题上界,因此位于原条带和原向前纵向带中,那里至多有七个后续候选。更小的当前纵向阈值只会去掉无法优于新点对的候选。后续纵坐标的间距不会更小,所以一旦不满足该界,其余项均可跳过。
快速检查
(区分运行时间与峰值空间的论证)
为什么向上返回纵坐标顺序可以避免第二个对数因子?每个递归调用分配多个列表,是否意味着这里的峰值存活空间为 ?
解答 · 答案
合并两个有序子列表只需线性时间;若在每次调用重新排序列表或条带,合并成本可能为 ,总界则为 。峰值空间的论证不同:顺序递归在按几何比例缩小的活动路径上,每层只保留常数个与该层规模成正比的列表,总共是 个引用,加上对数个栈帧。它不是常数空间,但累计分配量不等于峰值存活内存。