This is the 8th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

How to understand the divide-and-conquer algorithm

What is divide-and-conquer? Simply put, it is “divide and conquer”, that is, divide the original problem into n smaller subproblems with similar structure to the original problem, and then solve these subproblems recursively, and finally merge the results to get the solution of the original problem.

For dive-and-conquer algorithms, recursion is generally appropriate. In the recursive implementation of the divide-and-conquer algorithm, each recursion involves three operations.

  • Decomposition: the decomposition of the original problem into a series of subproblems.
  • Solve: solve each subproblem recursively.
  • Merge: Merge the results of subproblems into the original problem.

Problem model of divide and conquer algorithm

For problems that can be solved by using the divide and conquer algorithm, the following conditions are generally met:

  • The original problem has the same pattern as the decomposed subproblem.
  • The subproblems decomposed into the original problem can be solved independently, and there is no correlation between the subproblems.
  • There is a decomposing termination condition, that is, when the problem is small enough, it can be solved directly.
  • Subproblems can be merged into the original problem, but the complexity of the merge operation should not be too high, otherwise it will not reduce the overall complexity of the algorithm.

Let’s take a look at how divide-and-conquer works with an example. Let’s think about the problem, given a set of n points in two dimensions, how do you quickly find the nearest two points? The most intuitive idea is to go through all the points, figure out the distances between all the points, and then pick the point that corresponds to the smallest of those distances, but the time complexity of this algorithm is O(n*n), so is there a faster way? That’s divide-and-conquer.

For convenience, let’s set N to 2 to the k, which is equal to 2 to the k, where k is a positive integer. Now let’s see if this satisfies the dive-and-conquer problem model.

We can divide problem N into two subproblems, each of which is equal to half of the original problem. Let’s draw a vertical line E in the two-dimensional plane, dividing exactly N points in half along the X-axis (this process requires sorting along the X-axis, taking the middle points), so that there are N /2 points on either side of e. Suppose we recursively calculate the distance of the closest point pair for the left half of E as LD, and recursively calculate the distance of the closest point pair for the right half of e as RD, then we take the minimum value d=min(ld,rd) of the two distances, and draw two perpendicular lines between e-d and e+d. In this way, we divide the two-dimensional space into three parts. As shown in the figure below:

After this division, the location of the nearest point pair can only have the following three possibilities.

  1. Both nodes are in the left area.
  2. One node is on the left and one node is on the right.
  3. Both nodes are on the right.

We already solved 1 and 3 in the subproblem, and now we just need to solve the second problem, which is to search in the mid region. We see below how to search in the mid area, we need to put all nodes within the strip according to Y sorting (we can at the time of initialization is cached, behind it is good to use directly), since Y sorting the smallest node, we check the each point in the strip in a row, calculate all greater than its Y the distance between the point, Try to find a pair of points whose distance is smaller than D.

Suppose we want to compare nodes P, and we consider a space that is a rectangle made up of eight squares (d/2*d/2), with nodes P at the bottom edge of the rectangle,

All we need to do is identify all the nodes in this region, because once the Y-axis difference exceeds d, even if the X-axis difference is 0, it’s going to be greater than our previous distance d, so it’s impossible to find a pair of points that are less distant than d. And for one point, in fact, you only have to do at most seven comparisons to find all pairs of points that might be less than D, because there’s only one node in each cell, because the limit distance inside the cell is d over SQRT (2), which is the diagonal of the square, but this distance is obviously less than D, If there’s a node inside this square. So the previous definition that d is the smallest point pair distance in the left and right region is broken. So it can’t exist.

To sum up: this problem conforms to the dive-and-conquer problem model. Let’s look at the code implementation.

`

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): 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: # self.p2 = self.sortbyxpoints [q] d=min(ld,rd) # self.p2 = self.sortbyxpoints [q] d=min(ld,rd) # self.p2 = self.sortbyxpoints [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 # then we have X coordinate for the center e check Starting from the e - d e + d # banded area to detect the end of the closest point we comb through all the points inside the strip, InsidePoint =[] for point in self.sortbyypoints: if(point.x>LeftEdge and point.x<RightEdge): 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 = self. P2 =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)Copy the code

‘Today’s share is over, more hardcore knowledge, please pay attention.