如何從二維平面n個點中尋找距離最近兩個點？

如何理解分治演算法

什麼是分治演算法？簡單來說就是「分而治之」，也就是將原問題劃分成n個規模較小的，並且結構與原問題相似的子問題，然後去遞歸地解決這些子問題，最後再合併其結果，就得到原問題的解。

對於分治演算法來說，一般適合用遞歸來實現。分治演算法的遞歸實現中，每一次遞歸都會涉及如下三個操作。

分解：將原問題分解成一系列子問題。
解決：遞歸地求解各個子問題。
合併：將子問題的結果合併成原問題。

分治演算法的問題模型

對於可以採用分治演算法來解決的問題，一般都需要滿足以下幾個條件：

原問題與分解成的子問題具有相同的模式。
原問題分解成的子問題可以獨立求解，子問題之間沒有相關性。
具有分解終止條件，也就是說，當問題足夠小時，可以直接求解。
可以將子問題合併成原問題，而這個合併操作的複雜度不能太高，否則就起不到減小演算法總體複雜度的效果了。

下面我們來結合一個例子來看一下分治演算法的應用。我們來思考這麼一個問題，在給定一組在二維空間中的n個點，如何快速找出距離最近的兩點呢?最直觀的想法就是通過遍歷所有的點，然後求出所有點之間的距離，最後選出這些距離中的最小值對應的點，但是這種演算法的時間複雜度是O(n*n)，那有沒有更快的方法呢？那就是分治演算法。

為了方便起見，我們把N設置為2的k次冪，即N=2^k，k為正整數。下面我們來看一下這個問題是否滿足分治演算法的問題模型。

我們可以把問題N拆分成兩個子問題，每個子問題等於原問題的一半。我們在二維平面中畫一條垂線e，正好把N個點按照x軸位置拆分成2半（這個過程需要按照x軸排序，取中間的點），使得e的左右兩邊都有n/2個點。假設我們對e的左半邊部分遞歸的求出的最近點對的距離為ld，e的右半邊部分遞歸的求出的最近點對的距離為rd，接下來我們取出這兩個距離中的最小值d=min(ld,rd)，並且在e-d和e+d的位置上畫兩條垂線。這樣一來，我們把二維空間劃分成了3部分。如下圖所示：

這樣劃分後，最近點對的出現位置只能有以下三種可能。

兩個節點都在左邊區域。
一個節點在左，一個節點在右。
兩個節點都在右邊。

其中，1和3我們已經在求解子問題的時候已經解決了，現在我們只需要求解第2個問題就好了，即在mid區域進行搜索。我們下面來看如何在mid區域進行搜索，我們需要把這個帶狀區域內的所有節點按照Y軸遞增排序（我們可以在初始化的時候就快取起來，後面直接使用就好），從Y排序最小的節點開始，我們連續檢查帶狀區域內的每個點，計算所有比它的Y軸更大的點之間的距離，嘗試找出距離比d更小的點對。

假設我們需要對節點p進行比較，我們考慮這樣的一個空間，他是通過8個正方形（d/2*d/2）組成的一個長方形，p節點位於這個長方形的底邊上，

我們只需要判斷這個區域內的所有節點即可，因為一旦Y軸差距超過了d，就算x軸之差為0也會大於我們之前的距離d，所以不可能找出比 d 距離更小的點對。並且我們針對一個點，事實上只需要最多對比 7 次就能找出所有可能小於 d 的點對，因為每個小格子內部只可能出現1個節點，因為小格子內部的極限距離為 d / sqrt(2)，也就是正方形的對角線，但是這個距離顯然小於 d，如果這個正方形內部存在這樣一個節點。那麼之前對於 d 是左右區域內最小的點對距離的定義就被破壞了。所以不可能存在。

綜上所述：這個問題是符合分治演算法的問題模型的。下面我們來看一下程式碼實現。

import math
class Point:
     def __init__(self,x,y):
          self.x=x
          self.y=y

     def __str__(self):
          return 'x='+str(self.x)+',y='+str(self.y)


class RecentPoint:
     sortByXPoints = []
     sortByYPoints = []
     # p1=None
     # p2=None

     def getDistance(self, p1, p2):
          xDis = (p1.x - p2.x) ** 2
          yDis = (p1.y - p2.y) ** 2
          return math.sqrt(xDis + yDis)
     def findRecentPoint(self,data):
          self.sortByXPoints=sorted(data,key=lambda point:point.x)
          self.sortByYPoints=sorted(data,key=lambda point:point.y)

          return self._findRecentPoint(0, len(data)-1)

     def _findRecentPoint(self, p, q):

          #區域內只有兩對節點
          if (q-p)<=1:
               return self.getDistance(self.sortByXPoints[p], self.sortByXPoints[q])

          middle=math.floor((p+q)/2)

          ld=self._findRecentPoint(p, middle)
          rd=self._findRecentPoint(middle+1, q)

          # if(ld<rd):
          #      d=ld
          #      self.p1 = self.sortByXPoints[p]
          #      self.p2 = self.sortByYPoints[middle]
          # else:
          #      d = rd
          #      self.p1 = self.sortByXPoints[middle+1]
          #      self.p2 = self.sortByYPoints[q]

          d=min(ld,rd)

          #中心點
          e=self.sortByXPoints[middle].x + (self.sortByXPoints[middle+1].x - self.sortByXPoints[middle].x) / 2

          LeftEdge = e - d
          RightEdge = e + d

          #接下來我們檢查已 X 軸坐標 e 為中心點 從 e - d 開始 e + d 結束的帶狀區域內去檢測最近點
          #我們從中篩選所有帶狀區域內的點，並按照 Y坐標 的遞增排序進行排序

          insidePoint=[]
          for point in self.sortByYPoints:
               if(point.x>LeftEdge and point.x<RightEdge):
                    insidePoint.append(point)

          #開始對比節點,尋找是否比d更短
          for i in range(len(insidePoint)):
               for j in range(1,8):
                    if(i+j>=len(insidePoint)):
                         break;
                    dis=self.getDistance(insidePoint[i],insidePoint[i+j])

                    if(dis<d):
                         d=dis
                         # self.p1=insidePoint[i]
                         # self.p2=insidePoint[i+j]


          return d

data=[Point(1,6),Point(3, 4),Point(2, 5),Point(4, 8)]
s=RecentPoint()
print(s.findRecentPoint(data))
# print(s.p1)
# print(s.p2)
複製程式碼

` 今天的分享就到這裡，更多硬核知識，請關注公眾號，如果需要pdf文件，可以私信我哦。

Tags: leetcode 分治演算法數據結構與演算法面試