设计求解平面最邻近点对算法 1)数据没有事先预排序,设计算法O(n(logn)2)。 2)数据事先预排序,设计算法O(nlogn) 代码
时间: 2024-02-06 21:08:44 浏览: 17
1)数据没有事先预排序,设计算法O(n(logn)2)。
算法思路:
1. 将所有点按照x坐标进行排序。
2. 以中心线为界,将所有点分成左右两个集合。
3. 对左右两个集合分别进行递归调用,得到左右两个子问题的最小距离d1和d2。
4. 取d1和d2中的最小值作为当前问题的最小距离d。
5. 构造一个新的点集S',其中只包含横坐标在[x-d,x+d]范围内的点。
6. 将S'按照y坐标进行排序。
7. 在S'中寻找距离小于d的最邻近点对。具体方法是,对于每个点,只需要在其后面的至多7个点中找到距离该点小于d的最近点即可。
8. 返回d作为最终结果。
代码实现:
```python
import math
def dist(p1, p2):
return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
def closest_pair(points):
n = len(points)
if n <= 1:
return float('inf')
mid = n // 2
left_points = points[:mid]
right_points = points[mid:]
d1 = closest_pair(left_points)
d2 = closest_pair(right_points)
d = min(d1, d2)
center_x = (points[mid][0] + points[mid - 1][0]) / 2
S = [p for p in points if abs(p[0] - center_x) < d]
S.sort(key=lambda x: x[1])
for i in range(len(S)):
for j in range(i+1, len(S)):
if S[j][1] - S[i][1] >= d:
break
d = min(d, dist(S[i], S[j]))
return d
# 测试
points = [(1, 2), (3, 4), (5, 6), (7, 8), (2, 3), (4, 5), (6, 7), (8, 9)]
points.sort()
print(closest_pair(points)) # 输出结果为1.4142135623730951
```
2)数据事先预排序,设计算法O(nlogn)。
算法思路:
1. 将所有点按照x坐标进行排序。
2. 递归划分,对于每个子集合,先对y坐标进行排序,然后在子集合中寻找最邻近点对。
3. 返回所有子问题中距离最小的那个点对的距离。
代码实现:
```python
import math
def dist(p1, p2):
return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
def closest_pair(points):
n = len(points)
if n <= 1:
return float('inf')
mid = n // 2
left_points = points[:mid]
right_points = points[mid:]
d1 = closest_pair(left_points)
d2 = closest_pair(right_points)
d = min(d1, d2)
center_x = (points[mid][0] + points[mid - 1][0]) / 2
S = [p for p in points if abs(p[0] - center_x) < d]
S.sort(key=lambda x: x[1])
for i in range(len(S)):
for j in range(i+1, len(S)):
if S[j][1] - S[i][1] >= d:
break
d = min(d, dist(S[i], S[j]))
return d
def closest_pair_sort(points):
points.sort()
return closest_pair(points)
# 测试
points = [(1, 2), (3, 4), (5, 6), (7, 8), (2, 3), (4, 5), (6, 7), (8, 9)]
print(closest_pair_sort(points)) # 输出结果为1.4142135623730951
```