給定平面上的點,直接的最近點對算法會比較每一對。分治法可以減少工作:先解兩半,再只在狹窄帶狀區域中檢查跨越分界的配對。但帶內仍可能有很多點,單憑狹窄寬度不能解釋效率;真正限制每點所需鄰點數的,是幾何分離論證。
算法還有數據次序的責任。點最初按 x 排列,但帶內必須按 y 檢查。讓遞歸調用返回已按 y 排序的列表,就能在線性時間合併。本節會證明幾何及次序兩項主張,並涵蓋相同 x 座標、重合點與距離平手。
指定點、距離與返回見證
定義 9.1.1
(兩個不同輸入位置的配對)
輸入為有限整數座標點序列 。不同下標可以有相同座標。對 ,歐氏距離(Euclidean distance)平方為
函數返回最小距離平方,以及達到它的兩個原下標。少於兩點時返回 (None, None)。兩個重合輸入位置的距離零,是合法最優值,不是欠缺點對的標記。
任何最近配對都可接受。實作不列舉全部平手配對,也不承諾下標配對字典序最小。
平方根在非負數上遞增,所以比較距離平方已足夠。整數相減、平方及相加保留精確比較。實際距離可以是無理數,返回平方可避免為選見證而引入捨入。
先把 (x, y, original_id) 記錄排序一次。相同座標會相鄰,所以預先檢查相鄰項,就可立即返回零距離配對。處理此情況後,每個遞歸最近距離都為正。按排序列表的中間下標切成兩半,即使很多 x 相同,也保留平衡大小。
每個遞歸結果帶回 y 排序點列
對至少兩點、已按 x 排列的列表,遞歸調用返回三項:最小距離平方、見證配對,以及按 (y, x, id) 排列的全部記錄。兩點或三點直接比較每對;較大調用分成左右列表,解兩半,再合併它們返回的 y 列表。
設子問題最小距離為 ,寫 ,目前平方界限為 。設 是右列表第一個 x 座標;所有左 x 不大於 ,右 x 不小於 。
引理 9.1.2
(帶狀區域包含所有改善的跨組配對)
設 為兩個子問題最小距離中的較小者, 為右列表的第一個 x 座標。若左側一點與右側一點的距離小於 ,則兩點都落在帶狀區域 內。
證明
(水平間距不超過距離)
設左點與右點的距離小於 。它們的水平間距不大於全距離,所以小於 。分割座標 介於兩點的 x 座標之間,因此每個端點與該直線的距離都小於 ,兩點都屬於帶狀區域 。所以帶狀區域外的配對不可能嚴格改善較好的子問題距離。距離相等的跨組配對不必找到,因為在「任一最小者」的約定下,已返回的子問題配對就是該值的見證。
程式用最初子問題界限測試 (x-c)**2 < best 建帶,並保留合併後的 y 次序,不計算浮點寬度。
為甚麼其後七項已足夠
同一遞歸子問題內,任何兩點距離至少為 ;不同子問題的點則未必如此,合併步驟正是要找出這種更近配對。
引理 9.1.3
(後續七個鄰項已足夠)
把帶狀區域按 排序。對帶狀區域內的點 ,在此次序中排在 之後、且垂直間距 的帶狀區域內的點至多有七個。
證明
(每個子問題四個小格)
固定帶狀區域內的點 。只有 y 次序在它之後且 的點,才可能與它構成改善配對。考慮這個垂直區間與帶狀區域的交集。對每個遞歸子問題分別來看,其點落在寬 、高 的區域內:左子問題用切割線的左側,右子問題用右側。
把每個子問題的區域分成兩列兩行的小格。小格的邊長至多為 ,對角線為 。同一子問題內的兩點相距至少 ,所以每個小格至多含該子問題的一個點。每個子問題四個小格,故此區間內連同 至多有八個點。因此垂直間距小於 的後續帶狀區域項至多七個。切割線上的點歸入它們實際所屬的子問題,所以 x 座標相等不會令這個計數含糊,小格邊界也可以一致地歸入某一個小格。y 座標相同而排在 之前的項只佔用這八個位置中的一些,不會增加 之後的項數。
證明透視
為甚麼上限是八而不是無界
這個證明有一個幾何成分和一個次序成分。幾何成分是小格邊長 :對角線小於 ,而子問題內部的分離性禁止這種情況,所以一個小格至多容納該子問題的一個點。次序成分是只考慮間距小於 的後續項,這把候選點限制在高度為 的區間內,因此只需兩行小格。沒有這個限制,帶狀區域可以容納任意多個點:把它們全放在切割線上,垂直方向相隔 即可。
恰好在切割線上的點以及在小格邊界上的點,只需要約定,不需要新的論證:每個點歸入它實際所屬的子問題,每條邊界歸入某一個小格,所以八個的計數不會因座標相等而削弱。
因此,每個帶內點最多比較其後七項。若某個較後項目的垂直差平方,已不小於目前最佳距離平方,其後項目的差至少一樣大,也可全部略過。
掃描途中最佳值可以降低,但帶與七鄰點證明仍用原子問題界限 :任何稍後改善也在原帶及原垂直區間。使用較小的目前垂直界限,只排除不能改善新見證的配對,毋須每次改善都重建帶。
例題 9.1.4
(跨組配對同時改善兩個子答案)
輸入記錄已按 x 排列:
| 原下標 | 點 | 遞歸組別 |
|---|---|---|
| 左 | ||
| 左 | ||
| 右 | ||
| 右 |
左配對距離平方為十,右配對為二十,所以初始平方界限是十,分界 。只有下標 1、2 在嚴格帶內:水平差平方為四及零;下標 0、3 則為 25、16。
按 y 排列,帶內先是下標 2,再是 1。垂直差平方為一,完整距離平方為 。結果是平方五、見證下標 1、2,實際距離為 。
例題 9.1.5
(x 座標相等與平衡的分割)
取四個點 ,它們的 全為 。按指標分割,把編號 0、1 放在左側,編號 2、3 放在右側,切割座標 ;若按 x 座標分割,就無法把它們分開。兩個子問題的距離平方分別為 和 ,所以界為 ,帶狀條件 保留全部四個點,並且它們已按 y 排序。對編號 0,下一項的垂直間距平方為 ,所以掃描中斷。對編號 1,下一項(編號 2)的間距平方為 ,距離平方為 ,於是最好值變為 ,見證為 ,這是一個跨越分割的配對。再下一項(編號 3)的間距平方為 ,掃描停止;之後的點找不到更小的值。結果是距離平方 ,與最小的垂直間距 吻合。帶狀區域含有所有點,但每個點至多只檢查後面兩項。
例題 9.1.6
(重合的點在遞歸之前處理)
對 ,排序後的記錄為 。前兩筆相鄰而座標相同,所以函數在任何遞歸之前就返回距離平方 和見證 。這種情形必須先排除:若 ,帶狀條件 不會選中任何點,而裝填論證(使用邊長 的小格,以及相距至少 的子問題點)也就失去意義。
反例模式
只取較好的子答案,會漏掉跨組配對
對例題四點,只返回較小子答案會得到十,真正答案卻是跨分界的五。遞歸只涵蓋同一邊內部配對,不能代替帶狀論證。
相同 x 也不能全部送到同一子問題;純按座標分割可能極不平衡。按排序記錄下標分割,才保留平衡遞推,而幾何證明仍容許點在分界上相等。
常見錯誤
(把零距離當作缺少配對)
像 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 列表,是因為合併兩個按全序 排好的列表,得到的就是排好序的並集。
兩個引理都假設 ,所以初步的重複點檢查是證明的一部分,而不只是加速手段。沒有它,子問題距離為零會令帶狀區域為空,論證便不再涵蓋跨組配對。
保留線性合併步驟,並計入記憶體
對長度 調用,合併 y 列表、建帶及每點最多七次比較,都只需 工作。因此,平衡遞歸在 時,連初始 x 排序在內,共需 次比較與算術操作。
反例模式
每次重新排序帶,會多出一個對數因子
若每個遞歸層都自行按 y 排序帶,而不是把已排序 y 列表向上傳,合併步驟可能需 。遞推變成 ,一般界限便為 。
距離答案仍可能正確,改變的是可證明的時間。維持 y 次序是快速算法的一部分,不是偶然實作細節。
教學實作用切片、合併列表及帶列表,因此不是常數額外空間。最高同時儲存量是 個點記錄參照,加 遞歸框架:調用依序執行,一條活動遞歸路徑的大小形成幾何級數,每次調用只持有常數個與其大小成正比的列表。所有調用累積配置量,不等於同時存活記憶體。
這些界限計算機器字操作與參照。若座標絕對值至多 ,距離平方至多 ;固定位元實作必須容納中間差、平方及總和。Python 整數維持精確,但任意大整數算術與比較仍有位元成本。幾何證明只在推理時使用實數 ,程式全程比較整數平方。
練習與詳解
快速檢查
(重建例題的跨組改善)
對四個例題點,列出兩個子問題距離平方、分界座標、按原下標表示的帶內次序,以及最後距離平方。返回為甚麼是五,而不是其平方根?
解答 · 答案
子數值是十、二十,分界 。帶的 y 次序是下標 2、1,距離平方是五。介面返回平方以保留精確整數比較,歐氏距離則為 。
快速檢查
(用每個子問題內的分離性證明七)
每邊的半帶垂直區間用了多少個小格?為甚麼每格最多一個該子問題的點?這如何限制目前點之後的數量?
解答 · 答案
每邊四格,兩列兩行,對角線為 。同一子問題兩點若在一格,會違反子分離界限。包括目前點合共最多八,所以垂直差小於 的較後候選最多七個。
快速檢查
(處理相同座標而不失去平衡)
很多 x 相同時,為甚麼按排序列表下標分割?預先檢查對 [(2,3),(9,0),(2,3)] 返回甚麼?下標 0、2 為甚麼仍是合法點對?
解答 · 答案
下標分割保留子大小平衡,純座標分割卻可能把幾乎所有點送到一側。重合檢查返回平方零、下標 0、2。雖然位置相同,它們是不同輸入項目,形成合法最小配對。
快速檢查
(按見證契約解釋嚴格剪枝)
為甚麼帶可以略去離分界水平距離恰好 的點?y 差平方等於目前最佳值時,為甚麼也可略去?程式是否聲稱列出每個等距最優配對?
解答 · 答案
該水平差不可能屬於嚴格改善子界限的跨組配對。同理,垂直差已等於目前距離,也不可能嚴格改善。已有見證達到該值,任取一個最優配對已足夠。程式沒有列舉全部或字典序最小見證的聲稱。
快速檢查
(答案改善後保留原裝填界限)
若一次帶內比較降低最佳距離平方,為甚麼原帶與其後七項界限仍足夠?使用目前 y 差界限停止,為甚麼安全?
解答 · 答案
稍後每個改善也小於原子界限,所以仍在原帶及原向前垂直區間內,該處最多只有七個較後候選。較小目前 y 閾值只會排除不能勝過新見證的配對;其後 y 的差不更小,故一次不符合界限後可略去餘下項目。
快速檢查
(分清時間與最高同時空間的論證)
把 y 次序向上傳,為甚麼避免第二個對數因子?每個遞歸調用配置幾個列表,是否代表最高同時空間是 ?
解答 · 答案
合併兩個已排序子列表只需線性;每次重新排序列表或帶,可能令合併成本變成 ,總界限變為 。最高空間不同:順序遞歸只沿幾何縮小的活動路徑持有常數個按大小比例的列表,合共 個參照,加對數框架。它不是常數空間,但累積配置也不是最高同時存活記憶體。