文章目錄

• • @[toc]
  • • 問題描述
    • 一維最接近點對算法
    • • `Python`實現
    • 二維最接近點對算法
    • • 分治算法
      • 時間復雜性
      • `Python`實現

問題描述

• 給定平面上$n$個點，找其中的一對點，使得在$n$個點組成的所有點對中，該點對的距離最小

一維最接近點對算法

Python實現

import sysdef closest_pair(points):points.sort()  # 按照橫坐標排序min_dist = sys.maxsize  # 初始化最小距離為一個很大的數closest = None  # 初始化最接近點對為 Nonefor i in range(len(points) - 1):dist = abs(points[i] - points[i + 1])  # 計算相鄰點對的距離if dist < min_dist:min_dist = distclosest = (points[i], points[i + 1])return closestpoints = [2, 4, 1, 5, 8, 9, 3]res = closest_pair(points)print(f'最接近的點對: {res}')

二維最接近點對算法

分治算法

• 選取一垂直線$l:x=m$，$m$為$S$中各點$x$坐標的中位數，將$S$分割為 S 1 = { p ∈ S ∣ x ( p ) ≤ m } S_{1} = \set{p \in S \mid x(p) \leq m} S1?={p∈S∣x(p)≤m}和 S 2 = { p ∈ S ∣ x ( p ) > m } S_{2} = \set{p \in S \mid x(p) > m} S2?={p∈S∣x(p)>m}
• 遞歸地在$S_1$和$S_2$上解最接近點對問題，分別得到$S_1$和$S_2$中的最小距離$d_1$和$d_2$
• 設 d = min ? { d 1 , d 2 } d = \min\set{d_{1} , d_{2}} d=min{d1?,d2?}，若$S$的最接近點對$(p,q)$之間的距離小于$d$，則$p$和$q$必分屬于$S_1$和$S_2$，設$p\in S_1$，$q\in S_2$，則$p$和$q$距直線$l$的距離均小于$d$
• $P_1$和$P_2$分別表示直線$l$的左側和右側寬為$d$的兩個垂直長條區域，則$p\in P_1$且$q\in P_2$，此時$P_1$中所有點與$P_2$中所有點構成的點對均為最接近點對的候選者，在最壞情況下有$n^2/4$對這樣的候選者，但是對于$P_1$中任一點$p$，$P_2$中最多只有$6$個點與它構成最接近點對的候選者
  • 實際上對于$P_1$中任一點$p$，若與$P_2$中的點構成最接近點對的候選者，則必有$distance(p,q)<d$，滿足這個條件的$P_2$中的點一定落在一個$d\times 2d$的矩形$R$中
  • 可將矩形$R$的長為$2d$的邊$3$等分，將長為$d$的邊$2$等分，由此導出$6$個$(d/2)\times (2d/3)$的矩形，矩形$R$中最多只有$6$個$S$中的點

• 合并步驟中，最多只需檢查$6\times n/2=3n$個候選者，為了確切地知道要檢查哪$6$個點，將$p$和$P_2$中的點投影到垂直線$l$上，能與$p$點一起構成最接近點對候選者的$q$與$p$在$l$上投影點的距離小于$d$，且這種投影點最多只有$6$個，若將$P_1$和$P_2$中所有$S$中點按其$y$坐標排好序，則對$P_1$中所有點，對排好序的點列做一次掃描，就可以找出所有最接近點對的候選者

時間復雜性

$$T(n)=\{\begin{array}{ll}O(1),& n<4\\ 2T(n/2)+O(n),& n\ge 4\end{array}$$

$$T(n)=O(n\log n)$$

Python實現

import math# 計算兩點之間的歐幾里德距離
def dist(p1, p2):return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)# 分治法求解最接近點對問題
def closest_pair(points):# 如果點集中的點個數小于等于 3 個, 直接計算并返回最小距離對if len(points) <= 3:min_dist = float('inf')min_pair = Nonefor i in range(len(points)):for j in range(i + 1, len(points)):d = dist(points[i], points[j])if d < min_dist:min_dist = dmin_pair = (points[i], points[j])return min_pair# 將點集按照 x 坐標排序sorted_points = sorted(points, key=lambda p: p[0])# 將點集分成左右兩部分mid = len(sorted_points) // 2left_points = sorted_points[:mid]right_points = sorted_points[mid:]# 遞歸求解左右兩部分的最接近點對left_min_pair = closest_pair(left_points)right_min_pair = closest_pair(right_points)# 取左右兩部分最接近點對的最小距離if left_min_pair is None:min_dist = dist(right_min_pair[0], right_min_pair[1])min_pair = right_min_pairelif right_min_pair is None:min_dist = dist(left_min_pair[0], left_min_pair[1])min_pair = left_min_pairelse:left_dist = dist(left_min_pair[0], left_min_pair[1])right_dist = dist(right_min_pair[0], right_min_pair[1])if left_dist <= right_dist:min_dist = left_distmin_pair = left_min_pairelse:min_dist = right_distmin_pair = right_min_pair# 在橫跨左右兩部分的點中尋找更近的點對mid_x = sorted_points[mid][0]strip = []# 將點集按照 y 坐標排序sorted_points = sorted(points, key=lambda p: p[1])for point in sorted_points:if abs(point[0] - mid_x) < min_dist:strip.append(point)for i in range(len(strip)):for j in range(i + 1, min(i + 7, len(strip))):d = dist(strip[i], strip[j])if d < min_dist:min_dist = dmin_pair = (strip[i], strip[j])return min_dist, min_pairpoints = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]min_dist, min_pair = closest_pair(points)print(f'最接近的點對為: {min_pair}, 點對距離為 {min_dist}')

---